Systems and methods for spell correction of non-roman characters and words

• US 20050289463A1
• Filed: 06/23/2004
• Published: 12/29/2005
• Est. Priority Date: 06/23/2004
• Status: Abandoned Application

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Chan, Chiu-Ki, Huang, Wei-Hwa, Wu, Jun, Zhu, Huican, Zhu, Hongjun
• Application Number:
  US10/875,449
• Publication Number:
  US 20050289463A1
• Time in Patent Office: Days
• US Class Current: 715/257
• CPC Class Codes: G06F 40/129 Handling non-Latin characters, e.g. kana-to-kanji conversion
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation

Abstract

Systems and methods to process and correct spelling errors for non-Roman based words such as in Chinese, Japanese, and Korean languages using a rule-based classifier and a hidden Markov model are disclosed. The method generally includes converting an input entry in a first language such as Chinese to at least one intermediate entry in an intermediate representation, such as pinyin, different from the first language, converting the intermediate entry to at least one possible alternative spelling or form of the input in the first language, and determining that the input entry is either a correct or questionable input entry when a match between the input entry and all possible alternative spellings to the input entry is or is not located, respectively. The questionable input entry may be classified using, for example, a transformation rule based classifier based on transformation rules generated by a transformation rules generator.

Claims

1. A method, comprising:

receiving an input entry in a first language;

converting the input entry to at least one intermediate entry in an intermediate representation different from the first language;

converting the intermediate entry to at least one possible alternative form of the input entry in the first language;

comparing the input entry to at least one possible alternative form of the input entry to locate a match; and

determining that the input entry is a questionable input entry based on the comparing.

2. The method of claim 1, wherein:

the intermediate entry is converted to more than one possible alternative forms of the input entry in the first language,

the comparing includes comparing the input entry to each possible alternative of the input entry in the first language, and

the determining includes determining that the input entry is a questionable input entry if a match is not located from all the possible alternative forms and that the input entry is a correct input entry if a match is located.

3. The method of claim 1, wherein the first language is a non-Roman based language.

4. The method of claim 1, wherein the first language is Chinese and the intermediate representation is pinyin.

5. The method of claim 1, wherein the input entry is a user query in a query log.

6. The method of claim 1, wherein the receiving includes receiving a plurality of input entries.

7. The method of claim 1, further comprising:

classifying the questionable entry as one of a correctly spelled entry and an incorrectly spelled entry based on a set of rules.

8. The method of claim 7, wherein the classifying is performed by a transformation rule based classifier.

9. The method of claim 7, wherein the rules are spell correction transformation rules, further comprising:

generating and training the spell correction transformation rules using a transformation rules generator using the questionable input entry and the at least one possible alternative form.

10. The method of claim 9, wherein the generating and training the spell correction transformation rules is performed automatically using a database of questionable input entries.

11. The method of claim 7, wherein the classifying is performed at least one of automatically and with manual monitoring.

12. The method of claim 7, further comprising:

receiving a user input in the first language;

determining whether any of the rules apply to the user input;

generating at least one alternate form in the first language corresponding to the user input upon determining that at least one rule applies to the user input;

comparing a likelihood of the user input with a likelihood of at least one alternate form of the user input; and

making at least one of a spell correction suggestion and a spell correction with at least one alternate form of the user input that has a higher likelihood than the user input.

13. The method of claim 12, further comprising:

maintaining a user-editable table of stop rule patterns that disallow the making of a spell correction suggestion or a spell correction for certain specified combinations of user input and alternate spelling.

14. A system, comprising:

a first converter configured to convert the input in a first language to at least one intermediate entry in an intermediate representation different from the first language;

a second converter configured to convert the intermediate entry to at least one possible alternative spelling of the input in the first language; and

a comparator configured to compare the input entry to at least one possible alternative spelling to locate a match, the comparator further being configured to determine whether the input entry is a questionable input entry based on the comparing.

15. The system of claim 14, wherein:

the second converter is configured to convert the intermediate entry to more than one possible alternative forms of the input entry in the first language,

