System and method for inputting text into electronic devices

• US 9,659,002 B2
• Filed: 03/30/2010
• Issued: 05/23/2017
• Est. Priority Date: 03/30/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Touchtype Limited (Microsoft Corporation)
• Inventors: Reynolds, Jonathan Paul, Medlock, Benjamin William
• Primary Examiner(s): He, Jialong
• Application Number:
  US13/262,190
• Publication Number:
  US 20120029910A1
• Time in Patent Office: 2,611 Days
• CPC Class Codes: G06F 3/023 Arrangements for converting discrete items of information into a coded form, e.g. arrangements for interpreting keyboard generated codes as alphanumeric codes, operand codes or instruction codes
• CPC Class Codes: G06F 3/0237 using prediction or retrieval techniques
• CPC Class Codes: G06F 3/04817 using icons graphical or visual programming using iconic symbols G06F8/34
• CPC Class Codes: G06F 3/0482 Interaction with lists of selectable items, e.g. menus
• CPC Class Codes: G06F 3/04886 by partitioning the display area of the touch-screen or the surface of the digitising tablet into independently controllable areas, e.g. virtual keyboards or menus
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs

Abstract

The present invention provides a system comprising a user interface configured to receive text input by a user, a text prediction engine comprising a plurality of language models and configured to receive the input text from the user interface and to generate concurrently text predictions using the plurality of language models, and wherein the text prediction engine is further configured to provide text predictions to the user interface for display and user selection. An analogous method and an interface for use with the system and method are also provided.

Claims

1. A system comprising:

a processor; and

memory storing instructions that, when executed by the processor, configure the processor to;

receive text input by a user, wherein the text input by the user corresponds to a sequence of one or more characters input by the user via a keyboard;

generate independently, by a plurality of different language models, a plurality of text predictions from the received text input, wherein each of the plurality of text predictions comprises a term and an associated probability, wherein the plurality of different language models are pruned by comparing a sequence of terms stored in one language model among the plurality of different language models to a sequence of terms stored in one or more other language models among the plurality of different language models and retaining most probable duplicate or multiple entries by removing less probable duplicate or multiple entries from the plurality of different language models;

combine the plurality of text predictions into final text predictions; and

output at least one of the final text predictions.

2. The system of claim 1, wherein the plurality of text predictions are generated from the plurality of language models at the same time.

3. The system of claim 1, wherein the plurality of different language models comprises one or more of the group comprising a human language model, a static language model, a dynamic language model, an application language model, a community language model, an email language model, an SMS language model, a newswire language model, an academic paper language model, a blog language model, a product review language model, a local dialect language model, an interest group language model, a word processing language model, a patents language model, a company language model, a user community language model, and a user language model.

4. The system of claim 1, wherein the system further comprises a user interface, and wherein the processor is configured to insert the plurality of text predictions into an ordered associative structure or a multimap structure, and return a number of most probable terms as the plurality of text predictions for provision to the user interface.

5. The system of claim 1, wherein each of the plurality of different language models models language using an approximate or probabilistic trie, and an n-gram map, wherein the approximate or probabilistic trie is an extension of a standard trie, with a set of values stored at each node for all subsequently allowable character sequences from that node.

6. The system of claim 5, wherein each of the plurality of different language models is configured to conduct a search of the n-gram map to determine word or phrase predictions for a next term on the basis of up to n−

1 terms of preceding text input.

7. The system of claim 6, wherein each of the plurality of different language models comprises a mechanism to compute the intersection of the predictions determined by the approximate or probabilistic trie, and the n-gram map, by searching for and retaining only identifiers that are present in both prediction sets.

8. The system of claim 7, wherein each of the plurality of different language models further comprises a Bloom filter, comprising an n+1 gram map, which is configured to search the n+1 gram map to return a new text prediction set based on a context of:

the n−

1 terms of preceding text input used to search the n-gram map;

the prediction terms in the determined intersection; and

