Spell checking system including a phonetic speller

• US 7,831,911 B2
• Filed: 03/08/2006
• Issued: 11/09/2010
• Est. Priority Date: 03/08/2006
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ramsey, William D.
• Primary Examiner(s): Hong; Stephen S
• Assistant Examiner(s): SCOTT, MICHAEL E
• Application Number:
  US11/370,816
• Publication Number:
  US 20070213983A1
• Time in Patent Office: 1,707 Days
• Field of Search: 715/257, 715/255, 715/256, 715/259, 715/271, 704/254, 704/E15.02, 704/E19.007, 704/E13.001
• US Class Current: 715/257
• CPC Class Codes: G10L 15/187 Phonemic context, e.g. pronunciation rules, phonotactical constraints or phoneme n-grams
• CPC Class Codes: G10L 15/22 Procedures used during a speech recognition process, e.g. man-machine dialogue

Abstract

A spell checking system includes a letter spelling engine. The letter spelling engine is configured to select a plurality of candidate letter target strings that closely match a misspelled source string. The spell checking system includes a phoneme spelling engine. The phoneme spelling engine is configured to select a plurality of candidate phoneme target strings that closely match the misspelled source string. A ranker module is configured to combine the candidate letter target strings and the candidate phoneme target strings into a combined list of candidate target strings. The ranker module is also configured to rank the list of candidate target strings to provide a list of best candidate target strings for the misspelled source string.

Claims

1. A computer-implemented method of ranking replacement target strings for a misspelled source string, the computer-implemented method comprising:

converting the misspelled source string into a source phoneme sequence using a letter-to-sound system;

utilizing a computer processor that is a component of the computer to traverse at least one phoneme-based trie structure so as to select a plurality of different candidate phoneme sequences based on a comparison of phonemes in the phoneme-based trie structure to the source phoneme sequence but without doing a direct comparison of every component of the plurality of different candidate phoneme sequences to a component of the source phoneme sequence;

generating a count for each different candidate phoneme sequence in said plurality of different candidate phoneme sequences, the count being indicative of a quantity of edit operations required to transform the candidate phoneme sequence into the source phoneme sequence;

utilizing the computer processor to select a limited number of the plurality of different candidate phoneme sequences based at least in part on said counts, the limited number being less than all of the different candidate phoneme sequences included in said plurality of different candidate phoneme sequences;

utilizing the computer processor to select a first set of replacement target strings, each replacement target string in the first set being selected based on direct correspondence to a candidate phoneme sequences in said limited number of different candidate phoneme sequences;

utilizing the computer processor to traverse at least one letter-based trie structure so as to select a plurality of different candidate letter sequences, wherein selecting the plurality of different candidate letter sequences comprises traversing the letter-based trie structure so as to identify the plurality of different candidate letter sequences without doing a direct comparison of every component of the plurality of different candidate letter sequences with every component of the misspelled source string;

utilizing the computer processor to select a limited number of the plurality of different candidate letter sequences based at least in part on a count of a quantity of edit operations required to transform each different candidate letter sequence included in the limited number of different candidate letter sequences into the misspelled source string, the limited number of different candidate letter sequences being less than all of the different candidate letter sequences included in said plurality of different candidate letter sequences;

utilizing the computer processor to select a second set of replacement target strings, each replacement target string in the second set being one of the candidate letter sequences in said limited number of the plurality of different candidate letter sequences; and

utilizing the computer processor to rank the replacement strings in the first and/or second sets based on a summation of the count of the quantity of edit operations required to transform a particular different candidate phoneme sequence included in the limited number of the plurality of different candidate phoneme sequences into the source phoneme sequence plus the count of the quantity of edit operations required to transform a particular different candidate letter sequence included in the limited number of the plurality of different candidate letter sequences into the misspelled source string.

2. The computer-implemented method of claim 1, wherein the phoneme-based trie structure is derived from a lexicon that includes the first and second sets of replacement target strings.

4. The computer-implemented method of claim 1, wherein the letter-based trie structure is derived from a lexicon that includes the first and second sets of replacement target strings.

5. The computer-implemented method of claim 1, wherein said summation is augmented so as to apply an adjustable weight to at least one of the operations in the count of the quantity of operations required to transform the particular different candidate phoneme sequence included in the limited number of different candidate phoneme sequences into the source phoneme sequence or the operations in the count of the quantity of operations required to transform the particular different candidate letter string included in the limited number of different candidate letter sequences into the misspelled source string.

6. The computer-implemented method of claim 1, wherein said step of ranking the replacement strings in the first and/or second sets comprises ranking so as to account for assignment of a weighted bias scheme in which a weighted bias is assigned to some edit operations included in the count of the quantity of operations required to transform the particular different candidate phoneme sequence included in the limited number of different candidate phoneme sequences into the source phoneme sequence.

