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.
1. A method performed by a computer with a processor, comprising:
receiving a search query containing a representation of a text string having a plurality of search terms and identifying the search terms as being separated by spaces;
accessing, with the processor, a lexicon of terms stored in a memory;
generating, with the processor, a plurality of candidate spellings for each search term in the query based on a spelling similarity, a phonetic similarity, and a word boundary similarity, between the search terms and the terms in the lexicon, and organizing the candidate spellings in a structure to group candidate spellings for each search term;
assigning a score to each of the candidate spellings based on the spelling similarity, the phonetic similarity and the word boundary similarity;
generating, with the processor, a plurality of candidate query paths through the structure based on the scores that were previously assigned for each candidate spelling, each candidate query path containing a candidate spelling for each search term in the search query;
determining, with the processor, a relationship among the candidate spellings in each candidate query path; and
ranking, with a ranking model, the candidate query paths as a function of the scores of each candidate spelling and the relationship, the ranking model being generated by obtaining a set of feature functions for the ranking model that ranks candidate query paths of suggested spelling corrections given a search query;
generating, with the processor, a weight for each feature function in the set of feature functions to create weighted ranking parameters for the ranking model;
accessing, with a processor, a plurality of samples, each sample having a query and an expected spelling suggestion for the query;
employing the ranking model to rank candidate paths generated for each query; and
adjusting the weights for the weighted ranking parameters based on the ranking applied to the candidate paths for the plurality of samples.
2. The method of claim 1 wherein the spelling similarity comprises a measure of edit distance between a term in the search query and a term in a 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. The method of claim 1 wherein the phonetic similarity is computed as a function of phonetic encoding of the search query and terms in the lexicon.
8. The method of claim 1 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.
9. The method of claim 1 and further comprising:
identifying features in the search query and wherein ranking the candidates spellings is further performed as a function of the features.
10. The method of claim 1 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.
11. The method of claim 1 wherein at least one feature function relates to a frequency of a query term appearing in a lexicon.
12. The method of claim 1 wherein at least one feature function relates to a length of a query term.
13. The method of claim 1 wherein at least one feature function relates to a relationship between two terms in the query.
14. The method of claim 1 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.
15. The method of claim 1 wherein the feature functions relate to a phonetic similarity of a query term and a term in an expected spelling suggestion.
16. The method of claim 1 wherein the feature functions relate to a word boundary similarity of a query term and a term in an expected spelling suggestion.