the comparator is configured to compare the input entry to each of the at least one possible alternative of the input entry in the first language and to determining that the input entry is a questionable input entry if a match is not located from all the possible alternative forms and that the input entry is a correct input entry if a match is located.

16. The system of claim 14, wherein the first language is a non-Roman based language.

17. The system of claim 14, wherein the first language is Chinese and the intermediate representation is pinyin.

18. The system of claim 14, wherein the input entry is a user query in a query log.

19. The system of claim 14, further comprising:

a classifier configured to classify the questionable entry as one of correctly spelled entry and incorrectly spelled entry based on a set of rules.

20. The system of claim 19, wherein the classifier is a transformation rule based classifier.

21. The system of claim 19, wherein the rules of the classifier are spell correction transformation rules, the classifier further including a transformation rules generator for generating the spell correction transformation rules using the questionable input entry and the at least one possible alternative spelling of the input in the first language.

22. The system of claim 21, wherein the transformation rules generator generates the transformation rules automatically using a database of questionable input entries.

23. The system of claim 19, wherein the classifier performs at least one of automatically and with manual monitoring.

24. The system of claim 19, further comprising:

detector configured to determine whether any of the rules apply to a user input;

generator configured to generate at least one alternate spelling of the user input in the first language upon determining that at least one rule applies to the user input;

comparator configured to compare a likelihood of the user input with a likelihood of at least one alternate spelling of the user input; and

corrector configured to make at least one of a spell correction suggestion and a spell correction with at least one alternate spelling of the user input that has a higher likelihood than the user input.

25. The system of claim 24, further comprising:

customizable stop rule pattern table that disallows the corrector from making a spell correction suggestion or a spell correction for certain specified combinations of user input and alternate spelling.

26. A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium on which are stored instructions executable on a computer processor, the instructions including:

receiving an input entry in a first language;

converting the input entry to at least one intermediate entry in an intermediate representation different from the first language;

converting the intermediate entry to at least one possible alternative form of the input entry in the first language;

comparing the input entry to at least one possible alternative form of the input entry to locate a match; and

determining that the input entry is a questionable input entry based on the comparing.

27. The computer program product of claim 26, wherein:

the intermediate entry is converted to more than one possible alternative forms of the input entry in the first language,

the comparing includes comparing the input entry to each possible alternative of the input entry in the first language, and

the determining includes determining that the input entry is a questionable input entry if a match is not located from all the possible alternative forms and that the input entry is a correct input entry if a match is located.

28. The computer program product of claim 26, wherein the first language is a non-Roman based language.

29. The computer program product of claim 26, wherein the first language is Chinese and the intermediate representation is pinyin.

30. The computer program product of claim 26, wherein the input entry is a user query in a query log.

31. The computer program product of claim 26, wherein the receiving includes receiving a plurality of input entries.

32. The computer program product of claim 26, wherein the computer program product is implemented at a client site in a toolbar.

33. The computer program product of claim 26, the instructions further including:

classifying the questionable entry as one of correctly spelled and incorrectly spelled based on a set of rules.

34. The computer program product of claim 33, wherein the classifying is a transformation rule based classification.

35. The computer program product of claim 33, wherein the rules are spell correction transformation rules, the instructions further including:

generating and training the spell correction transformation rules using a transformation rules generator using the questionable input entry and the at least one possible alternative form.

36. The computer program product of claim 35, wherein the spell correction transformation rules are generated automatically using a database of questionable input entries.

37. The computer program product of claim 33, wherein the classifying is performed at least one of automatically and with manual monitoring.

38. The computer program product of claim 33, the instructions further including:

receiving a user input in the first language;

determining whether any of the rules apply to the user input;

generating at least one alternate form in the first language corresponding to the user input upon determining that at least one rule applies to the user input;

comparing a likelihood of the user input with a likelihood of at least one alternate form of the user input; and

making at least one of a spell correction suggestion and a spell correction with at least one alternate form of the user input that has a higher likelihood than the user input.

39. The computer program product of claim 38, the instructions further including:

maintaining a user-editable table of stop rule patterns that disallow the making of a spell correction suggestion or a spell correction for certain specified combinations of user input and alternate form.