7. The method of claim 6, wherein said weighted bias scheme is based on types of edit operations, wherein statistically frequently performed edits are given a higher weighted bias than statistically infrequently performed edits.

8. The computer-implemented method of claim 1, wherein said step of ranking the replacement strings comprises summating, for each unique instance of a replacement string in the first and second sets, the count of the quantity of edit operations required to transform the candidate phoneme sequence included in the limited number of different candidate phoneme sequences into the source phoneme sequence plus the count of the quantity of edit operations required to transform the candidate letter string included in the limited number of different candidate letter sequences into the misspelled source string.

9. The computer-implemented method of claim 8, further comprising augmenting the summated value for each unique instance of a replacement string in the first and second sets by multiplying the summated value by a contextual score, the contextual score being derived by a formula that factors in words on either side of the misspelled source string.

10. The method of claim 8, wherein summating the quantity of edit operations required to transform the different candidate phoneme sequence plus the quantity of edit operations required to transform the different candidate letter string further comprises applying a weighting scheme so as to statistically favor frequently performed edits over infrequently performed edits.

11. The method of claim 1, wherein said particular different candidate phoneme sequence and said particular different candidate letter sequence correspond to a common replacement string, the common replacement string being included in both the first and second sets of replacement target strings.

12. The computer-implemented method of claim 1, wherein said step of ranking the replacement strings in the first and/or second sets comprises ranking so as to account for assignment of a weighted bias scheme wherein a weighted bias is assigned to favor some edit operations required to transform a particular different candidate letter string included in the limited number of different candidate letter sequences into the misspelled source string over others.

3. The computer-implemented method of 1, wherein selecting the plurality of different candidate letter sequences comprises parsing the misspelled source string to obtain a source letter sequence string.

13. A computer-implemented spell checking system for ranking replacement target strings for a misspelled source string, the computer-implemented method comprising:

a phoneme spelling engine that selects sets of the replacement target strings for ranking by;

converting the misspelled source string into a source phoneme sequence using a letter-to-sound system;

utilizing a computer processor that is a component of the computer to traverse at least one phoneme-based trie structure so as to select a plurality of different candidate phoneme sequences based on a comparison of phonemes in the phoneme-based trie structure to the source phoneme sequence but without doing a direct comparison of every component of the plurality of different candidate phoneme sequences to a component of the source phoneme sequence;

generating a count for each different candidate phoneme sequence in said plurality of different candidate phoneme sequences, the count being indicative of a quantity of edit operations required to transform the candidate phoneme sequence into the source phoneme sequence;

utilizing the computer processor to select a limited number of the plurality of different candidate phoneme sequences based at least in part on said counts, the limited number being less than all of the different candidate phoneme sequences included in said plurality of different candidate phoneme sequences;

utilizing the computer processor to select a first set of replacement target strings, each replacement target string in the first set being selected based on direct correspondence to candidate phoneme sequences in said limited number of different candidate phoneme sequences;

a letter spell checking engine that utilizes the computer processor to select the replacement target strings that closely match the misspelled source target string by;

utilizing the computer processor to traverse at least one letter-based trie structure so as to select a plurality of different candidate letter sequences, wherein selecting the plurality of different candidate letter sequences comprises traversing the letter-based trie structure so as to identify the plurality of different candidate letter sequences without doing a direct comparison of every component of the plurality of different candidate letter sequences with every component of the misspelled source string;

utilizing the computer processor to select a limited number of the plurality of different candidate letter sequences based at least in part on a count of a quantity of edit operations required to transform each different candidate letter sequence included in the limited number of different candidate letter sequences into the misspelled source string, the limited number of different candidate letter sequences being less than all of the different candidate letter sequences included in said plurality of different candidate letter sequences;

utilizing the computer processor to select a second set of replacement target strings, each replacement target string in the second set being one of the candidate letter sequences in said limited number of the plurality of different candidate letter sequences; and

a ranker module utilizing the computer processor to rank the replacement strings in the first and/or second sets based on a summation of the count of the quantity of edit operations required to transform a particular different candidate phoneme sequence included in the limited number of the plurality of different candidate phoneme sequences into the source phoneme sequence plus the count of the quantity of edit operations required to transform a particular different candidate letter sequence included in the limited number of the plurality of different candidate letter sequences into the misspelled source string.

14. The spell checking system of claim 13, wherein the phoneme spelling engine traverses phoneme-based trie structures derived from a lexicon.

15. The spell checking system of claim 13, wherein the letter spelling engine traverses letter-based trie structures derived from a lexicon.