Language input architecture for converting one text form to another text form with modeless entry Number:7,165,019 from the United States Patent and Trademark Office (PTO) owispatent

Title: Language input architecture for converting one text form to another text form with modeless entry

Abstract: A language input architecture converts input strings of phonetic text (e.g., Chinese Pinyin) to an output string of language text (e.g., Chinese Hanzi) in a manner that minimizes typographical errors and conversion errors that occur during conversion from the phonetic text to the 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. Each typing model is trained on real data, and learns probabilities of typing errors. 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.

Patent Number: 7,165,019 Issued on 01/16/2007 to Lee,   et al.

---

Inventors:	Lee; Kai-Fu (Woodinville, WA), Chen; Zheng (Beijing, CN), Han; Jian (Beijing, CN)
Assignee:	Microsoft Corporation (Redmond, WA)
Appl. No.:	09/606,807
Filed:	June 28, 2000

---

Current U.S. Class:	704/2 ; 704/10; 704/3; 704/8; 704/9
Current International Class:	G06F 17/28 (20060101)
Field of Search:	704/2,260,9,3,10 715/535 716/11

---

References Cited [Referenced By]

---

U.S. Patent Documents

	4833610		May 1989		Zamora et al.
	5175803		December 1992		Yeh
	5214583		May 1993		Miike et al.
	5218536		June 1993		McWherter
	5258909		November 1993		Damerau et al.
	5278943		January 1994		Gasper et al.
	5319552		June 1994		Zhong
	5510998		April 1996		Woodruff et al.
	5535119		July 1996		Ito et al.
	5572423		November 1996		Church
	5594642		January 1997		Collins et al.
	5646840		July 1997		Yamauchi et al.
	5671426		September 1997		Armstrong, III
	5704007		December 1997		Cecys
	5715469		February 1998		Arning
	5732276		March 1998		Komatsu et al.
	5781884		July 1998		Pereira et al.
	5806021		September 1998		Chen et al.
	5835924		November 1998		Maruyama et al.
	5893133		April 1999		Chen
	5907705		May 1999		Carter
	5930755		July 1999		Cecys
	5933525		August 1999		Makhoul et al.
	5974371		October 1999		Hirai et al.
	5974413		October 1999		Geauregard et al.
	5987403		November 1999		Sugimura
	6047300		April 2000		Walfish et al.
	6073146		June 2000		Chen
	6131102		October 2000		Potter
	6148285		November 2000		Busardo
	6154758		November 2000		Chiang
	6173252		January 2001		Qiu et al.
	6246976		June 2001		Mukaigawa et al.
	6256630		July 2001		Gilai et al.
	6356866		March 2002		Pratley et al.
	6374210		April 2002		Chu
	6487533		November 2002		Hyde-Thomson et al.
	6490563		December 2002		Hon et al.
	6573844		June 2003		Venolia et al.
	6646572		November 2003		Brand

Foreign Patent Documents

	0 555 545		Dec., 1992		EP
	1158776		Feb., 1984		GB
	2158776		Nov., 1985		GB
	2248328		Sep., 1991		GB
	WO 95/17729		Jun., 1995		WO
	WO 00/10101		Feb., 2000		WO

Other References

Mei Yuan et al., "A Neural Network for Disambiguating Pinyin Chinese Input," Proc. Of the Computer Assisted Language Instruction Consortium 94 Annual Symposium, Mar. 14-18, 1994, pp. 239-243, XP-001020457, section: Introduction. cited by other . Camarda et al., "Entering Asian Text with Input Method Editors," Using Word 2000, Chapter 26. cited by other.

Primary Examiner: Dorvil; Richemond
Assistant Examiner: Han; Qi
Attorney, Agent or Firm: Lee & Hayes, PLLC

---

Parent Case Text

---

RELATED CASES

The present application claims benefit of U.S. Provisional Application No. 60/163,902, filed Nov. 5, 1999.

The present application is a co-pending with U.S. patent application Ser. No. 09/606,811, filed concurrently herewith on Jun. 28, 2000, entitled "Language Input User Interface" and with U.S. patent application Ser. No. 09/606,660, filed concurrently herewith on Jun. 28, 2000, entitled "Language Input Architecture For Converting One Text Form to Another Text Form With Tolerance To Spelling, Typographical, And Conversion Errors". Both applications are incorporated herein by reference.

---

Claims

---

The invention claimed is:

1. A method comprising: receiving an input string containing at least first and second languages; segmenting the input string into probable typing candidates having different partitions, one to another; generating one or more candidate strings of language text for each said language using one or more said probable typing candidates; and determining at least one said candidate string that may be used to replace the input string based on a probability of how likely the at least one said candidate string was incorrectly entered as the input string.

