SPELLING CORRECTION SYSTEM AND METHOD FOR MISSPELLED INPUT

• US 20090254819A1
• Filed: 04/07/2009
• Published: 10/08/2009
• Est. Priority Date: 04/07/2008
• Status: Active Grant

• Current Assignee: Knu-Industry Cooperation Foundation, Samsung Electronics Co. Ltd.
• Original Assignee: Knu-Industry Cooperation Foundation, Samsung Electronics Co. Ltd.
• Inventors: Lee, Se Hee, Lee, Joo Ho, Kim, Hark Soo, Ham, Jong Gyu, SONG, Hee jun, Park, Young Hee, Shim, Hyun Sik
• Granted Patent: US 8,365,070 B2
• Time in Patent Office: Days
• US Class Current: 715/257
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06F 40/242 Dictionaries

Abstract

A spelling correction system and method automatically recognizes and corrects misspelled inputs in an electronic device with relatively lower computing power. In a learning process, a misspelling correction dictionary is constructed on the basis of a corpus of accepted words, and context-sensitive strings are selected from among all the strings registered in the dictionary. Context information about the context-sensitive strings is acquired. In an applying process, at least one target string is selected from among all the strings in a user'"'"'s input sentence through the dictionary. If the target string is one of the context-sensitive strings, the target string is corrected by use of the context information.

Claims

1. A spelling correction method for an electronic device comprising:

(a) selecting context-sensitive strings, which have different meanings according to context, from among all strings registered in a misspelling correction dictionary stored in a memory on the basis of a corpus of accepted words;

(b) acquiring context information about the context-sensitive strings;

(c) receiving a user'"'"'s input sentence by the electronic device;

(d) selecting at least one target string from among all strings in the user'"'"'s input sentence through the misspelling correction dictionary; and

(e) if the target string is one of the context-sensitive strings, correcting the target string by using the context information.

2. The method of claim 1, further comprising:

after the correcting of the target string in (e), correcting a postposition in connection with the corrected target string.

3. The method of claim 1, wherein the corpus of accepted words includes existing lexicons, vocabularies and dictionaries.

4. The method of claim 1, wherein the misspelling correction dictionary includes an incorrect string field used for recording incorrect strings, a correct string field used for recording correct strings from which spelling errors are removed, and a part-of-speech field used for recording parts of speech in connection with the incorrect strings or the correct strings.

5. The method of claim 1, wherein the misspelling correction dictionary is stored in the memory after being converted into a syllable tree data (TRIE) structure or an alphabet TRIE structure.

6. The method of claim 4, wherein the selecting of the context-sensitive strings includes selecting the incorrect string from the misspelling correction dictionary, and assigning the selected incorrect string to the context-sensitive string when the selected incorrect string is found once or more in a corpus of learning words.

7. The method of claim 1, wherein the acquiring of the context information about the context-sensitive strings includes obtaining the frequency the context-sensitive string is found in a corpus of learning words.

8. The method of claim 7, wherein the acquiring of the context information about the context-sensitive strings further includes obtaining context information about strings corresponding to the context-sensitive strings.

9. The method of claim 1, wherein the context information includes a frequency f(W_before) a string W_before is found in the corpus of learning words, a frequency f(w₋

1,W_all,w₊₁) a string w<sub>−

1</sub>W_allw₊₁ is found, a frequency f(w<sub>−

1</sub>,W_all) a string w<sub>−

1</sub>W_all is found, a frequency f(W_all,w₊₁) a string W_allw₊₁ is found, a frequency f(c<sub>−

1</sub>,W_all,c₊₁) a string W_all is found between categories c<sub>−

1</sub> and c₊₁, a frequency f(c<sub>−

1</sub>,W_all) a string W_all is found after a category c<sub>−

1</sub>, and a frequency f(W_all,c₊₁) a string W_all is found before a category c₊₁, where a string W_all includes the string W_before before corrected and a string W_after after corrected, where characters w<sub>−

1</sub> and w₊₁ mean respectively a syllable located just before the string W_all and a syllable located just after the string W_all, and where characters c<sub>−

1</sub> and c₊₁ mean respectively categories to which the syllables w<sub>−

1</sub> and w₊₁ belongs.

10. The method of claim 9, wherein the categories include a kind of language, a number, a special character, an auxiliary inflectional word, a suffix, a postposition, and a verb ending.

11. The method of claim 9, wherein the correcting of the target string includes calculating a context score of the target string by using the context information about the target string, and replacing the target string with a string having a highest context score.

12. The method of claim 11, wherein the context score is calculated through a following Equation:

$P<br><br>\left(W_{\mathrm{before}}|w_{-1},W_{\mathrm{all}},w_{+1}\right)\approx <br><br>\mathrm{\alpha <br><br>}<br><br>\frac{f<br><br>\left(W_{\mathrm{before}}\right)}{f<br><br>\left(w_{-1},W_{\mathrm{all}},w_{+1}\right)}+\mathrm{\beta <br><br>}<br><br>\frac{f<br><br>\left(W_{\mathrm{before}}\right)}{f<br><br>\left(w_{-1},W_{\mathrm{all}}\right)+f<br><br>\left(W_{\mathrm{all}},w_{+1}\right)}+\mathrm{\gamma <br><br>}<br><br>\frac{f<br><br>\left(W_{\mathrm{before}}\right)}{f<br><br>\left(c_{-1},W_{\mathrm{all}},c_{+1}\right)}+\mathrm{\delta <br><br>}<br><br>\frac{f<br><br>\left(W_{\mathrm{before}}\right)}{f<br><br>\left(c_{-1},W_{\mathrm{all}}\right)+f<br><br>\left(W_{\mathrm{all}},c_{+1}\right)}$

