Method of spell-checking search queries

• US 8,051,374 B1
• Filed: 02/02/2007
• Issued: 11/01/2011
• 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): Ries; Laurie
• Assistant Examiner(s): Mills; Frank D
• Application Number:
  US11/670,885
• Time in Patent Office: 1,733 Days
• Field of Search: 715/257
• US Class Current: 715/257
• 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 method comprising:

receiving, by one or more processors of one or more server devices, a target text-string in a search query from a user device;

identifying, by one or more processors of one or more server devices, a set of contexts, from within a corpus of contexts, that include the target text-string;

determining, by one or more processors of one or more server devices, a quantity of correct spelling contexts in the set of contexts, where the correct spelling contexts include a correct spelling of the target text-string, where determining the quantity of correct spelling contexts, further comprises;

identifying a number of contexts in the set of contexts in which occurrences of the target text-string are equal to or greater than a first threshold and in which a ratio of target text-string occurrences to occurrences of a reference text-string is equal to or greater than a second threshold, and

determining the quantity of correct spelling contexts in the set of contexts that include a correct spelling of the target text-string based on the number of identified contexts;

determining, by one or more processors of one or more server devices, a quantity of incorrect spelling contexts in the set of contexts, where the incorrect spelling contexts include an incorrect spelling of the reference text-string;

determining, by one or more processors of one or more server devices, that the target text-string is a misspelling of the reference text-string based on the quantity of correct spelling contexts and the quantity of incorrect spelling contexts; and

forming, by one or more processors of one or more server devices, an alternative search query in response to determining that the target text-string is a misspelling of the reference text-string.

2. The method of claim 1, where the first threshold and the second threshold are at least 1.

3. The method of claim 1, where the first threshold is at least 1 and the second threshold is at least 2.

4. The method of claim 1, where the reference text-string includes one or more characteristics corresponding to the target text-string.

5. A method comprising:

receiving, by one or more processors of one or more server devices, a target text-string in a search query from a user device;

identifying, by one or more processors of one or more server devices, a set of contexts, from within a corpus of contexts, that include the target text-string;

determining, by one or more processors of one or more server devices, a quantity of correct spelling contexts in the set of contexts, where the correct spelling contexts include a correct spelling of the target text-string,

determining, by one or more processors of one or more server devices, a quantity of incorrect spelling contexts in the set of contexts, where the incorrect spelling contexts include an incorrect spelling of a reference text-string, where determining the quantity of incorrect spelling contexts, further comprises;

identifying a number of contexts in the set of contexts in which occurrences of the reference text-string are equal to or greater than a first threshold and in which a ratio of reference text-string occurrences to target text-string occurrences is equal to or greater than a second threshold, and

determining the quantity of incorrect spelling contexts in the set of contexts that include an incorrect spelling of the reference text-string based on the number of identified contexts,

determining, by one or more processors of one or more server devices, that the target text-string is a misspelling of the reference text-string based on the quantity of correct spelling contexts and the quantity of incorrect spelling contexts; and

forming, by one or more processors of one or more server devices, an alternative search query when the target text-string is a misspelling of the reference text-string.

6. The method of claim 5, where the first threshold and the second threshold are at least 1.

7. The method of claim 5, where the first threshold is at least 1 and the second threshold is at least 2.

8. A method comprising:

receiving, by one or more processors of one or more server devices, a target text-string in a search query from a user device;

identifying, by one or more processors of one or more server devices, a set of contexts, from within a corpus of contexts, that include the target text-string;

determining, by one or more processors of one or more server devices, a quantity of correct spelling contexts in the set of contexts, where the correct spelling contexts include a correct spelling of the target text-string,

determining, by one or more processors of one or more server devices, a quantity of incorrect spelling contexts in the set of contexts, where the incorrect spelling contexts include an incorrect spelling of a reference text-string;

determining, by one or more processors of one or more server devices, that the target text-string is a misspelling of the reference text-string based on the quantity of correct spelling contexts and the quantity of incorrect spelling contexts, where determining that the target text-string is the misspelling of the reference text-string is based on a function of the quantity of correct spelling contexts relative to a sum that includes the quantity of incorrect spelling contexts and the quantity of correct spelling contexts; and

forming, by one or more processors of one or more server devices, an alternative search query when the target text-string is a misspelling of the reference text-string.

9. A method comprising:

receiving, by one or more processors of one or more server devices, a target text-string in a search query from a user device;

identifying, by one or more processors of one or more server devices, a set of contexts, from within a corpus of contexts, that include the target text-string;

determining, by one or more processors of one or more server devices, a quantity of correct spelling contexts in the set of contexts, where the correct spelling contexts include a correct spelling of the target text-string,

determining, by one or more processors of one or more server devices, a quantity of incorrect spelling contexts in the set of contexts, where the incorrect spelling contexts include an incorrect spelling of a reference text-string;

determining, by one or more processors of one or more server devices, that the target text-string is a misspelling of the reference text-string based on the quantity of correct spelling contexts and the quantity of incorrect spelling contexts, where determining that the target text-string is the misspelling of the reference text-string is based on a function of the quantity of incorrect spelling contexts relative to a sum that includes the quantity of incorrect spelling contexts and the quantity of correct spelling contexts; and

forming, by one or more processors of one or more server devices, an alternative search query when the target text-string is a misspelling of the reference text-string.

10. A method comprising:

receiving, by one or more processors of one or more server devices, a target text-string, where the target text-string is received in a search query;

selecting, by one or more processors of one or more server devices, a reference text-string having characteristics corresponding to the target text-string;