2. A method as recited in claim 1 further comprising selectively performing one of (1) converting the input string to the candidate string in the first language, or (2) leaving the input string in the second language.

3. A method as recited in claim 1 wherein the first language is a primary language and the second language is secondary language used less frequently than the primary language.

4. A method as recited in claim 1 wherein the input string of the first language comprises phonetic text and the input string of the second language comprises non-phonetic text.

5. A method as recited in claim 1 wherein the first language is Chinese and the second language is English.

6. A method comprising: allowing entry of an input string containing at least first and second languages without switching modes for entry of the first and second languages; segmenting the input string into probable typing candidates having different partitions, one to another; and determining probable candidate strings, from the probable typing candidates, in at least one of the first and second languages that may be used to replace the input string based on probabilities of how likely each of the candidate strings was incorrectly entered as the input string; selectively performing, based on the probabilities, one of (1) converting the input string to an output string in the first language and outputting the output string, or (2) outputting the input string in the second language.

7. A method as recited in claim 6 further comprising: displaying the input string containing the first and second language in a single edit line; and selectively displaying the output string or the input string in the single edit line.

8. A method as recited in claim 6 wherein the first language is Chinese and the second language is some language other than Chinese.

9. A language input architecture comprising: a user interface to receive an input string written in a combination of phonetic text and non-phonetic text; a first typing model to produce probable first typing candidates written in the phonetic text that may be substituted for the input string based on typing error probabilities of how likely each of the first candidate strings was incorrectly entered as the input string, wherein each said first candidate string is produced at least in part by segmenting the input string; a second typing model to produce probable second typing candidates written in the non-phonetic text that may be substituted for the input string based on typing error probabilities of how likely each of the second candidate strings was incorrectly entered as the input string, wherein each said second candidate string is produced at least in part by segmenting the input string; a language model to provide possible conversion strings written in language text for the first typing candidates written in the phonetic text; and a search engine configured to selectively (1) convert the input string to one of the conversion strings so that the phonetic text is replaced with the language text, or (2) output one of the second candidates so that the non-phonetic text is maintained without conversion.

10. A language input architecture comprising as recited in claim 9 wherein the search engine converts the input string to one of the conversion strings when the first probability is higher than the second probability.

11. A language input architecture comprising as recited in claim 9 wherein the search engine outputs one of the second candidates based on a comparison of the typing error probabilities of the second candidate strings with the typing error probabilities of the first candidate strings.

12. A language input architecture comprising as recited in claim 9 wherein the phonetic text is a first language and the non-phonetic text is a second language.

13. A language input architecture comprising as recited in claim 9, wherein the phonetic text is Pinyin and the non-phonetic text is English.

14. A method comprising: receiving an input string containing at least first and second languages; segmenting the input string into probable typing candidates having different partitions, one to another; determining at least one first candidate string using at least one said probable typing candidate that may be used to replace the input string based on a first probability of how likely the first candidate string was incorrectly entered as the input string in the first language; determining at least one second candidate string using one or more said probable typing candidates that may be used to replace the input string based on a second probability of how likely the second candidate string was incorrectly entered as the input string in the second language; using the first candidate string if the first probability is higher than the second probability to derive at least one output string containing the first language; and using the second candidate string if the first probability is lower than the second probability to derive at least one output string containing the second language.

15. A method as recited in claim 14, wherein the first language is a primary language and the second language is secondary language used less frequently than the primary language.

16. A method as recited in claim 14, wherein the input string of the first language comprises phonetic text and the input string of the second language comprises non-phonetic text.

17. A method as recited in claim 14, wherein the first language is Chinese and the second language is English.

18. A method as recited in claim 14, wherein the input string is a combination of Chinese Pinyin and English, and the output string is a combination of Chinese Hanzi and English.

19. A method as recited in claim 14, further comprising obtaining the first and second candidate strings from a database.

20. A method as recited in claim 14, further comprising: deriving the first probability that the first candidate string was incorrectly entered from data collected from multiple users entering a training text in the first language; and deriving the second probability that the second candidate string was incorrectly entered from data collected from multiple users entering a training text in the second language.

21. A method as recited in claim 14, further comprising displaying the output string in line with the input string being entered by a user.

22. 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 14.

23. A language input architecture comprising: a first typing model to receive an input string, segment the input string into probably typing candidates having different partitions and determine a first typing error probability of how likely a first candidate string was incorrectly entered as the input string; a second typing model to receive the input string, segment the input string into probably typing candidates having different partitions and determine a second typing error probability of how likely a second candidate string was incorrectly entered as the input string; and a search engine to select one of the first and second candidate strings based on the respective first and second typing error probabilities.

24. A language input architecture as recited in claim 23 wherein the first typing model is trained using a first language and the second typing model is trained using a second language.

