Method of spell-checking search queries

• US 7,194,684 B1
• Filed: 04/09/2002
• Issued: 03/20/2007
• Est. Priority Date: 04/09/2002
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Shazeer, Noam
• Primary Examiner(s): Hong; Stephen
• Assistant Examiner(s): HONEYCUTT, KRISTINA B
• Application Number:
  US10/119,375
• Time in Patent Office: 1,806 Days
• Field of Search: 715/533, 715/532, 715/530, 715/540, 707/3, 707/6
• US Class Current: 715/205
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A computer-implemented method for determining whether a target text-string is correctly spelled is provided. The target text-string is compared to a corpus to determine a set of contexts which each include an occurrence of the target text-string. Using heuristics, each context of the set is characterized based on occurrences in the corpus of the target text-string and a reference text-string. Contexts are characterized as including a correct spelling of the target text-string, an incorrect spelling of the reference text-string, or including an indeterminate usage of the target text-string. A likelihood that the target text-string is a misspelling of the reference text-string is computed as a function of the quantity of contexts including a correct spelling of the target text-string and the quantity of contexts including an incorrect spelling of a reference text-string. In one application, the target text-string is received in a search query, the search executed following a spell-check.

Claims

1. A computer-implemented method for detecting spelling errors in a target text-string, comprising:

comparing the target text-string to a database of contexts and determining from the comparison, a set of contexts characterized as

X contexts, where each of the X contexts are characterized as including a correct spelling of the target text-string, and

Y contexts, where each of the Y contexts are characterized as including an incorrect spelling of a reference text-string; and

computing a likelihood that the target text-string is a misspelling of the reference text-string as a function of one of X or Y, relative to a combination of X and Y;

characterizing a context as including an incorrect spelling of the reference text-string in response to occurrences of the reference text-string in the context being at least equal to a pre-determined minimum quantity threshold, and a ratio of reference text-string occurrences in the context to target text-string occurrences in the context being greater than a pre-determined ratio threshold.

2. The method of claim 1, wherein the likelihood that the target text-string is a misspelling of the reference text-string is computed as a function of X, relative to X plus Y.

3. The method of claim 1, further comprising applying heuristics to characterize a context of the database, the heuristics being a function of occurrences of the target text-string in the context and occurrences of the reference text-string in the context.

4. The method of claim 1, wherein the pre-determined ratio threshold is at least equal to 1.

5. The method of claim 4, wherein the pre-determined quantity threshold is 3, and the pre-determined ratio threshold is 1.

6. The method of claim 1, wherein no contexts simultaneously have occurrences of the reference text-string at least equal to a pre-determined maximum quantity threshold, and occurrences of the target text-string at most equal to a pre-determined minimum quantity threshold.

7. The method of claim 6, wherein the pre-determined maximum quantity threshold is 3, and the pre-determined minimum quantity threshold is 1.

8. The method of claim 1, further comprising:

characterizing a context as including a correct spelling of the target text-string in response to occurrences of the target text-string in the context being at least equal to a second pre-determined quantity threshold, and a ratio of target text-string occurrences in the context to reference text-string occurrences in the context being greater than a second pre-determined ratio threshold.

9. The method of claim 8, wherein the second pre-determined ratio threshold is at least equal to 1.

10. The method of claim 9, wherein the second pre-determined quantity threshold is 3, and the second pre-determined ratio threshold is 1.

11. The method of claim 10, further comprising characterizing a context having an occurrence of the target text-string as indeterminate in response to the context not being characterizable as one of:

including a correct spelling of the target text-string, or including an incorrect spelling of the reference text-string.

12. The method of claim 1, further comprising:

characterizing a context as having a correct spelling of the target text-string in response to occurrences of the target text-string in the context being at least equal to a pre-determined quantity threshold, and a ratio of target text-string occurrences in the context to reference text-string occurrences in the context being greater than a pre-determined ratio threshold.

13. The method of claim 12, wherein the pre-determined ratio threshold is at least equal to 1.

