Determining a known character string equivalent to a query string

• US 7,251,665 B1
• Filed: 05/03/2001
• Issued: 07/31/2007
• Est. Priority Date: 05/03/2000
• Status: Expired due to Term

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Dunning, Ted E., Kindig, Bradley D.
• Primary Examiner(s): Wong; Leslie
• Application Number:
  US09/848,982
• Time in Patent Office: 2,280 Days
• Field of Search: 704/1, 704/9, 704/10, 704/7, 707530-533, 707/536, 707/540, 707/104.1, 382/230, 382/224, 382/229
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 40/279 Recognition of textual entities
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

A system, method, and computer program product perform text equivalencing. The text equivalencing is performed by modifying a string of characters by applying a set of heuristics, comparing the modified strings of characters to known strings of characters. If a match is found, the text equivalencing engine performs database update and exits. If no match is found, sub-strings are formed by grouping together frequently occurring sets of characters. An information retrieval technique is performed on the sub-strings to determine equivalent text.

Claims

1. A computer-implemented method comprising:

modifying a query string of characters using a predetermined set of heuristics;

performing a character-by-character comparison of the modified query string with at least one known string of characters in a corpus in order to locate an exact match for the modified query string; and

responsive to not finding an exact match, performing the following steps in order to locate an equivalent for the modified query string;

forming a plurality of sub-string of characters from the query string, the sub-strings having varying lengths such that at least two of the formed sub-strings differ in length; and

using an information retrieval technique on the sub-strings formed from the query string to identify a known string of characters equivalent to the query string,

wherein the information retrieval technique further comprises;

weighting the sub-strings;

scoring known strings of characters; and

retrieving information associated with the known string having the highest score.

2. The method of claim 1, further comprising, responsive to the highest score being greater than a first threshold, automatically accepting the known string having the highest score as an exact match.

3. The method of claim 1, further comprising, responsive to the highest score being less than a second threshold and greater than a first threshold, presenting the known string having the highest score to a user for manual confirmation.

4. The method of claim 1, further comprising, responsive to the highest score being less than a second threshold and greater than a third threshold, presenting the known string having the highest score to a user to select the equivalent string.

5. The method of claim 1, wherein forming a plurality of sub-strings of character comprises successively extending sub-strings based on frequency of occurrence in the modified query string.

6. The method of claim 1, wherein the query string is selected from the group consisting of a song title, a song artist, an album name, a book title, an author'"'"'s name, a book publisher, a genetic sequence, and a computer program.

7. The method of claim 1, wherein the predetermined set of heuristics comprises removing whitespace from the query string.

8. The method of claim 1, wherein the predetermined set of heuristics comprises removing a portion of the query string.

9. The method of claim 1, wherein the predetermined set of heuristics comprises replacing a symbol in the query string with an alternate representation for the symbol.

10. The method of claim 1 further comprising storing a database entry indicating that the query string is an equivalent of the identified known string.

11. The computer-implemented method of claim 1, wherein the length of a sub-string is determined based on one or more character sequences identified in the modified query string and a corresponding frequency of occurrence for each identified character sequences.

12. The computer-implemented method of claim 1, wherein a weight for a given sub-string is based at least in part on a number of times the sub-string occurs in the query.