25. A language input architecture as recited in claim 23 wherein the input string contains phonetic text and non-phonetic text and the first typing model is trained to the phonetic text and the second typing model is trained to the non-phonetic text.

26. A language input architecture as recited in claim 23 wherein the first typing model is trained using Chinese and the second typing model is trained using English.

27. A language input architecture as recited in claim 23 wherein the input string contains Pinyin and English and the first typing model is trained to the Pinyin and the second typing model is trained to the English.

28. A language input architecture as recited in claim 23 further comprising a language model to provide an output string for the selected typing candidate.

29. A language input architecture as recited in claim 28 wherein the search engine converts the input string to the output string.

30. A language input architecture as recited in claim 28 further comprising a user interface to receive the input string and to display the output string in a common edit line.

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

32. One or more computer-readable media having computer-executable instructions that, when executed on a processor, direct a computer to: allow entry of an input string containing at least first and second languages without switching modes for entry of the first and second languages; determine probable candidate strings in at least one of the first and second languages that may be used to replace the input string based on probabilities of how likely each of the candidate strings was incorrectly entered as the input string, wherein the probable candidate strings are generated from probable typing candidates formed by segmenting the input string; selectively perform, based on the probabilities, one of (1) converting the input string to an output string in the first language and outputting the output string, or (2) outputting the input string in the second language.

33. One or more computer-readable media having computer-executable instructions that, when executed on a processor, direct a computer to: receive an input string containing phonetic text and non-phonetic text; segment the input string into probable typing candidates having different partitions, one to another; generate one or more candidate strings using one or more said probable typing candidates; determine at least one first said candidate string written in the phonetic text that may be used to replace the input string based on a first probability of how likely the first said candidate string was incorrectly entered as the input string; determine at least one second said candidate string written in the non-phonetic text that may be used to replace the input string based on a second probability of how likely the second said candidate string was incorrectly entered as the input string in the second language; associate possible conversion strings written in language text for the first typing candidates written in the phonetic text; convert the input string to the conversion string associated with the first said candidate string when comparison of the first probability with the second probability indicates it is more likely that the first said candidate string was incorrectly entered as the input string so that the phonetic text is converted to the language text; and output the second said candidate string when comparison of the first probability with the second probability indicates it is more likely that the second said candidate string was incorrectly entered as the input string in the second language so that the non-phonetic text remains unconverted.

---

Description

---

TECHNICAL FIELD

The invention relates to a language input method and system. More particularly, the invention provides language input method and system that has error tolerance for both typographical errors that occur during text entry and conversion errors that occur during conversion from one language form to another language form.

BACKGROUND

Language specific word processing software has existed for many years. More sophisticated word processors offer users advanced tools, such as spelling and grammar correction, to assist in drafting documents. Many word processors, for example, can identify words that are misspelled or sentence structures that are grammatically incorrect and, in some cases, automatically correct the identified errors.

Generally speaking, there are two causes for errors being introduced into a text. One cause is that the user simply does not know the correct spelling or sentence structure. Word processors can offer suggestions to aid the user in choosing a correct spelling or phraseology. The second and more typical cause of errors is that the user incorrectly enters the words or sentences into the computer, even though he/she knew the correct spelling or grammatical construction. In such situations, word processors are often quite useful at identifying the improperly entered character strings and correcting them to the intended word or phrase.

Entry errors are often more prevalent in word processors designed for languages that do not employ Roman characters. Language specific keyboards, such as the English version QWERTY keyboards, do not exist for many languages because such languages have many more characters than can be conveniently arranged as keys in the keyboard. For example, many Asian languages contain thousands of characters. It is practically impossible to build a keyboard to support separate keys for so many different characters.

Rather than designing expensive language and dialect specific keyboards, language specific word processing systems allow the user to enter phonetic text from a small character-set keyboard (e.g., a QWERTY keyboard) and convert that phonetic text to language text. "Phonetic text" represents the sounds made when speaking a given language, whereas the "language text" represents the actual written characters as they appear in the text. In the Chinese language, for example, Pinyin is an example of phonetic text and Hanzi is an example of the language text. By converting the phonetic text to language text, many different languages can be processed by the language specific word processor using conventional computers and standard QWERTY keyboards.

Word processors that require phonetic entry thus experience two types of potential entry errors. One type of error is common typing mistakes. However, event if the text is free of typographical errors, another type of error is that the word processing engine might incorrectly convert the phonetic text to an unintended character text. When both of these two problems are at work on the same phonetic text input string, a cascade of multiple errors may result. In some situations, the typing induced errors may not be readily traced without a lengthy investigation of the entire context of the phrase or sentence.

The invention described herein is directed primarily to the former type of entry errors made by the user when typing in the phonetic text, but also provide tolerance for conversion errors made by the word processing engine. To better demonstrate the problems associated with such typing errors, consider a Chinese-based word processor that converts the phonetic text, Pinyin, to a language text, Hanzi.

