Language input architecture for converting one text form to another text form with tolerance to spelling typographical and conversion errors

• US 7,424,675 B2
• Filed: 09/27/2004
• Issued: 09/09/2008
• Est. Priority Date: 11/05/1999
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chen, Zheng, Han, Jian, Lee, Kai-Fu
• Primary Examiner(s): Singh; Rachna
• Assistant Examiner(s): Tran; Quoc A
• Application Number:
  US10/951,307
• Publication Number:
  US 20050044495A1
• Time in Patent Office: 1,443 Days
• Field of Search: 715/533, 715/535, 715/257, 715/260, 715/262, 715/625, 704/1, 704/9
• US Class Current: 715/262
• CPC Class Codes: G06F 40/129 Handling non-Latin characters, e.g. kana-to-kanji conversion
• CPC Class Codes: G06F 40/216 using statistical methods
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06F 40/44 Statistical methods, e.g. probability models
• CPC Class Codes: G06F 40/53 Processing of non-Latin text kana-to-kanji conversion G06F40/129; vowelisation G06F40/232

Abstract

A language input architecture converts input strings of phonetic text to an output string of language text. The language input architecture has a search engine, one or more typing models, a language model, and one or more lexicons for different languages. The typing model is configured to generate a list of probable typing candidates that may be substituted for the input string based on probabilities of how likely each of the candidate strings was incorrectly entered as the input string. The language model provides probable conversion strings for each of the typing candidates based on probabilities of how likely a probable conversion output string represents the candidate string. The search engine combines the probabilities of the typing and language models to find the most probable conversion string that represents a converted form of the input string.

Claims

1. A language input architecture, tangibly embodied on one or more computer-readable media, comprising:

a user interface to receive an input string, the input string containing a spelling error;

a typing model to automatically correct spelling errors and to determine typing candidates, each typing candidate being associated with a first probability representing how likely the typing candidate would be correctly entered as the input string, wherein the first probability is derived from data collected from multiple users entering a training text; and

a language model to determine conversion candidates associated with each of the typing candidates, each conversion candidate being associated with a second probability representing a likelihood of the conversion candidate being in context with preceding strings.

2. A language input architecture as recited in claim 1, wherein the language model comprises an N-gram statistical language model.

3. A language input architecture as recited in claim 1, wherein the spelling error is automatically corrected by the typing model and the language model without user input.

15. A method as recited in claim 1, wherein the statistical language model includes an N-gram statistical language model.

16. A method as recited in claim 1, wherein the selected conversion candidate has the highest overall probability from combining the first and second probabilities.

4. A language input architecture, tangibly embodied on one or more computer-readable media, comprising:

a typing model to receive an input string and determine a typing error probability of how likely a candidate string would be incorrectly entered as the input string, wherein the typing model is trained using data collected from multiple users entering a training text;

a language model to determine a language text probability of how likely an output string represents the candidate string; and

a search engine to selectively convert the input string to the output string based on the typing error probability and the language text probability.

5. A language input architecture as recited in claim 4, wherein the input string comprises phonetic text and the output string comprises language text.

6. A language input architecture as recited in claim 4, wherein the input string comprises Pinyin and the output string comprises Hanzi.

7. A language input architecture as recited in claim 4, wherein the input string comprises a combination of phonetic text and non-phonetic text and the output string comprises a combination of language text and the non-phonetic text.

8. A language input architecture as recited in claim 4, further comprising a user interface to receive the input string and to display the output string.

9. A language input architecture as recited in claim 4, further comprising a database to store the candidate string.

10. A language input architecture as recited in claim 4, further comprising a sentence context model for providing the typing model with text previously input in a sentence that also contains the input string, the typing model being configured to derive the typing error probability using a combination of the input string and the text in the sentence.

11. A word processor embodied on a computer-readable medium comprising the language input architecture as recited in claim 4.

12. One or more computer-readable media having computer-executable instructions that, when executed on a processor, direct a computer to:

receiving an input string;