determining, by one or more processors of one or more server devices, a first ratio of occurrences of the reference text-string relative to occurrences of the target text-string in a first memory;

determining, by one or more processors of one or more server devices, a second ratio of occurrences of the reference text-string relative to occurrences of the target text-string in a second memory;

determining, by one or more processors of one or more server devices, a likelihood that the target text-string is a misspelling of the reference text-string based on the first ratio and the second ratio; and

providing, by one or more processors of one or more server devices, the reference text-string in an alternative search query.

11. The method of claim 10, where the second memory includes fewer misspellings than the first memory.

12. The method of claim 11, where determining the likelihood that the target text-string is a misspelling further comprises:

determining a third ratio that includes a comparison of the second ratio to the first ratio; and

determining the likelihood that the target text-string is a misspelling based on the third ratio.

13. The method of claim 12, further comprising:

determining that the target text-string is a misspelling when the first ratio exceeds a first threshold, the second ratio exceeds a second threshold, and the third ratio exceeds a third threshold.

14. The method of claim 13, where the first threshold is at least 1, the second threshold is at least 2, and the third threshold is at least 1.5.

15. The method of claim 10, further comprising:

identifying a set of contexts from within a corpus of contexts that include the target text-string;

determining a quantity of correct spelling contexts, in the set of contexts, that include a correct spelling of the target text-string;

determining a quantity of incorrect spelling contexts, in the set of contexts, that include an incorrect spelling of the reference text-string; and

determining that the target text-string is not a misspelling of the reference text-string when a fourth ratio of incorrect contexts to correct contexts exceeds a fourth threshold.

16. A storage device including a computer-readable medium containing computer-executable instructions, comprising:

one or more instructions for receiving a search query from a user, where the search query includes a target text-string;

one or more instructions for selecting a reference text-string having characteristics corresponding to the target text-string;

one or more instructions for determining a first ratio of occurrences of the reference text-string relative to occurrences of the target text-string in a first memory;

one or more instructions for determining a second ratio of occurrences of the reference text-string relative to occurrences of the target text-string in a second memory;

one or more instructions for determining that the target text-string is a misspelling of the reference text-string based on of the first ratio and the second ratio; and

one or more instructions for providing an alternative search query.

17. The storage device of claim 16, where the one or more instructions for determining that the target text-string is a misspelling of the reference text-string includes:

one or more instructions for determining a third ratio that includes a comparison of the second ratio to the first ratio;

one or more instructions for determining a likelihood that the target text-string is a misspelling based on the third ratio; and

one or more instructions for determining that the target text-string is a misspelling when the first ratio exceeds a first threshold, the second ratio exceeds a second threshold, and the third ratio exceeds a third threshold.

18. The storage device of claim 16, where the one or more instructions for determining that the target text-string is a misspelling of the reference text-string includes:

one or more instructions for identifying a set of contexts from within a corpus of contexts that include the target text-string;

one or more instructions for determining a quantity of correct spelling contexts, in the set of contexts, that include a correct spelling of the target text-string;

one or more instructions for determining a quantity of incorrect spelling contexts, in the set of contexts, that include an incorrect spelling of the reference text-string; and

one or more instructions for determining that the target text-string is not a misspelling of the reference text-string when a fourth ratio of incorrect contexts to correct contexts exceeds a fourth threshold.

19. A storage device including a computer-readable medium containing computer-executable instructions, comprising:

one or more instructions for receiving a target text-string in a search query from a user device;

one or more instructions for identifying at least one reference text-string based on the target text-string;

one or more instructions for identifying a set of contexts, from within a corpus of contexts, that include the target text-string,

one or more instructions for determining a quantity of correct spelling contexts in the set of contexts, where the correct spelling contexts include a correct spelling of the target text-string, where the one or more instructions for determining the quantity of correct spelling contexts includes;

one or more instructions for identifying a number of contexts in the set of contexts in which occurrences of the target text-string are equal to or greater than a first threshold and in which a ratio of target text-string occurrences to occurrences of the at least one reference text-string is equal to or greater than a second threshold, and

one or more instructions for determining the quantity of correct spelling contexts in the set of contexts that include a correct spelling of the target text-string based on the number of identified contexts;

one or more instructions for determining a quantity of incorrect spelling contexts in the set of contexts, where the incorrect spelling contexts include an incorrect spelling of the at least one reference text-string;

one or more instructions for determining that the target text-string is a misspelling of the at least one reference text-string based on the quantity of correct spelling contexts and the quantity of incorrect spelling contexts; and

one or more instructions for providing an alternative search query when the target text-string is a misspelling of the at least one reference text-string.

20. A storage device including a computer-readable medium containing computer-executable instructions, comprising:

one or more instructions for receiving a target text-string in a search query from a user device;

one or more instructions for identifying at least one reference text-string based on the target text-string;

one or more instructions for identifying a set of contexts, from within a corpus of contexts, that include the target text-string;

one or more instructions for determining a quantity of correct spelling contexts in the set of contexts, where the correct spelling contexts include a correct spelling of the target text-string;

one or more instructions for determining a quantity of incorrect spelling contexts in the set of contexts, where the incorrect spelling contexts include an incorrect spelling of the at least one reference text-string, where the one or more instructions for determining that the target text-string is a misspelling of the reference text-string includes;

one or more instructions for determining that the target text-string is the misspelling of the at least one reference text-string based on a function of the quantity of correct spelling contexts relative to a sum that includes the quantity of incorrect spelling contexts and the quantity of correct spelling contexts; and

one or more instructions for providing an alternative search query when the target text-string is a misspelling of the at least one reference text-string.