There are several reasons why entry of phonetic text often yields increased typing errors. One reason is that the average typing accuracy on an English keyboard is lower in China than in English-speaking countries. A second reason is that phonetic text is not used all that frequently. During earlier education years, users are not as prone to study and learn phonetic spelling as, for example, English-speaking users are taught to spell words in English.

A third reason for increased typing errors during phonetic text input is that many people speak natively in a regional dialect, as opposed to a standard dialect. The standard dialect, which is the origin of phonetic text, is a second language. In certain dialects and accents, spoken words may not match corresponding proper phonetic text, thus making it more difficult for a user to type phonetic text. For instance, many Chinese speak various Chinese dialects as their first language and are taught Mandarin Chinese, which is the origin of Pinyin, as a second language. In some Chinese dialects, for example, there is no differentiation in pronouncing "h" and "w" is certain contexts; in other dialects, the same can be said for "ng" and "n"; and yet in others, "r" is not articulated. As a result, a Chinese user who speaks Mandarin as a second language may be prone to typing errors when attempting to enter Pinyin.

Another possible reason for increased typing errors is that it is difficult to check for errors while typing phonetic text. This is due in part to the fact that phonetic text tends to be long, unreadable strings of characters that are difficult to read. In contrast to English-based text input, where what you see is what you typed, entered phonetic text is often not "what you see is what you get." Rather, the word processor converts the phonetic text to language text. As a result, users generally do not examine the phonetic text for errors, but rather wait until the phonetic text is converted to the language text.

For this last reason, a typing error can be exceptionally annoying in the context of Pinyin entry. Pinyin character strings are very difficult to review and correct because there is no spacing between characters. Instead, the Pinyin characters run together regardless of the number of words being formed by the Pinyin characters. In addition, Pinyin-to-Hanzi conversion often does not occur immediately, but continues to formulate correct interpretations as additional Pinyin text is entered. Thus, if a user types in the wrong Pinyin symbols, the single error may be compounded by the conversion process and propagated downstream to cause several additional errors. As a result, error correction takes longer because by the time the system converts decisively to Hanzi characters and then the user realizes there has been an error, the user is forced to backspace several times just to make one correction. In some systems, the original error cannot even be revealed.

Since mistakes are expected to be made frequently during phonetic input, there is a need for a system that can tolerate errors in the phonetic input. It is desirable that the system would return the correct answer even though the phonetic string contains slightly erroneous characters.

Language specific word processors face another problem, separate from the entry problem, which concerns switching modes between two languages in order to input words from the different language into the same text. It is common, for example, to draft a document in Chinese that includes English words, such as technical terms (e.g., Internet) and terms that are difficult to translate (e.g., acronyms, symbols, surnames, company names, etc.). Conventional word processors require a user to switch modes from one language to the other language when entering the different words. Thus, when a user wants to enter a word from a different language, the user must stop thinking about text input, switch the mode from one language to another, enter the word, and then switch the mode back to the first language. This significantly reduces the user's typing speed and requires the user to shift his/her attention between the text input task and an extraneous control task of changing language modes.

Accordingly, there is a need for a "modeless" system that does not require mode switching. To avoid modes, the system should be able to detect the language that is being typed, and then convert the letter sequence to one language or the other, dynamically, on a word-by-word basis.

This is not as easy as it may seem, however, because many character strings may be appropriate in both contexts. For example, many valid English words are also valid Pinyin strings. Furthermore, more ambiguities may arise since there are no spaces between Chinese characters, and between Chinese and English words, during Pinyin input.

As an example, when a user types a string of Pinyin input text "woshiyigezhongguoren", the system converts this string into Chinese character: "" (generally translated to "I am a Chinese").

Sometimes, instead of typing "woshiyigezhongguoren", a user types the following:

wosiyigezhongguoren (the error is the "sh" and "s" confusion);

woshiyigezongguoren (the error is the "zh" and "z" confusion);

woshiygezhongguoren (the error is the "i" omission after "y");

woshiyigezhonggouren (the error is the "ou" juxtaposition);

woshiyigezhongguiren (the error is the "i" and "o" confusion).

The inventors have developed a word processing system and method that makes spell correction feasible for difficult foreign languages, such as Chinese, and allows modeless entry of multiple languages through automatic language recognition.

SUMMARY

A language input architecture converts input strings of phonetic text (e.g., Chinese Pinyin) to an output string of language text (e.g., Chinese Hanzi) in a manner that minimizes typographical errors and conversion errors that occur during conversion from the phonetic text to the language text. The language input architecture may be implemented in a wide variety of areas, including word processing programs, email programs, spreadsheets, browsers, and the like.