determine typing candidates based, at least in part, on a typing model configured to automatically correct a spelling error, each typing candidate being associated with a first probability representing how likely the typing candidate would be correctly entered as the input string, wherein the first probability is associated with observed errors made during entry of training text by trainers;

determine a conversion string associated with the typing candidate based, at least in part, on a statistical language model, the conversion string being associated with a second probability of how likely the conversion string accurately represents the typing candidate based on a language context of the input string; and

convert the input string to the conversion string.

13. One or more computer-readable media having computer-executable instructions that, when executed on a processor, direct a computer to:

receive an input string;

determine typing candidate strings that may be used to replace the input string based on a first probability of how likely each typing candidate string would be correctly entered as the input string, wherein the typing candidate strings are based on a typing model that is trained on actual data collected from multiple users entering at least one training text;

use at least one of the typing candidate strings to derive an output string based on the first probability and a second probability of how likely the output string is within a context associated with previously entered strings; and

convert the input string to the output string.

14. A method for handling text input comprising:

receiving an input string having a spelling error;

determining typing candidates based, at least in part, on a typing model configured to automatically correct the spelling error, each typing candidate being associated with a first probability representing how likely the typing candidate would be correctly entered as the input string, wherein the first probability is associated with observed errors made during entry of training text by trainers;

determining conversion candidates associated with each of the typing candidates based, at least in part, on a statistical language model, each conversion candidate being associated with a second probability representing a likelihood of the conversion candidate being within a context associated with the input string;

selecting a conversion candidate from the determined conversion candidates based, at least in part, on the first probability and the second probability; and

converting the input string using the selected conversion candidate.

17. A method for handling text input comprising:

receiving an input string;

determining a typing candidate based, at least in part, on a typing model, the typing candidate being associated with a first probability of how likely the typing candidate would be correctly entered as the input string, wherein the first probability is derived from data collected from multiple users entering a training text;

determining a conversion siring associated with the typing candidate based, at least in part, on a statistical language model, the conversion string being associated with a second probability of how likely the conversion string accurately represents the typing candidate based on textual elements entered previous to the input string; and

converting the input string to the conversion string.

18. A method as recited in claim 17, wherein the input string comprises phonetic text and the conversion string comprises language text.

19. A method as recited in claim 17, wherein the input string comprises Pinyin and the conversion string comprises Hanzi.

20. A method as recited in claim 17, wherein determining the conversion string comprises obtaining the conversion string from a database.

21. A method as recited in claim 17, wherein determining the typing candidate comprises segmenting the input string multiple different ways to produce multiple typing candidates that may be used to replace the input string, each of the typing candidates being associated with a typing error probability of how likely the candidate string was correctly entered as the input string.

22. A method as recited in claim 21, further comprising determining multiple conversion strings corresponding to each of the multiple typing candidates, each of the multiple conversion strings being associated with a language text probability.

23. A method as recited in claim 22, further comprising:

converting the input string to at least one of the conversion strings selected based on the typing error probability and the language text probability associated with the at least one conversion string.

24. A method as recited in claim 17, further comprising displaying the conversion string in line with the input string being entered by a user.

25. One or more computer-readable media having computer-executable instructions that, when executed on a processor, direct a computer to perform the method as recited in claim 17.

26. A method for handling text input comprising:

segmenting an input string in multiple different ways to produce multiple typing candidates based, at least in part, on a typing model, each of the multiple typing candidates being associated with a first probability of how likely the typing candidate would be correctly entered as the input string, wherein the first probability is derived from data collected from multiple users entering a training text;

determining multiple candidate strings that may be used to replace the input string based, at least in part, on a statistical language model, each of the candidate strings being associated with a second probability of how likely the candidate string accurately represents the typing candidate; and

associating an output string with at least one of the candidate strings based, at least in part, on the first and second probabilities associated with the at least one candidate strings.

27. A method as recited in claim 26, wherein the input string comprises phonetic text and the output string comprises language text.

28. A method as recited in claim 26, wherein the input string comprises Pinyin and the output string comprises Hanzi.

29. A method as recited in claim 26, wherein the input string comprises a combination of Pinyin and English and the output string comprises a combination of Hanzi and English.

