Self learning contextual spell corrector

• US 8,176,419 B2
• Filed: 12/19/2007
• Issued: 05/08/2012
• Est. Priority Date: 12/19/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhu, Weibin, Xu, Haiyun, Wang, Mingyu, Rong, Li
• Primary Examiner(s): HUYNH, CONG LAC T
• Application Number:
  US11/959,946
• Publication Number:
  US 20090164890A1
• Time in Patent Office: 1,602 Days
• Field of Search: 715/257
• US Class Current: 715/257
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation

Abstract

A group of keywords are received, wherein each keyword includes one or more words. A word list is formed from the group of keywords, where the word list includes a list of each word in the group of keywords. A misspelled keyword is corrected using analysis of the words in the word list. The corrected keyword is output.

Claims

1. A computer-implemented method comprising:

receiving a group of keywords, wherein each keyword includes one or more words;

forming a word list from the group of keywords, where the word list includes a list of each word in the group of keywords;

determining that a first word in the word list is a misspelling of a second word in the word list by;

determining correct spelling candidate words in the word list;

computing misspelling confidence scores for correcting the first word to the correct spelling candidate words; and

in at least one instance, choosing, as the second word, an individual correct spelling candidate word having a misspelling confidence score that exceeds a misspelling confidence score threshold and that has a highest misspelling confidence score;

correcting the first word by spelling the first word like the second word; and

outputting corrected keywords that include the corrected first word.

2. The method of claim 1, further comprising

determining that another word in the word list is a combination of at least two other words in the word list;

and

correcting the another word by separating the another word into the at least two other words.

3. The method of claim 2 further comprising:

finding matching words in the word list that match a portion of the another word; and

computing connection confidence scores for the matching words;

wherein the determining that the another word is a combination of the at least two other words is based on the connection confidence scores.

4. One or more computer-readable storage devices storing computer-readable instructions that, when executed by a processing unit, cause the processing unit to perform the method of claim 1.

5. A system comprising the one or more computer-readable storage devices of claim 4 and the processing unit.

6. The method of claim 1, wherein the misspelling confidence scores reflect spatial edit distances between the correct spelling candidate words and the first word.

7. A computer-implemented method comprising:

receiving a group of keywords, wherein each keyword includes one or more words;

forming a word list from the group of keywords, where the word list includes a list of each word in the group of keywords;

determining that a first word in the word list is a portion of a second word in the word list by;

combining the first word with other words in the word list to form combination candidate words;

computing separation confidence scores for the combination candidate words; and

in at least one instance, choosing, as the second word, an individual combination candidate word having a separation confidence score that exceeds a separation confidence score threshold and that has a highest separation confidence score;

correcting the first word by spelling the first word like the second word; and

outputting corrected keywords that include the corrected first word.

8. The method of claim 7, further comprising:

breaking the group of keywords into the one or more words to form the word list; and

counting a frequency of each word in the word list.

9. The method of claim 8, further comprising:

sorting the words in the word list by frequency.

10. The method of claim 7 wherein the group of keywords includes an order, wherein the keywords include bidding keywords for an online advertising system.

11. One or more computer-readable storage devices storing computer-readable instructions that, when executed by a processing unit, cause the processing unit to perform the method of claim 7.

12. A system comprising the one or more computer-readable storage devices of claim 11 and the processing unit.

13. A computer-implemented method comprising:

receiving an order including keywords for an online advertising system, wherein individual keywords include at least two words comprising a first word and a second word;

breaking the keywords into the at least two words;

forming a word list from the at least two words by sorting the at least two words decreasingly by frequency of occurrence in the order;

determining that correcting the first word to the second word meets misspelling candidate criteria, the misspelling candidate criteria including;

a frequency of occurrence of the second word is higher than a frequency of occurrence of the first word,

stemming forms of the first word and the second word are not the same,

an edit distance from the first word to the second word is less than a first threshold,

a ratio of the length of the first word to the edit distance is larger than or equal to a second threshold, and

the frequency of occurrence of the first word is less than a third threshold;

in an instance when the misspelling candidate criteria are met, computing a misspelling confidence score and correcting spelling of the first word using the second word when the misspelling confidence score exceeds a fourth threshold; and

outputting corrected keywords that include the corrected first word.

14. The method of claim 13, further comprising:

determining that a another word in the word list is a combination of at least two other words in the word list that are sub-words of the another word; and

correcting the another word by separating the another word into the at least two other words.

15. The method of claim 14 further comprising identifying a first one of the sub-words when:

an edit distance between the first sub-word and a portion of the another word is not greater than a fifth threshold, and

a ratio of the edit distance to a sub-word length of the first sub-word is less than or equal to a sixth threshold.

16. The method of claim 13, further comprising:

determining that a third word in the word list is a sub-word of fourth word in the word list; and

correcting the third word by spelling the third word like the fourth word.

17. One or more computer-readable storage devices storing computer-readable instructions that, when executed by a processing unit, cause the processing unit to perform the method of claim 13.

18. A system comprising the one or more computer-readable storage devices of claim 17 and the processing unit.