In one implementation, the language input architecture has a user interface to receive in input string of characters, symbols, or other text elements. The input string may include phonetic text and non-phonetic text, as well as one or more languages. The user interface allows the user to enter the input text string in a single edit line without switching modes between entry of different text forms or different languages. In this manner, the language input architecture offers modeless entry of multiple languages for user convenience.

The language input architecture also has a search engine, one or more typing models, a language model, and one or more lexicons for different languages. The search engine receives the input string from the user interface and distributes the input string to the one or more typing models. Each typing model is configured to generate a list of probable typing candidates 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 probable typing candidates may be stored in a database.

The typing model is trained from data collected from many trainers who enter a training text. For instance, in the context of the Chinese language, the trainers enter a training text written in Pinyin. The observed errors made during entry of the training text are used to compute the probabilities associated with the typing candidates that may be used to correct the typing error. Where multiple typing models are employed, each typing model may be trained in a different language.

In one implementation, the typing model may be trained by reading strings of input text and mapping syllables to corresponding typed letters of each string. A frequency count expressing the number of times each typed letter is mapped to one of the syllables is kept and the probability of typing for each syllable is computed from the frequency count.

The typing model returns a set of probable typing candidates that account for possible typographical errors that exist in the input string. The typing candidates are written in the same language or text form as the input string.

The search engine passes the typing candidates to the language model, which provides probable conversion strings for each of the typing candidates. More particularly, the language model is a trigram language model that attempts to determine a language text probability of how likely a probable conversion output string represents the candidate string based on two previous textual elements. The conversion string is written in a different language or different text form than the input string. For example, the input string might comprise Chinese Pinyin or other phonetic text and the output string might comprise Chinese Hanzi or other language text.

Based upon the probabilities derived in the typing and language models, the search engine selects the associated typing candidate and conversion candidate that exhibits the highest probability. The search engine converts the input string (e.g., written in phonetic text) to an output string consisting of the conversion candidate returned from the language model so that the entered text form (e.g., phonetic text) is replaced with another text form (e.g., language text). In this manner, any entry error made by the user during entry of the phonetic text is eliminated.

Where multiple languages are used, the output string may have a combination of the conversion candidate as well as portions of the input string (without conversion). An example of this latter case is where the Chinese-based language input architecture outputs both converted Pinyin-to-Hanzi text along with non-converted English text.

The user interface displays the output string in the same edit line that continues to be used for entry of the input string. In this manner, the conversion is taking place automatically and concurrently with the user entering additional text.

BRIEF DESCRIPTION OF THE DRAWINGS

The same numbers are used throughout the Figures to reference like components and features.

FIG. 1 is a block diagram of a computer system having a language-specific word processor that implements a language input architecture.

FIG. 2 is a block diagram of one exemplary implementation of the language input architecture.

FIG. 3 is a diagrammatic illustration of a text string that is parsed or segmented into different sets of syllables, and candidates that may be used to replace those syllables assuming the text string contains errors.

FIG. 4 is a flow diagram illustrating a general conversion operation performed by the language input architecture.

FIG. 5 is a block diagram of a training computer used to train probability-based models employed in the language input architecture.

FIG. 6 is a flow diagram illustrating one training technique.

FIG. 7 is a block diagram of another exemplary implementation of the language input architecture, in which multiple typing models are employed.

FIG. 8 is a flow diagram illustrating a multilingual conversion process.

DETAILED DESCRIPTION

The invention pertains to a language input system and method that converts one form of a language (e.g., phonetic version) to another form of the language (e.g., written version). The system and method have error tolerance for spelling and typographical errors that occur during text entry and conversion errors that occur during conversion from one language form to another language form. For discussion purposes, the invention is described in the general context of word processing programs executed by a general-purpose computer. However, the invention may be implemented in many different environments other than word processing and may be practiced on many diverse types of devices. Other contexts might include email programs, spreadsheets, browsers, and the like.

The language input system employs a statistical language model to achieve very high accuracy. In one exemplary implementation, the language input architecture uses statistical language modeling with automatic, maximum-likelihood-based methods to segment words, select a lexicon, filter training data, and derive a best possible conversion candidate.

Statistical sentence-based language modeling assumes, however, that a user's input is perfect. In reality, there are many typing and spelling errors in the user's input. Accordingly, the language input architecture includes one or more typing models that utilize probabilistic spelling models to accept correct typing while tolerating common typing and spelling errors. The typing models may be trained for multiple languages, such as English and Chinese, to discern how likely the input sequence is a word in one language as opposed to another language. Both models can run in parallel and are guided by the language model (e.g., a Chinese language model) to output the most likely sequence of characters (i.e., English and Chinese characters).

Exemplary Computer System

FIG. 1 shows an exemplary computer system 100 having a central processing unit (CPU) 102, a memory 104, and an input/output (I/O) interface 106. The CPU 102 communicates with the memory 104 and I/O interface 106. The memory 104 is representative of both volatile memory (e.g., RAM) and non-volatile memory (e.g., ROM, hard disk, etc.).