30. A method as recited in claim 26, further comprising selecting a particular candidate string with a combination of first and second probabilities that represents the least likelihood of typing errors and the greatest likelihood of an accurate conversion and converting the input string to the output string that is associated with the particular candidate string.

31. One or more computer-readable media having computer-executable instructions that, when executed on a processor, direct a computer to perform the method as recited in claim 26.

32. A method comprising:

receiving an input string;

determining typing candidates based, at least in part, on a typing model configured to automatically correct a spelling error, each typing candidate being associated with a first probability representing how likely the typing candidate would be correctly entered as the input string, wherein the first probability is associated with observed errors made during entry of training text by trainers;

determining a conversion string associated with the typing candidate based, at least in part, on a statistical language model, the conversion string being associated with a second probability of how likely the conversion string accurately represents the typing candidate based on a language context of the input string; and

converting the input string to the conversion string.

33. A language input architecture, tangibly embodied on one or more computer-readable media, comprising:

a user interface to receive an input string, the input string containing a spelling error;

a typing model to generate a list of probable candidate strings that may be substituted for the input string based on first typing error probabilities, each first typing error probability indicating a likelihood that the corresponding candidate string would be incorrectly entered as the input string, the typing model being trained on actual data collected from multiple users entering at least one training text;

determining a conversion string associated with each candidate string based, at least in part, on a statistical language model, the conversion string being associated with a second probability of how likely the conversion string accurately represents the typing candidate based on textual elements entered previous to the input string; and

converting the input string to the conversion string.

34. A language input architecture, tangibly embodied on one or more computer-readable media, comprising:

a typing model to generate a list of probable candidate strings that may be substituted for an input string written in phonetic text based on typing error probabilities of how likely each of the candidate strings would be incorrectly entered as the input string, wherein the typing model is trained using data collected from multiple users entering a training text; and

a language model to provide output strings written in language text for each of the candidate strings based on language text probabilities of how likely each of the output strings accurately represent the corresponding candidate strings.

35. A language input architecture as recited in claim 34, wherein the phonetic text is Pinyin and the language text is Hanzi.

36. A language input architecture as recited in claim 34, further comprising a user interface to receive the input string written in phonetic text.

37. A language input architecture as recited in claim 34, further comprising a database to store the candidate strings.

38. A word processor embodied on a computer-readable medium comprising the language input architecture as recited in claim 34.

39. One or more computer-readable media having computer-executable instructions that, when executed on a processor, direct a computer to:

analyze an input string having a spelling error;

determine typing candidates based, at least in part, on a typing model configured to automatically correct the spelling error, each typing candidate being associated with a first probability representing how likely the typing candidate would be correctly entered as the input string, wherein the first probability is derived from data collected from multiple users entering a training text;

determine conversion candidates associated with each of the typing candidates based, at least in part, on a statistical language model, each conversion candidate being associated with a second probability representing a likelihood of the conversion candidate being within a context associated with the input string;

select a conversion candidate from the determined conversion candidates based, at least in part, on the first probability and the second probability; and

convert the input string using the selected conversion candidate.

40. A language input architecture, tangibly embodied on one or more computer-readable media, implemented at least in part on one or more computing devices, comprising:

a user interface to receive an input string, the input string containing a spelling error;

a first typing model to generate a list of probable candidate strings that may be substituted for the input string based on typing error probabilities of how likely each of the candidate strings was incorrectly entered as the input string, the first typing model being trained in a first language and on actual data collected from multiple users entering at least one training text;

a second typing model to generate a list of probable candidate strings that may be substituted for the input string based on typing error probabilities of how likely each of the candidate strings was incorrectly entered as the input string, the second typing model being trained in a second language, wherein each candidate string is associated with a first probability;

a language model to determine conversion candidates associated with each of the candidate strings, each conversion candidate being associated with a second probability representing a likelihood of the conversion candidate being in context with preceding strings; and

a search engine to select a particular candidate string with a combination of first and second probabilities that represents the least likelihood of typing errors and the greatest likelihood of an accurate conversion and converting the input string to an output string that is associated with the particular candidate string.