System and method for inputting text into electronic devices

• US 9,384,185 B2
• Filed: 09/29/2011
• Issued: 07/05/2016
• Est. Priority Date: 09/29/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Touchtype Limited (Microsoft Corporation)
• Inventors: Medlock, Benjamin, Orr, Douglas Alexander Harper
• Primary Examiner(s): YEN, ERIC L
• Application Number:
  US13/876,159
• Publication Number:
  US 20130253912A1
• Time in Patent Office: 1,741 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 3/0236 using selection techniques to select from displayed items
• CPC Class Codes: G06F 3/0237 using prediction or retrieval techniques
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs

Abstract

A text prediction engine, a system comprising a text prediction engine, and a method for generating sequence predictions. The text prediction engine, system and method generate a final set of sequence predictions, each with an associated probability value.

Claims

1. A text prediction system, comprising:

one or more processors;

memory storing instructions that, when executed by the one or more processors, cause the one or more processors to;

generate at least one first sequence prediction based on a first evidence source and a first model, wherein each of the at least one first sequence prediction comprises a first sequence and a first associated probability estimate;

generate at least one second sequence prediction based on a second evidence source and a second model, wherein each of the at least one second sequence prediction comprises a second sequence and a second associated probability estimate;

wherein the first associated probability estimate or the second associated probability estimate is weighted according to a probability that the first model or the second model comprises a given context sequence; and

combine the at least one first sequence prediction and the at least one second sequence prediction into at least one combined sequence prediction based at least in part on the first associated probability estimate and the second associated probability estimate; and

a display coupled to at least one of the one or more processors or the memory, wherein the display is configured to;

output the at least one combined sequence prediction within a text entry graphical user interface.

2. The text prediction system according to claim 1, wherein the at least one first sequence prediction and the at least one second sequence prediction are combined into at least one combined sequence prediction by ranking the at least one first sequence prediction and the at least one second sequence prediction and removing duplicate sequence predictions, wherein, the first sequence prediction or the second sequence prediction of the duplicate sequence predictions is removed dependent on which of the first associated probability estimate and the second associated probability estimate is lowest.

3. The system according to claim 1, further comprising a prior model configured to generate at least one third sequence prediction, wherein each of the at least one third sequence prediction comprises a third sequence and a third associated probability estimate.

4. The system according to claim 3, wherein:

the first model comprises a context model and the second model comprises an input model, the first evidence source comprises a first sequence of characters from the text entry user interface and the second evidence source comprises a second sequence of characters from the text entry user interface; and

wherein the prior model comprises a target prior model.

5. The system according to claim 4, wherein:

the input model comprises a candidate model and a language model;

the context model comprises a candidate model and a prefix match model; and

the target prior model comprises a character model and a unigram model.

6. The system according to claim 1, wherein at least one of the at least one first sequence prediction or the at least one second sequence prediction are generated based at least in part on an uncertainty associated with the first evidence source or the second evidence source.

7. The system according to claim 1, wherein the instructions, when executed by the one or more processors, further cause the one or more processors to:

approximately normalise the first associated probability estimate and the second associated probability estimate by estimating a normalisation factor for the first associated probability estimate and the second associated probability estimate.

8. The system according to claim 7, further comprising a prior model configured to generate at least one third sequence prediction, wherein each of the at least one third sequence prediction comprises a third sequence and a third associated probability estimate.

9. The system according to claim 1, wherein the first evidence source is modelled independently by the first model to generate the at least one first sequence prediction, and wherein the second evidence source is modelled independently by the second model to generate the at least one second sequence prediction.

10. The system according to claim 1, wherein the first evidence source comprises user inputted text, and wherein the first model comprises a plurality of language models corresponding to a plurality of different languages.

11. The system according to claim 1, wherein the first evidence source is treated conditionally independent of the second evidence, given the at least one combined sequence prediction.

12. The system according to claim 1, wherein the instructions, when executed by the one or more processors, further cause the one or more processors to receive text from the text entry graphical user interface, to generate the at least one combined sequence prediction, and to provide the at least one combined sequence prediction to the text entry graphical user interface for output to the display.

13. The system according to claim 12, wherein the instructions, when executed by the one or more processors, further cause the one or more processors to input automatically one of the at least one combined sequence prediction into the system if a probability associated with the one of the at least one combined sequence prediction is equal to or greater than a threshold probability estimate.

14. A non-transitory computer-readable storage medium containing a set of instructions, that when executed by a processor, cause the processor to process a sequence of characters entered into a user interface, wherein processing the sequence of characters comprises:

receiving the sequence of characters from the user interface at least one first sequence prediction based at least in part on a first model and a first evidence source, wherein the first evidence source comprises the sequence of characters, wherein each of the at least one first sequence prediction comprises a first sequence and a first associated probability estimate;

generating at least one second sequence prediction based on a second evidence source and a second model, wherein each of the at least one second sequence prediction comprises a second sequence and a second associated probability estimate;

wherein the first associated probability estimate and the second associated probability estimate are weighted according to a probability that the first model or the second model comprises a given context sequence;

combining the at least one first sequence prediction and the at least one second sequence prediction into at least one combined sequence prediction based at least in part on the first associated probability estimate and the second associated probability estimate; and

visually outputting, via the user interface, the at least one combined sequence prediction.

15. The non-transitory computer-readable storage medium according to claim 14, wherein the at least one first sequence prediction and the at least one second sequence prediction are combined into at least one combined sequence prediction by ranking the at least one first sequence prediction and the at least one second sequence prediction and removing duplicate sequence predictions, wherein, the first sequence prediction or the second sequence prediction of the duplicate sequence predictions is removed dependent on which of the first associated probability estimate and the second associated probability estimate is lowest.

16. The non-transitory computer-readable storage medium according to claim 14, wherein at least one of the first associated probability estimate or the second associated probability estimate are approximately normalised, wherein approximately normalising the first associated probability estimate or the second associated probability estimate comprises estimating a normalisation factor for the first associated probability estimate or the second associated probability estimate.

17. The non-transitory computer-readable storage medium according to claim 14, wherein at least one of the first sequence prediction or the second sequence prediction corresponds to an adjusted or corrected version of text input by a user into the user interface.

18. The non-transitory computer-readable storage medium according to claim 14, wherein the at least one combined sequence prediction is output via a display associated with the user interface only if for each combined sequence prediction, a probability estimate associated with the combined sequence prediction is greater than or equal to a first threshold estimate.

19. The non-transitory computer-readable storage medium according claim 18, further comprising inputting automatically the combined sequence prediction if the combined sequence prediction has a probability estimate greater than or above a second threshold estimate.