The computer system 100 has one or more peripheral devices connected via the I/O interface 106. Exemplary peripheral devices include a mouse 110, a keyboard 112 (e.g., an alphanumeric QWERTY keyboard, a phonetic keyboard, etc.), a display monitor 114, a printer 116, a peripheral storage device 118, and a microphone 120. The computer system may be implemented, for example, as a general-purpose computer. Accordingly, the computer system 100 implements a computer operating system (not shown) that is stored in memory 104 and executed on the CPU 102. The operating system is preferably a multi-tasking operating system that supports a windowing environment. An example of a suitable operating system is a Windows brand operating system from Microsoft Corporation.

It is noted that other computer system configurations may be used, such as hand-held devices, multiprocessor systems, microprocessor-based or programmable consumer electronics, network PCs, minicomputers, mainframe computers, and the like. In addition, although a standalone computer is illustrated in FIG. 1, the language input system may be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network (e.g., LAN, Internet, etc.). In a distributed computing environment, program modules may be located in both local and remote memory storage devices.

A data or word processing program 130 is stored in memory 104 and executed on CPU 102. Other programs, data, files, and such may also be stored in memory 104, but are not shown for ease of discussion. The word processing program 130 is configured to receive phonetic text and convert it automatically to language text. More particularly, the word processing program 130 implements a language input architecture 131 that, for discussion purposes, is implemented as computer software stored in memory and executable on a processor. The word processing program 130 may include other components in addition to the architecture 131, but such components are considered standard to word processing programs and will not be shown or described in detail.

The language input architecture 131 of word processing program 130 has a user interface (UI) 132, a search engine 134, one or more typing models 135, a language model 136, and one or more lexicons 137 for various languages. The architecture 131 is language independent. The UI 132 and search engine 134 are generic and can be used for any language. The architecture 131 is adapted to a particular language by changing the language model 136, the typing model 135 and the lexicon 137.

The search engine 134 and language module 136 together form a phonetic text-to-language text converter 138. With the assistance of typing model 135, the converter 138 becomes tolerant to user typing and spelling errors. For purposes of this disclosure, "text" means one or more characters and/or non-character symbols. "Phonetic text" generally refers to an alphanumeric text representing sounds made when speaking a given language. A "language text" is the characters and non-character symbols representative of a written language. "Non-phonetic text" is alphanumeric text that does not represent sounds made when speaking a given language. Non-phonetic text might include punctuation, special symbols, and alphanumeric text representative of a written language other than the language text.

Perhaps more generally stated, phonetic text may be any alphanumeric text represented in a Roman-based character set (e.g., English alphabet) that represents sounds made when speaking a given language that, when written, does not employ the Roman-based character set. Language text is the written symbols corresponding to the given language.

For discussion purposes, word processor 130 is described in the context of a Chinese-based word processor and the language input architecture 131 is configured to convert Pinyin to Hanzi. That is, the phonetic text is Pinyin and the language text is Hanzi. However, the language input architecture is language independent and may be used for other languages. For example, the phonetic text may be a form of spoken Japanese, whereas the language text is representative of a Japanese written language, such as Kanji. Many other examples exist including, but not limited to, Arabic languages, Korean language, Indian language, other Asian languages, and so forth.

Phonetic text is entered via one or more of the peripheral input devices, such as the mouse 110, keyboard 112, or microphone 120. In this manner, a user is permitted to input phonetic text using keyed entry or oral speech. In the case of oral input, the computer system may further implement a speech recognition module (not shown) to receive the spoken words and convert them to phonetic text. The following discussion assumes that entry of text via keyboard 112 is performed on a full size, standard alphanumeric QWERTY keyboard.

The UI 132 displays the phonetic text as it is being entered. The UI is preferably a graphical user interface. A more detailed discussion of the UI 132 is found in co-pending application Ser. No. 09/606,660, entitled "LANGUAGE INPUT USER INTERFACE", which is incorporated herein by reference.

The user interface 132 passes the phonetic text (P) to the search engine 134, which in turn passes the phonetic text to the typing model 137. The typing model 137 generates various typing candidates (TC.sub.1, . . . , TC.sub.N) that might be suitable edits of the phonetic text intended by the user, given that the phonetic text may include errors. The typing model 137 returns multiple typing candidates with reasonable probabilities to the search engine 134, which passes the typing candidates onto the language model 136. The language model 136 evaluates the typing candidates within the context of the ongoing sentence and generates various conversion candidates (CC.sub.1, . . . , CC.sub.N) written in the language text that might be representative of a converted form of the phonetic text intended by the user. The conversion candidates are associated with the typing candidates.

