Determining a known character string equivalent to a query string

• US 7,546,316 B2
• Filed: 06/14/2007
• Issued: 06/09/2009
• Est. Priority Date: 05/03/2000
• Status: Expired due to Fees

• 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:
  US11/818,297
• Publication Number:
  US 20070244890A1
• Time in Patent Office: 726 Days
• Field of Search: 707 3- 5, 707/7, 707/10, 707/104.1, 704/7, 704/9, 704/10, 382/224, 382/229, 382/230
• 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 method comprising:

modifying, using one or more processors, a query string of characters using a set of heuristics;

performing, using one or more processors, 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 for the modified query string in the corpus, performing, by one or more processors, the following steps in order to locate an equivalent for the modified query string;

forming a plurality of sub-strings of characters from the modified query string, the sub-strings having varying lengths such that at least two of the formed sub-strings differ in length, each sub-string comprising a composition of characters selected based on a frequency of occurrence of the composition in the modified query string; and

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

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

3. 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.

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

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

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

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

34. The 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 sequence in the modified query string.

8. A system comprising:

at least one processor configured to execute;

a heuristics module for modifying a query string of characters using a set of heuristics;

a comparator module, coupled to the heuristics module, for 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 find an exact match for the modified query string;

a sub-string formation and information retrieval module for locating an equivalent for the modified query string, responsive to the comparator module not finding an exact match for the modified query string in the corpus, said sub-string formation module, coupled to the comparator module, for forming a plurality of sub-strings of characters from the modified query string, the sub-strings having varying lengths such that at least two of the formed sub-strings differ in length, each sub-string comprising a composition of characters selected based on a frequency of occurrence of the composition in the modified query string; and

said information retrieval module, coupled to the sub-string formation module, for performing an information retrieval technique on the sub-strings formed from the modified query string to identify a known string of characters equivalent to the query string.

9. The system of claim 8, wherein the information retrieval module further comprises:

a weight module for weighting the sub-strings;

a score module for scoring known strings of characters; and

a retrieval module, coupled to the weight and score modules, for retrieving information associated with the known string having the highest score.

10. The system of claim 9, further comprising an accept module, coupled to the retrieval module, for accepting the information retrieved as an exact match for the highest score greater than a first threshold.

11. The system of claim 9, further comprising an accept module, coupled to the retrieval module, for presenting the information retrieved to a user for manual confirmation for the highest score less than a first threshold and greater than a second threshold.

12. The system of claim 9, further comprising an accept module, coupled to the retrieval module, for presenting the information retrieved to the user as a set of options for a user to select for the highest score less than a second threshold and greater than a third threshold.

13. The system of claim 8, wherein the sub-string formation module forms a plurality of substrings of characters by successively extending sub-strings based on frequency of occurrence of the sub-strings in the modified query string.

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

15. The system of claim 8, wherein the set of heuristics comprises removing whitespace from the query string.

16. The system of claim 8, wherein the heuristics module comprises a removal module for removing a portion of the query string.

17. The system of claim 8, wherein the heuristics module comprises a replacement module for replacing a symbol in the query string with an alternate representation for the symbol.

18. The system of claim 8 further comprising a database update module for storing a database entry indicating that the query string is an equivalent of the identified known string.

35. The system of claim 8, 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 sequence in the modified query string.

36. The system of claim 9, 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.

19. A computer-readable medium comprising program code to:

modify a query string of characters using a set of heuristics;

perform 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 for the modified query string in the corpus, locate an equivalent for the modified query string by forming a plurality of sub-strings of characters from the modified query string, the sub-strings having varying lengths such that at least two of the formed sub-strings differ in lengths each sub-string comprising a composition of characters selected based on a frequency of occurrence of the composition in the modified query string, and

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

20. The computer-readable medium of claim 19, wherein the information retrieval technique further comprises:

weighting the sub-strings;

scoring known strings of characters; and

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

21. The computer-readable medium of claim 20, further comprising program code to automatically accept the known string having the highest score as an exact match, responsive to the highest score being greater than a first threshold.

22. The computer-readable medium of claim 20, further comprising program code to present the known string having the highest score to a user for manual confirmation, responsive to the highest score being less than a second threshold and greater than a first threshold.

23. The computer-readable medium of claim 20, further comprising program code to present the known string having the highest score to a user to select the equivalent string of characters, responsive to the highest score being less than a second threshold and greater than a third threshold.

24. The computer-readable medium of claim 19, wherein forming the plurality of substrings comprises successively extending sub-strings based on a frequency of occurrence of the sub-strings in the modified query string.

25. The computer-readable medium of claim 19, 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.

26. The computer-readable medium of claim 19, wherein the set of heuristics comprises removing whitespace from the query string.

27. The computer-readable medium of claim 19, wherein the set of heuristics comprises removing a portion of the query string.

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

29. The computer-readable medium of claim 19 further comprising program code to store a database entry indicating that the query is an equivalent of the identified known string.

37. The computer-readable medium of claim 19, 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 sequence in the modified query string.

38. The computer-readable medium of claim 20, 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.

30. A system comprising:

at least one processor configured to execute;

heuristics program code for modifying a query string of characters using a set of heuristics;

a comparator for 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;

sub-string formation program code and information retrieval program code for locating an equivalent for the modified query string, responsive to the comparator not finding an exact match for the modified query string in the corpus, said formation program code for forming a plurality of sub-strings of characters from the modified query string, the sub-strings having varying lengths such that at least two of the formed substrings differ in length, each sub-string comprising a composition of characters selected based on a frequency of occurrence of the composition in the modified query string; and

said information retrieval program code operating on the sub-strings formed from the modified query string for identifying a known string of characters equivalent to the query string.

31. The system of claim 30, wherein the information retrieval program code further comprises:

code for weighting the sub-strings;

code for scoring known strings of characters; and

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

32. The system of claim 31, 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.

33. The system of claim 30, 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 sequence in the modified query string.