Systems and methods for improved spell checking

• US 7,254,774 B2
• Filed: 03/16/2004
• Issued: 08/07/2007
• Est. Priority Date: 03/16/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Cucerzan, Silviu-Petru, Brill, Eric D.
• Primary Examiner(s): Hong; Stephen
• Assistant Examiner(s): TSUI, WILSON W
• Application Number:
  US10/801,968
• Publication Number:
  US 20050210383A1
• Time in Patent Office: 1,239 Days
• Field of Search: 715/533, 715/532, 707/3, 707/5
• US Class Current: 715/257
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/9532 Query formulation
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation

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 for spell checking 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 for 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.

Claims

1. A system comprising a computer readable storage having computer readable instructions stored thereon, when executed causes a computer to facilitate 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, the spell checking component employs an iterative process where alternative spellings for potentially misspelled stop words in the substring are identified in an iteration after the iteration where alternative spellings for potentially misspelled words that are not stop words in the same substring are identified, wherein a Viterbi search is employed 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.

2. The system of claim 1, the spell checking component further utilizes user-dependent information in proposing at least one alternative spelling.

3. The system of claim 1, the alternative spelling for the substring set is further based on at least one trusted lexicon.

4. The system of claim 3, the spell checking component further employs a list of stop words.

5. The system of claim 4, the list of stop words containing high frequency words and function words and their frequent misspellings.

6. The system of claim 4, the spell checking component employs an iterative process to search a space of alternative spellings.

7. The system of claim 6, the spell checking component employs, at least in part, heuristics to impose restrictions on a search space utilized to determine a proposed alternative spelling.

8. The system of claim 7, the heuristics utilize, at least in part, at least one fringe to limit the search space.

9. The system of claim 4, the query log comprising a histogram of queries asked over a time frame.

10. The system of claim 9, the histogram of asked queries relates to a subset of the users;

the subset comprising at least one user.

11. The system of claim 9, the query log resides on a server computer.

12. The system of claim 9, the query log resides on a client computer.

13. The system of claim 1, a substring comprising at least one selected from a group consisting of an entry in at least one trusted lexicon, an entry in a stop word list, and a sequence of characters without a pre-defined set of delimiter characters.

14. The system of claim 1, a substring bigram comprising a pair of substrings in a text.

15. The system of claim 14, the substring bigram comprising a pair of adjacent substrings in a text.

16. The system of claim 1, the spell checking component utilizes substring occurrence and co-occurrence statistics from the at least one query log, the substring co-occurrence statistics comprising substring bigram counts with stop-word-sequence-skipping counts, the substring occurrence and co-occurrence statistics from the query log are stored in a same searchable data structure.

17. The system of claim 16, the data structure comprising a trie.

18. The system of claim 17, handles concatenated and/or split substrings in a same manner as it handles individual substrings.

19. The system of claim 18, the spell checking component generates 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.

20. The system of claim 19, the set of alternative spellings comprising a set of alternative spellings determined via an iterative correction process.

21. The system of claim 20, the iterative correction process comprising a plurality of iterations that change at least one substring to another substring as an alternative spelling;

the iterative correction process halts when all possible alternative spellings are less appropriate than a current set of alternative spellings.

22. The system of claim 21, the alternative spellings and their appropriateness are computed based on a probabilistic string distance and a statistical context model.

23. The system of claim 22, the probabilistic string distance comprising a modified context-dependent weighted Damerau-Levenshtein edit function that allows insertion, deletion, substitution, transposition, and long-distance movement of characters as point changes.

24. The system of claim 22, in each iteration, the set of alternative spellings for a substring is generated utilizing a searchable substring data structure extracted from at least one query log and at least one trusted lexicon.

25. The system of claim 24, in each iteration, the set of alternative spellings for each substring is restricted to within a probabilistic distance δ

from an input substring;

the restriction is imposed within each iteration without limiting the iterative correction process as a whole.

26. The system of claim 25, in each iteration, the iterative correction process searches for an optimum set of alternative spellings via utilization of a statistical context model.

27. The system of claim 26, the statistical context model comprising substring occurrence and co-occurrence statistics extracted from at least one query log.

28. The system of claim 27, a Viterbi search is employed to facilitate in determining the optimum set of alternative spellings according to the context model in each iteration.

29. The system of claim 28, 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.

36. A device employing the system of claim 1 comprising at least one a computer, a server, and a handheld electronic device.

30. A method of facilitating spell checking, comprising:

receiving input data containing text;

identifying a set of potentially misspelled substrings in the text;

generating a set of alternative spellings that are substrings in at least one selected from the group consisting of at least one query log comprising data utilized by users to query a data collection over a time frame and at least one lexicon, the set of alternative spellings comprising a set of alternative spellings determined via an iterative correction process that includes 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 the at least one query log, the iterative correction process includes identifying alternative spellings for potentially misspelled stop words in the substrings in an iteration after an iteration identifying alternative spellings for potentially misspelled words that are not stop words in the same substrings;

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; and

proposing at least one alternative spelling for the substring set.

31. The method of claim 30, further comprising:

employing, at least in part, a list of stop words to facilitate in determining at least one alternative spelling;

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; and

handling concatenated and/or split substrings in a same manner as handling individual substrings.

32. The method of claim 31, 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.

33. The method of claim 32, 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; and

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.

35. A device employing the method of claim 30 comprising at least one of a computer, a server, and a handheld electronic device.

34. A system comprising a computer readable storage having computer readable instructions stored thereon, when executed causes a computer to facilitate 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 means employing an iterative process that identifies alternative spellings for potentially misspelled stop words in the substrings in an iteration after an iteration identifies alternative spellings for potentially misspelled words that are not stop words in the same substrings, and the means 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.