SYSTEM AND METHOD FOR INPUTTING TEXT INTO ELECTRONIC DEVICES

• US 20170220552A1
• Filed: 04/20/2017
• Published: 08/03/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
• Granted Patent: US 10,073,829 B2
• Time in Patent Office: 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 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 text predictions by comparing a sequence of terms associated with one language model among the plurality of different language models to a sequence of terms associated with one or more other language models among the plurality of different language models; and

combine the pruned text predictions to generate final text predictions.

2. The system of claim 1, wherein the 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 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, further comprising a user interface, and wherein the processor is configured to insert the text predictions into an ordered associative structure or a multimap structure, and return a number of most probable terms as the text predictions for provision to the user interface.

5. 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 each node for all subsequently allowable character sequences from that node.

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

7. The system of claim 6, 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 both prediction sets.

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

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

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

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

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

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

16. 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 comparing a sequence of terms stored in one of the plurality of different language models to a sequence of terms stored in another of the language models and removing duplicate or multiple entries; and

combining the updated plurality of text predictions into final text predictions.

17. The method of claim 16, 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.

18. The method of claim 17, 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.

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

20. 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 comparing a sequence of terms associated with one language model among the plurality of different language models to a sequence of terms associated with one or more other language models among the plurality of different language models; and

combine the updated text predictions to generate final text predictions.