Systems and methods for improved spell checking

Abstract

The present invention leverages iterative transformations of search query strings along with statistics extracted from search query logs and/or web data to provide possible alternative spellings for the search query strings. This provides a spell checking means that can be influenced to provide individualized suggestions for each user. By utilizing search query logs, the present invention can account for substrings not found in a lexicon but still acceptable as a search query of interest. This allows a means to provide a higher quality proposal for alternative spellings, beyond the content of the lexicon. One instance of the present invention operates at a substring level by utilizing word unigram and/or bigram statistics extracted from query logs combined with an iterative search. This provides substantially better spelling alternatives for a given query than employing only substring matching. Other instances can receive input data from sources other than a search query input.

1 - 20 . (canceled)  
   
   
       21 . A system that facilitates spell checking, comprising: 
 a component that receives input data containing text; and    a spell checking component that identifies a set of potentially misspelled substrings in the text and proposes at least one alternative spelling for the substring set based on at least one query log; the query log comprising data utilized by users to query a data collection over a time frame, wherein the identification of a misspelled substring is based at least in part on the frequency of occurrence of the substring in the at least one query log.    
   
   
       22 . The system of  claim 21 , the spell checking component further utilizes user-dependent information in proposing at least one alternative spelling.  
   
   
       23 . The system of  claim 21 , the alternative spelling for the substring set is further based on at least one trusted lexicon; the trusted lexicon comprising at least one selected from the group consisting of a trusted lexicon with content and a trusted lexicon without content.  
   
   
       24 . The system of  claim 21 , the spell checking component further employs a list of stop words; the list of stop words comprising at least one selected from the group consisting of a list of stop words with content and a list of stop words without content.  
   
   
       25 . The system of  claim 21 , the spell checking component further utilizes substring co-occurrence statistics from the at least one query log.  
   
   
       26 . The system of  claim 25 , the substring co-occurrence statistics comprising substring bigram counts; a substring bigram comprising a pair of substrings in a text.  
   
   
       27 . The system of  claim 26 , the substring bigram comprising a pair of adjacent substrings in a text.  
   
   
       28 . The system of  claim 28 , the substring co-occurrence statistics for the list of stop words with content further comprising a substring bigram with stop-word-sequence-skipping counts.  
   
   
       29 . The system of  claim 21 , the spell checking component generates a set of alternative spellings that are substrings in at least one selected from the group consisting of the at least one query log and at least one lexicon.  
   
   
       30 . The system of  claim 29 , a Viterbi search is employed to facilitate in determining the optimum set of alternative spellings according to the context model in each iteration.  
   
   
       31 . The system of  claim 30 , the Viterbi search can employ fringes to restrict a search for alternative spellings in an iteration such that for every pair of adjacent substrings, if any of the substrings is in at least one trusted lexicon, then only one of the substrings is allowed to change in that iteration.  
   
   
       32 . A method of facilitating spell checking, comprising: 
 receiving input data containing text;    identifying a set of potentially misspelled substrings in the text, wherein the identification of a misspelled substring is based at least in part on the prevalence of the substring in at least one query log; the query log comprising data utilized by users to query a data collection over a time frame; and    proposing at least one alternative spelling for the substring set.    
   
   
       33 . The method of  claim 32 , the alternative spelling for the substring is based at least one of the at least one query log or on at least one trusted lexicon; the trusted lexicon comprising at least one of a trusted lexicon with content or a trusted lexicon without content.  
   
   
       34 . The method of  claim 33 , further comprising: 
 employing, at least in part, a list of stop words to facilitate in determining at least one alternative spelling; the list of stop words comprising at least one selected from the group consisting of a list of stop words with content and a list of stop words without content;    utilizing substring occurrence and co-occurrence statistics from at least one query log; the query log comprising a histogram of queries asked over a time frame and the substring occurrence and co-occurrence statistics from the query log are stored in a same searchable data structure;    handling concatenated and/or split substrings in a same manner as handling individual substrings; and    generating a set of alternative spellings that are substrings in at least one selected from the group consisting of at least one query log and at least one lexicon, the set of alternative spellings comprising a set of alternative spellings determined via an iterative correction process.    
   
   
       35 . The method of  claim 34 , the iterative correction process comprising: 
 changing at least one substring to another substring as an alternative spelling; and    halting the iterative correction process when all possible alternative spellings are less appropriate than a current set of alternative spellings; the alternative spellings and their appropriateness are computed based on a probabilistic string distance and a statistical context model.    
   
   
       36 . The method of  claim 35 , further comprising in each iteration of the iterative correction process: 
 utilizing a searchable substring data structure extracted from at least one query log and at least one trusted lexicon to generate the set of alternative spellings for a substring;    restricting the set of alternative spellings for each substring to within a probabilistic distance δ from an input substring; the restriction being imposed within each iteration without limiting the iterative correction process as a whole; and    searching for an optimum set of alternative spellings via utilization of a statistical context model; the statistical context model comprising substring occurrence and co-occurrence statistics extracted from at least one query log.    
   
   
       37 . The method of  claim 36 , further comprising: 
 employing a Viterbi search to facilitate in determining the optimum set of alternative spellings according to the context model in each iteration; the Viterbi search can employ fringes to restrict a search for alternative spellings in an iteration such that for every pair of adjacent substrings, if any of the substrings is in at least one trusted lexicon, then only one of the substrings is allowed to change in that iteration.    
   
   
       38 . A system that facilitates spell checking queries to a search engine, comprising: 
 means for receiving input data containing text; and    means for identifying a set of potentially misspelled substrings in the text and proposing at least one alternative spelling for the substring set based on at least one query log; the query log comprising data utilized by users to query a data collection over a time frame, the identification of a misspelled substring is based at least in part on the number of occurrence of the substring in the at least one query log.    
   
   
       39 . The system of  claim 38 , means for identifying a set of potentially misspelled substrings in the text further employs a list of stop words.  
   
   
       40 . The system of  claim 39 , the list of stop words containing high frequency words and function words and their frequent misspellings.