wherein P(W_before|w<sub>−

1</sub>,W_all,w₊₁) is the context score and α

, β

, γ and

δ

are weight parameters.

13. The method of claim 2, wherein the correcting of a postposition includes determining whether the corrected target string is a substantive, further determining whether there is a final consonant in each last syllable of the target string and the corrected target string, and replacing the postposition with the counterpart when only one of the target string and the corrected target string has a final consonant.

14. The method of claim 13, wherein the replacing of the postposition includes specifying the postposition following the corrected target string, extracting the counterpart of the specified postposition, calculating the respective context scores of the specified postposition and the counterpart, and comparing the calculated context scores with each other.

15. A spelling correction system of an electronic device comprising:

a dictionary constructing unit for constructing a misspelling correction dictionary on a basis of a corpus of accepted words;

an information extracting unit for selecting context-sensitive strings, which have different meanings according to context, from among all strings registered in the misspelling correction dictionary, and for acquiring context information about the selected context-sensitive strings;

an input unit receiving a user'"'"'s input sentence; and

a string correction unit for selecting at least one target string from among all strings in the user'"'"'s input sentence through the misspelling correction dictionary, and, if the target string is one of the context-sensitive strings, for correcting the target string by using the context information.

16. The system of claim 15, further comprising:

a postposition correction unit for correcting a postposition in connection with the corrected target string.

17. The system of claim 15, wherein the misspelling correction dictionary further includes an incorrect string field means for recording incorrect strings, a correct string field means for recording correct strings from which spelling errors are removed, and a part-of-speech field means for recording parts of speech in connection with the recorded incorrect strings or the correct strings.

18. The system of claim 16, wherein the dictionary constructing unit converts the misspelling correction dictionary into a syllable tree data (TRIE) structure or an alphabet TRIE structure.

19. The system of claim 15, wherein the information extracting unit selects the incorrect string from the misspelling correction dictionary, and assigns the selected incorrect string to the context-sensitive string when the selected incorrect string is found once or more in a corpus of learning words.

20. The system of claim 15, wherein the information extracting unit further acquires context information about strings corresponding to the context-sensitive strings.

21. The system of claim 15, wherein the string correction unit calculates a context score of the target string by using the context information about the target string, and replaces the target string with a string having a highest context score.

22. The system of claim 21, wherein the context information includes a frequency f(W_before) a string W_before is found in a corpus of learning words, a frequency f(w₋

1,W_all,w₊₁) a string w<sub>−

1</sub>W_allw₊₁ is found, a frequency f(w<sub>−

1</sub>,W_all) a string w<sub>−

1</sub>W_all is found, a frequency f(W_all,w₊₁) a string W_allw₊₁ is found, a frequency f(c<sub>−

1</sub>,W_all,c₊₁) a string W_all is found between categories c<sub>−

1</sub> and c₊₁, a frequency f(c<sub>−

1</sub>,W_all) a string W_all is found after a category c<sub>−

1</sub>, and a frequency f(W_all,c₊₁) a string W_all is found before a category c₊₁, where a string W_all includes the string W_before before corrected and a string W_after after corrected, where characters w<sub>−

1</sub> and w₊₁ mean respectively a syllable located just before the string W_all and a syllable located just after the string W_all, and where characters c<sub>−

1</sub> and c₊₁ mean respectively categories to which the syllables w<sub>−

1</sub> and w₊₁ belongs.

23. The system of claim 22, wherein the string correction unit calculates the context score through an Equation as follows:

$P<br><br>\left(W_{\mathrm{before}}|w_{-1},W_{\mathrm{all}},w_{+1}\right)\approx <br><br>\mathrm{\alpha <br><br>}<br><br>\frac{f<br><br>\left(W_{\mathrm{before}}\right)}{f<br><br>\left(w_{-1},W_{\mathrm{all}},w_{+1}\right)}+\mathrm{\beta <br><br>}<br><br>\frac{f<br><br>\left(W_{\mathrm{before}}\right)}{f<br><br>\left(w_{-1},W_{\mathrm{all}}\right)+f<br><br>\left(W_{\mathrm{all}},w_{+1}\right)}+\mathrm{\gamma <br><br>}<br><br>\frac{f<br><br>\left(W_{\mathrm{before}}\right)}{f<br><br>\left(c_{-1},W_{\mathrm{all}},c_{+1}\right)}+\mathrm{\delta <br><br>}<br><br>\frac{f<br><br>\left(W_{\mathrm{before}}\right)}{f<br><br>\left(c_{-1},W_{\mathrm{all}}\right)+f<br><br>\left(W_{\mathrm{all}},c_{+1}\right)}$

wherein P(W_before|w<sub>−

1</sub>,W_all,w₊₁) is the context score and α

, β

, γ and

δ

are weight parameters.

24. The system of claim 16, wherein the postposition correction unit determines whether the corrected target string is a substantive, further determines whether there is a final consonant in each last syllable of the target string and the corrected target string, and replaces the postposition with the counterpart when only one of the target string and the corrected target string has a final consonant.

25. The system of claim 16, further comprising:

a memory unit in the electronic device for storing the misspelling correction dictionary and the context information.