Spell checking system including a phonetic speller

• US 20070213983A1
• Filed: 03/08/2006
• Published: 09/13/2007
• Est. Priority Date: 03/08/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ramsey, William
• Granted Patent: US 7,831,911 B2
• Time in Patent Office: Days
• US Class Current: 704/254
• 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 suggesting replacement target strings for a misspelled source string, the computer-implemented method comprising:

selecting a plurality of candidate phoneme target strings that closely match the misspelled source string;

selecting a plurality of candidate letter target strings that closely match the misspelled source string; and

combining the candidate phoneme target strings and the candidate letter target strings to provide a list of candidate target strings for replacing the misspelled source string.

2. The computer-implemented method of claim 1, wherein selecting the plurality of candidate phoneme target strings comprises converting the misspelled source string into a source phoneme sequence string using a letter-to-sound system.

3. The computer-implemented method of claim 2, wherein selecting the plurality of candidate phoneme target strings further comprises traversing phoneme-based trie structures to select candidate phoneme target-strings, wherein the candidate phoneme target strings are those phoneme target strings which were found using a minimal number of edit operations.

4. The computer-implemented method of claim 3, wherein the phoneme-based trie structures are derived from a lexicon.

8. The computer-implemented method of claim 1, further comprising ranking the list of candidate target strings to provide best candidate target strings based on the rank.

9. The computer-implemented method of claim 8, wherein ranking the list of candidate target strings comprises summating, for each candidate target string, a number of edit operations of a corresponding candidate phoneme target string and a number of edit operations of a corresponding candidate letter target string to find a combined score.

10. The computer-implemented method of claim 9, wherein summating further comprises augmenting the number of edit operations of the candidate phoneme target string in the combined score with an adjustable weight.

11. The computer-implemented method of claim 8, wherein ranking the list of candidate target strings comprises scoring each candidate target string based on types of edit operations, wherein statistically frequently performed edits are given higher scores than statistically infrequently performed edits.

12. The computer-implemented method of claim 8, wherein ranking the list of candidate target strings comprises one of summating, for each candidate target string, a number of edit operations of a corresponding candidate phoneme target string and a number of edit operations of a corresponding candidate letter target string to find a combined score and scoring each candidate target string based on types of edit operations, wherein statistically frequently performed edits are given higher scores than statistically infrequently performed edits.

13. The computer-implemented method of claim 12, further comprising augmenting the combined score of each candidate target string by multiplying the combined score by a contextual score, the contextual score being derived by utilizing words on either side of the source string to disambiguate the source string.

5. The computer-implemented method of 1, wherein selecting the plurality of candidate letter target strings further comprises parsing the source string to obtain a source letter sequence string.

6. The computer-implemented method of claim 5, wherein selecting the plurality of candidate letter target strings comprises traversing letter-based trie structures to select candidate letter target strings, wherein the candidate letter target strings are those letter target strings which were found using a minimal number of edit operations.

7. The computer-implemented method of claim 6, wherein the letter-based trie structures are derived from a lexicon.

14. A spell checking system comprising:

a letter spelling engine configured to select a plurality of candidate letter target strings that closely match a misspelled source string;

a phoneme spelling engine configured to select a plurality of candidate phoneme target strings that closely match the misspelled source string; and

a ranker module configured to combine the candidate letter target strings and the candidate phoneme target strings into a combined list of candidate target strings and configured to rank the list of candidate target strings to provide a list of best candidate target strings for the misspelled source string.

15. The spell checking system of claim 14, wherein the phoneme spelling engine is configured to traverse phoneme-based trie structures derived from a lexicon.

16. The spell checking system of claim 14, wherein the letter spelling engine is configured to traverse letter-based trie structures derived from a lexicon.

17. The spell checking system of claim 14, wherein the phoneme spelling engine comprises a letter-to-sound system for converting the misspelled source string into a source phoneme sequence string.

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

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

traversing phoneme-based trie structures to select a plurality of candidate phoneme target strings, wherein the candidate phoneme target strings are those phoneme target strings which were selected based on a minimal number of edit operations.

19. The computer-implemented method of claim 18, further comprising:

parsing the misspelled letter source string into a source letter sequence string; and

traversing letter-based trie structures to select a plurality of candidate letter target strings, wherein the candidate letter target strings are those letter target strings which were selected base on a minimal number of edit operations.

20. The computer implemented method of claim 19, further comprising:

combining the candidate phoneme target strings and the candidate letter target strings to provide a list of candidate target strings for replacing the misspelled source string; and

ranking the list of candidate target strings to provide best candidate target strings based on the rank.