System and method for inputting text into electronic devices

• US 10,073,829 B2
• Filed: 04/20/2017
• Issued: 09/11/2018
• Est. Priority Date: 03/30/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Touchtype Limited (Microsoft Corporation)
• Inventors: Medlock, Benjamin William, Reynolds, Jonathan Paul
• Primary Examiner(s): He, Jialong
• Application Number:
  US15/493,028
• Publication Number:
  US 20170220552A1
• Time in Patent Office: 509 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 user interface;

a processor; and

memory storing instructions that, when executed by the processor, cause the system to perform operations comprising;

receive text input corresponding to a sequence of one or more input characters;

generate text predictions based on the received text input using a plurality of different language models, the text predictions comprising a term and an associated probability;

prune the plurality of different language models by comparing a first sequence of terms stored in one language model among the plurality of different language models to a second sequence of terms stored in one or more other language models among the plurality of different language models and removing one of the first or second sequence of terms when the first and second sequence of terms are duplicates;

receive additional text input;

provide updated text predictions based on the pruned plurality of different language models;

insert the updated text predictions into an ordered associative structure or a multi-map structure; and

return one or more probable terms of the updated text predictions for provision to the user interface.

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

3. The system of claim 1, wherein the plurality of different language models comprises one or more of 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 plurality of different language 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 nodes for all subsequently allowable character sequences.

5. The system of claim 4, wherein 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 based on n−

1 terms of preceding text input.

6. The system of claim 5, wherein the plurality of different language models comprise a mechanism to compute an 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 the predictions.

7. The system of claim 6, wherein the plurality of different language models further comprise 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 intersection; and

an extra term of context, immediately preceding the n−

1 terms used to search the n-gram map.

8. The system of claim 7, 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.

9. The system of claim 8, further comprising a button, the user 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.

10. The system of claim 8, 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 a current input sequence including the word as context input.

11. The system of claim 8, 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 a current input sequence excluding that word as context input, and pass characters of that word as current term input.

12. The system of claim 8, 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 a current input sequence including the word as context input.

13. The system of claim 8, 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 a current input sequence excluding that word as context input, and pass characters of that word as current term input.

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

15. A method for processing user text input and generating text predictions, comprising:

receiving text input corresponding to a sequence of one or more input characters;

generating, using a plurality of different language models, a plurality of text predictions, based the received text input, wherein the plurality of text predictions comprise at least a term and an associated probability;

update the plurality of text predictions by updating the language models and comparing a first sequence of terms stored in one of the plurality of different language models to a second sequence of terms stored in another of the language models and removing one of the first or second sequence of terms when the first and second sequence of terms are duplicate or multiple entries;

receiving additional text input;

providing the updated plurality of text predictions based on the updated language models;

insert the updated plurality of text predictions into an ordered associative structure or a multi-map structure; and

return one or more probable terms of the updated plurality of text predictions for provision to a user interface.

16. The method of claim 15, wherein the plurality of different language models comprise 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 based on up to n−

1 terms of preceding text input.

17. The method of claim 16, wherein the different language models comprise a mechanism to compute an 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.

18. The method of claim 15, wherein a punctuation item is stored in an n-gram map with the next term.

19. A computer readable memory product having stored thereon a computer program including instructions that, when executed on a processor, configure a computing device to:

receive text input corresponding to a sequence of one or more input characters input;

generate text predictions based on the received text input using a plurality of different language models, the text predictions comprising a term and an associated probability;

update the text predictions by updating the language models and comparing a first sequence of terms stored in one language model among the plurality of different language models to a second sequence of terms stored in one or more other language models among the plurality of different language models and removing one of the first or second sequence of terms when the first and second sequence of terms are duplicates;

receive additional text input;

provide the updated text predictions based on the updated language models;

insert the updated text predictions into an ordered associative structure or a multi-map structure; and

return one or more probable terms of the updated text predictions for provision to a user interface.