14. The method of claim 13, wherein the pre-determined quantity threshold is 3, and the pre-determined ratio threshold is 1.

15. The method of claim 1, wherein the target text-string is a word and the reference text-string is a word.

16. The method of claim 1, wherein the target text-string is a phrase, and the reference text-string is a phrase.

17. The method of claim 1, further comprising receiving a search query, the search query including the target text-string.

18. The method of claim 17, wherein the database is a corpus including naturally occurring text that is similar in patterns of content and misspelling to the search query.

19. The method of claim 1, wherein the database is a corpus including naturally occurring text that is similar in patterns of content and misspelling to a search query.

20. The method of claim 1, wherein the set of contexts may be characterized to include Z contexts, where each of the Z contexts are characterized as an indeterminate context.

21. The method of claim 20, wherein each of X, Y and Z is a positive integer.

22. A computer-implemented method for detecting spelling errors in a target text-string, comprising:

selecting a reference text-string having characteristics corresponding to the target text-string;

computing from a first database, a first ratio of occurrences of the reference text-string relative to occurrences of the target text-string;

computing from a second database, a second ratio of occurrences of the reference text-string relative to occurrences of the target text-string; and

determining a likelihood that the target text-string is misspelled as a function of the first ratio and the second ratio, wherein the first and second databases are each a corpus including naturally occurring text that are similar in patterns of content, the second database being a better-spelled corpus than the first database;

wherein the characteristics corresponding to the target text-string include an edit distance between the target text-string and the reference text-string, and an edit distance between the target text-string and any previously identified misspellings of the reference text-string, and wherein the target text-string is misspelled when the second ratio is greater than a first comparison threshold, and the ratio of the second ratio to the first ratio is greater than a second comparison threshold.

23. The method of claim 22, wherein the characteristics corresponding to the target text-string include the an edit distance between the target text string and the reference text string, and an edit distance between the target text string and any previously identified misspellings of the reference text string.

24. The method of claim 22, wherein the target text-string is misspelled when the second ratio is greater than a first comparison threshold, and the ratio of the second ratio to the first ratio is greater than a second comparison threshold.

25. The method of claim 24, wherein the first comparison threshold is 2 and the second comparison threshold is 2.

26. The method of claim 22, further comprising receiving a search query, the search query including the target text-string.

27. A computer-implemented method for detecting spelling errors in a target text-string, comprising:

comparing the target text-string to a first and second database of contexts and determining from the comparisons, a set of contexts including contexts characterized as

X contexts, each of the X contexts characterized as including a correct spelling of the target text-string,

Y contexts, each of the Y contexts characterized as including an incorrect spelling of a reference text-string, and

Z contexts, each of the Z contexts characterized as an indeterminate context; and

computing a likelihood that the target text-string is a misspelling of the reference text-string as a function of one of X and Y, relative to X plus Y;

wherein a context is characterized as including an incorrect spelling of the reference text-string or characterized as including a correct spelling of the target text-string in response to (1) a first ratio, determined from the first database, of occurrences of the reference text-string in the context to occurrences of the target text-string in the context, (2) a second ratio determined from the second database, of occurrences of the reference text-string in the context to occurrences of the target text-string in the context, and (3) a third ratio of the second ratio to the first ratio, the first and second databases each being a corpus including naturally occurring text that are similar in patterns of content, the second database being a better-spelled corpus than the first database.

28. The method of claim 27 wherein a context is characterized as including a misspelling if the first ratio is greater than a first predetermined comparison threshold, the second ratio is greater than a second comparison threshold, and the third ratio is greater than a third predetermined comparison threshold.

29. The method of claim 28 where the comparison thresholds are 1, 2, and 2 respectively.

30. The method of claim 27 wherein a context is characterized as including a correct spelling of the target text-string when the second ratio is less than a predetermined comparison threshold.

31. The method of claim 30 where the predetermined comparison threshold is 1.

32. The method of claim 27, further comprising receiving a search query, the search query including the target text-string.