Conversion from phonetic text to language text is not a one-for-one conversion. The same or similar phonetic text might represent a number of characters or symbols in the language text. Thus, the context of the phonetic text is interpreted before conversion to language text. On the other hand, conversion of non-phonetic text will typically be a direct one-to-one conversion wherein the alphanumeric text displayed is the same as the alphanumeric input.

The conversion candidates (CC.sub.1, . . . , CC.sub.N) are passed back to the search engine 134, which performs statistical analysis to determine which of the typing and conversion candidates exhibit the highest probability of being intended by the user. Once the probabilities are computed, the search engine 134 selects the candidate with the highest probability and returns the language text of the conversion candidate to the UI 132. The UI 132 then replaces the phonetic text with the language text of the conversion candidate in the same line of the display. Meanwhile, newly entered phonetic text continues to be displayed in the line ahead of the newly inserted language text.

If the user wishes to change language text from the one selected by the search engine 134, the user interface 132 presents a first list of other high probability candidates ranked in order of the likelihood that the choice is actually the intended answer. If the user is still dissatisfied with the possible candidates, the UI 132 presents a second list that offers all possible choices. The second list may be ranked in terms of probability or other metric (e.g., stroke count or complexity in Chinese characters).

Language Input Architecture

FIG. 2 illustrates the language input architecture 131 in more detail. The architecture 131 supports error tolerance for language input, including both typographical errors and conversion errors. In addition to the UI 132, search engine 134, language model 136, and typing model 135, the architecture 131 further includes an editor 204 and a sentence context model 216. A sentence context model 216 is coupled to the search engine 134.

The user interface 132 receives input text, such as phonetic text (e.g. Chinese Pinyin text) and non-phonetic text (e.g., English), from one or more peripheral devices (e.g., keyboard, mouse, microphone) and passes the input text to the editor 204. The editor 204 requests that the search engine 132, in conjunction with the typing model 135 and language model 136, convert the input text into an output text, such as a language text (e.g. Chinese Hanzi text). The editor 204 passes the output text back to the UI 132 for display.

Upon receiving a string of input text from the user interface 132, the search engine 134 sends the string of input text to one or more of the typing models 135 and to the sentence context model 216. The typing model 135 measures a priori probability of typing errors in the input text. The typing model 135 generates and outputs probable typing candidates for the input text entered by the user, effectively seeking to cure entry errors (e.g., typographical errors). In one implementation, the typing model 135 looks up potential candidates in a candidate database 210. In another implementation, the typing model 135 uses statistical-based modeling to generate probable candidates for the input text.

The sentence context model 216 may optionally send any previously input text in the sentence to the search engine 132 to be used by the typing model 135. In this manner, the typing model may generate probable typing candidates based on a combination of the new string of text and the string of text previously input in the sentence.

It is appreciated that the terms "typing errors", "typographical errors", and "spelling errors" may be interchangeable to refer to the errors made during keyed entry of the input text. In the case of verbal entry, such errors may result from improper recognition of the vocal input.

The typing model 135 may return all of the probable typing candidates or prune off the probable typing candidates with lower probability, thereby returning only the probable typing candidates with higher probability back to the search engine 134. It will also be appreciated that the search engine 134, rather than the typing model 135, can perform the pruning function.

According to one aspect of the invention, the typing model 135 is trained using real data 212 collected from hundreds or thousands of trainers that are asked to type in sentences in order to observe common typographical mistakes. The typing model and training are described below in more detail under the heading "Training the Typing Model."

The search engine 134 sends the list of probable typing candidates returned from the typing model 135 to the language model 136. Simplistically, a language model measures the likelihood of words or text strings within a given context, such as a phrase or sentence. That is, a language model can take any sequence of items (words, characters, letters, etc.) and estimate the probability of the sequence. The language model 136 combines the probable typing candidates from the search engine 134 with the previous text and generates one or more candidates of language text corresponding to the typing candidates.

Corpus data or other types of data 214 are used to train the trigram language model 136. The training corpus 214 may be any type of general data, such as everyday text such as news articles or the like, or environment-specific data, such as text directed to a specific field (e.g., medicine). Training the language model 136 is known in the word processing art and is not described in detail.

The language input architecture 131 tolerates errors made during entry of an input text string and attempts to return the most likely words and sentences given the input string. The language model 136 helps the typing model 135 to determine which sentence is most reasonable for the input string entered by the user. The two models can be described statistically as the probability that an entered string s is a recognizable and valid word w from a dictionary, or P(w|s). Using Bayes formula, the probability P(w|s) is described as:

.function..function..function..function. ##EQU00001##

