QUERY SPELLER

• US 20080046405A1
• Filed: 08/16/2006
• Published: 02/21/2008
• Est. Priority Date: 08/16/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhou, Ming, Gao, Jianfeng, Li, Mu, Hullender, Gregory N., Crumb, Janine R., Zhang, Haoyong, Olds, Elliott K., Lv, Yajuan
• Granted Patent: US 7,818,332 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence

Abstract

Candidate suggestions for correcting misspelled query terms input into a search application are automatically generated. A score for each candidate suggestion can be generated using a first decoding pass and paths through the suggestions can be ranked in a second decoding pass. Candidate suggestions can be generated based on typographical errors, phonetic mistakes and/or compounding mistakes. Furthermore, a ranking model can be developed to rank candidate suggestions to be presented to a user.

Claims

1. A method, comprising:

receiving a search query containing a plurality of terms;

generating candidate spellings for each search term in the query;

assigning a score to each of the candidates spellings;

generating candidate query paths based on the scores for each candidates spelling, each candidate query path containing a candidate spelling for each term in the search query;

determining a relationship among the candidate spellings in each candidate query path; and

ranking the candidate query paths as a function of the scores and the relationship.

2. The method of claim 1 wherein the candidate spellings are generated as a function of at least one of edit distance between a term in the search query and a term in a lexicon, phonetic similarity between a term in the search query and a term in the lexicon and a word boundary similarity between a term in the search query and a term in the lexicon.

3. The method of claim 2 wherein assigning a score is performed as a function of edit distance, phonetic similarity and word boundary similarity.

4. The method of claim 3 wherein each score is used as an estimate to generate the candidate query paths.

5. The method of claim 1 and further comprising:

identifying features in the search query and wherein ranking the candidate query paths is performed as a function of the features identified in the search query.

6. The method of claim 1 wherein the candidate spellings are generated based on terms in a lexicon.

7. A method, comprising:

receiving a search query;

accessing a lexicon of terms;

generating candidate spellings from the search query as a function of a spelling similarity between the search query and terms in the lexicon, a phonetic similarity between the search query and terms in the lexicon and word boundary similarity between the search query and terms in the lexicon; and

ranking the candidates spellings as a function of the spelling similarity, the phonetic similarity and the word boundary similarity.

8. The method of claim 7 wherein the search query contains a plurality of terms and the candidate spellings are generated for each of the terms in the search query.

9. The method of claim 7 wherein the spelling similarity is computed using an edit distance measure.

10. The method of claim 7 wherein the phonetic similarity is computed as a function of phonetic encoding of the search query and terms in the lexicon.

11. The method of claim 10 wherein the phonetic similarity is further computed as a difference between surface letters in the search query and surface letters of terms in the lexicon.

12. The method of claim 7 and further comprising:

identifying features in the search query and wherein ranking the candidates spellings is further performed as a function of the features.

13. A method, comprising:

obtaining a set of feature functions corresponding to a score for candidate query paths of suggested spelling corrections given a search query;

generating a set of weights for each feature function in the set of feature functions;

accessing a plurality of samples, each sample having a query and an expected spelling suggestion for the query; and

adjusting the weights in the set of weights based on the plurality of samples.

14. The method of claim 13 and further comprising:

determining a score for each query and each expected spelling suggestion for the query in the plurality of samples based on the feature functions;

comparing the score for the query and the score for the expected spelling suggestion for each of the plurality of samples; and

adjusting the weights as a function of the comparison of the scores for the query and the scores for the expected spelling suggestions in each of the plurality of samples.

15. The method of claim 13 wherein at least one feature function relates to a frequency of a query term appearing in a lexicon.

16. The method of claim 13 wherein at least one feature function relates to a length of a query term.

17. The method of claim 13 wherein at least one feature function relates to a relationship between two terms in the query.

18. The method of claim 13 wherein at least one feature function relates to an edit distance measure of similarity between a query term and a term in an expected spelling suggestion.

19. The method of claim 13 wherein the feature functions relate to a phonetic similarity of a query term and a term in an expected spelling suggestion.

20. The method of claim 13 wherein the feature functions relate to a word boundary similarity of a query term and a term in an expected spelling suggestion.