an extra term of context, immediately preceding the n−

1 terms used to search the n-gram map.

9. The system of claim 6, wherein a punctuation item is stored in the n-gram map with the next term.

10. The system of claim 1, further comprising a user interface that comprises:

a single or multi-character entry mechanism;

a word prediction pane; and

a typing pane to display inputted text.

11. The system of claim 10, further comprising a button, the interface configured to undo a previous word selection in response to a press of the button or in response to a left-to-right gesture on the button.

12. The system of claim 10, wherein the word prediction pane is touch-sensitive and includes one or more word keys to present predicted words and wherein, in response to a word key press selecting a word, the user interface is configured to display the word in the typing pane and pass the current input sequence including the word to the text prediction engine as the context input.

13. The system of claim 10, wherein the word prediction pane is touch-sensitive and includes one or more word keys to present predicted words and wherein, in response to a word key press and hold or left-to-right gesture on the word key to select a word, the user interface is configured to display the word in the typing pane, pass the current input sequence excluding that word to the text prediction engine as the context input, and pass the characters of that word to the text prediction engine as the current term input.

14. The system of claim 1, wherein each of the plurality of different language models is configured to predict a word or phrase prediction based on one or more preceding words.

15. The system of claim 1, wherein generating independently, by the plurality of language models, the plurality of text predictions from the received text input comprises generating at least one first text prediction from a first language model and generating at least one second text prediction from a second language model;

and

wherein combining the plurality of text predictions into the final text predictions comprises combining the at least one first text prediction and the at least one second text prediction into the final text predictions.

16. The system of claim 1, wherein the plurality of language models comprises a general language model and a context specific language model.

17. The system of claim 1, wherein the plurality of language models comprises a model of human language and at least one language model specific to an application, a company, a user community, or a user.

18. The system of claim 1, wherein combining the plurality of text predictions into the final text predictions comprises identifying a number of most probable text predictions as the final text predictions.

19. A method for processing user text input and generating text predictions, comprising;

receiving text input, wherein the text input corresponds to a sequence of one or more characters input via a keyboard;

generating independently, by a plurality of different language models, a plurality of text predictions from the received text input, wherein each of the plurality of text predictions comprises a term and an associated probability, wherein the plurality of different language models are pruned by comparing a sequence of terms stored in one language model among the plurality of different language models to a sequence of terms stored in one or more other language models among the plurality of different language models and retaining most probable duplicate or multiple entries by removing less probable duplicate or multiple entries from the plurality of different language models;

combining the plurality of text predictions into final text predictions; and

outputting at least one of the final text predictions.

20. A computer program product comprising a non-transitory computer readable medium having stored thereon a computer program including instructions that, when executed on a processor configure the processor to carry out the method of claim 19.

21. The method of claim 19, wherein each of the plurality of different language models comprises an n-gram map, and an approximate or probabilistic trie, the method further comprising conducting a search of the n-gram map to determine word or phrase predictions for a next term on the basis of up to n−

1 terms of preceding text input.

22. The method of claim 21, wherein each of the different language models comprise a mechanism to compute the intersection of the word or phrase predictions determined by the approximate or probabilistic trie, and the n-gram map, the method further comprising computing the intersection of the word or phrase predictions.

23. The method of claim 19, wherein generating independently, by the plurality of language models, the plurality of text predictions from the received text input comprises generating at least one first text prediction from a first language model and generating at least one second text prediction from a second language model;

and

wherein combining the plurality of text predictions into the final text predictions comprises combining the at least one first text prediction and the at least one second text prediction into the final text predictions.

24. The method of claim 19, wherein the plurality of language models comprises a general language model and a context specific language model.

25. The method of claim 19, wherein the plurality of language models comprises a model of human language and at least one language model specific to an application, a company, a user community, or a user.

26. The method of claim 19, wherein combining the plurality of text predictions into the final text predictions comprises identifying a number of most probable text predictions as the final text predictions.