The denominator P(s) remains the same for purposes of comparing possible intended words given the entered string. Accordingly, the analysis concerns only the numerator product P(s|w)P(w), where the probability P(s|w) represents the spelling or typing model and the probability P(w) represents the language model. More specifically, the typing model P(s|w) describes how likely a person intending to input X will instead input Y; whereas, the language model P(w) describes how likely a particular word given the sentence context is to have been generated.

In the context of converting Pinyin to Hanzi, the probability P(w|s) can be restated as P(H|P), where H represents a Hanzi string and P represents a Pinyin string. The goal is to find the most probable Chinese character H', so as to maximize P(H|P). Thus, the probability P(H|P) is the likelihood that an entered Pinyin string P is a valid Hanzi string H. Since P is fixed and hence P(P) is a constant for a given Pinyin string, Bayes formula reduces the probability P(H|P), as follows: H'=arg max.sub.H P(H|P)=arg max.sub.H P(P|H)*P(H)

The probability P(P|H) represents the spelling or typing model. Usually, the Hanzi string H can be further decomposed into multiple words W.sub.1, W.sub.2, W.sub.3, . . . , W.sub.M, and the probability P(P|H) can be estimated as: Pr(P|H).apprxeq..PI.P(P.sub.f(i)|W.sub.i) where P.sub.f(i) is the sequence of Pinyin characters that correspond to the word W.sub.i.

In prior art statistically-based Pinyin-to-Hanzi conversion systems, the probability P(P.sub.f(i)|W.sub.i) is set to 1 if P.sub.f(i) is an acceptable spelling of word W.sub.i and is set to 0 if P.sub.f(i) is not an acceptable spelling of word W.sub.i. As a result, conventional systems provide no tolerance for any erroneously entered characters. Some systems have the "southern confused pronunciation" feature to deal with this problem, although this also employs the preset values probabilities of 1 and 0. In addition, such systems only address a small fraction of typing errors because it is not data-driven (learned from real typing errors).

In contrast, the language architecture described herein utilizes both the typing model and the language model to carry out a conversion. The typing model enables error tolerance to erroneously input characters by training the probability of P(P.sub.f(i)|W.sub.i) from a real corpus. There are many ways to build typing models. In theory, all possible P(P.sub.f(i)|W.sub.i) can be trained; but in practice, there are too many parameters. To reduce the number of parameters that need to be trained, one approach is to consider only single-character words and map all characters with equivalent pronunciation into a single syllable. In the Chinese language, there are approximately 406 syllables, so this is essentially training P(Pinyin text|syllable), and then mapping each character to its corresponding syllable. This is described below in more detail beneath the heading "Training the Typing Model".

With the language architecture 131, a wide range of probabilities is computed. One goal of Pinyin-to-Hanzi conversion is to find the Hanzi string H that maximizes the probability P(P|H). This is accomplished by selecting the W.sub.i that yields the largest probability as the best Hanzi sequence. In practice, efficient searches like the well-known Viterbi Beam search may be used. For more information on the Viterbi Beam search, the reader is directed to an article by Kai-Fu Lee, entitled "Automatic Speech Recognition", Kluwer Academic Publishers, 1989, and to writings by Chin-Hui Lee, Frank K. Soong, Kuldip K. Paliwal, entitled "Automatic Speech and Speaker Recognition--Advanced Topics", Kluwer Academic Publishers, 1996.

The probability P(H) represents the language model, which measures the a priori probability of any given string of words. A common approach to building a statistical language model is to utilize a prefix tree-like data structure to build an N-gram language model from a known training set of text. One example of a widely used statistical language model is the N-gram Markov model, which is described in "Statistical Methods for Speech Recognition", by Frederick Jelinek, The MIT Press, Cambridge, Mass., 1997. The use of a prefix tree data structure (a.k.a. a suffix tree, or a PAT tree) enables a higher-level application to quickly traverse the language model, providing the substantially real-time performance characteristics described above. The N-gram language model counts the number of occurrences of a particular item (word, character, etc.) in a string (of size N) throughout a text. The counts are used to calculate the probability of the use of the item strings.

The language model 136 is preferably a trigram language model (i.e., an N-gram where N=3), although a bigram may be suitable in some contexts. Trigram language models are suitable for English and also work well for Chinese, assuming it utilizes a large training corpus.

A trigram model considers the two most previous characters in a text string to predict the next character, as follows: (a) characters (C) are segmented into discrete language text or words (W) using a pre-defined lexicon, wherein each W is mapped in the tree to one or more C's; (b) predict the probability of a sequence of words (W.sub.1, W.sub.2, . . . W.sub.M) from the previous two words: P(W.sub.1,W.sub.2,W.sub.3, . . . W.sub.M).apprxeq..PI.P(W.sub.n|W.sub.n-1,W.sub.n-2) (1) where P( ) represents the probability of the language text; W.sub.1 is the current word W.sub.n-1 is the previous word W.sub.n-2 is the word previous to W.sub.n-1