USER INPUT PREDICTION

• US 20140351741A1
• Filed: 07/25/2014
• Published: 11/27/2014
• 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 William, Osbourne, Joseph Hayyim Benedict
• Granted Patent: US 10,037,319 B2
• Time in Patent Office: Days
• US Class Current: 715/773
• CPC Class Codes: G06F 3/0237 using prediction or retrieval techniques
• 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/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs

Abstract

A system for inputting text into an electronic device. The system comprises a candidate generator (2) configured to generate one or more candidates from an input sequence (20). The input sequence (20) comprises a contiguous sequence of characters. Each candidate comprises two or more terms separated by one or more term boundaries. The candidate generator (2) is configured to assign a first probability estimate to each candidate by: searching for one or more terms of that candidate in a context language model, wherein the context language model comprises sequences of terms, each sequence of terms having a corresponding probability of occurring; and assigning the probability corresponding to the one or more terms of that candidate from the context language model to the candidate. The candidate generator (2) is configured to discard one or more candidates on the basis of the corresponding first probability estimates. There is provided a corresponding method of inferring term boundaries in a user input sequence.

Claims

1. A system comprising:

a processor;

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

generate one or more candidates from an input sequence, the input sequence comprising a contiguous sequence of characters, wherein each candidate comprises two or more terms separated by one or more term boundaries;

search for one or more terms of each candidate in stored sequences of terms, each sequence of terms having a corresponding probability of occurring; and

assign a probability to each candidate based on the search.

2. The system of claim 1, wherein the memory stores instructions that, when executed by the processor, configure the processor to generate a subset of the one or more candidates based on the probability assigned to each candidate.

3. The system of claim 2, wherein the one or more terms comprises the candidate.

4. The system of claim 3, wherein the memory stores instructions that, when executed by the processor, configure the processor to search in the stored sequences for a sequence comprising a context sequence in combination with each candidate, wherein the context sequence is user inputted text that precedes the input sequence and comprises one or more terms separated by one or more term boundaries.

5. The system of claim 4, wherein the memory stores instructions that, when executed by the processor, configure the processor to convert user input signals into an input sequence and a context sequence.

6. The system of claim 2, wherein the processor converts the user input signals into an input sequence by generating a sequence of sets of characters, each set of characters having a probability distribution over the characters in the set, such that there is a probability value associated with each character in each set.

7. The system of claim 6, wherein the processor generates one or more candidates from an input sequence by converting the input sequence into a graph comprising one or more paths, wherein the one or more paths correspond to the one or more candidates.

8. The system of claim 7, wherein the graph comprises a collection of nodes and directed edges, each edge connecting one node to another, wherein in the graph each character of each set of characters is assigned a node, the incoming edge for each node corresponding to the probability for the associated character.

9. The system of claim 8, wherein the processor is configured to insert one or more term boundary nodes into the graph, each of the one or more term boundary nodes having a probability of occurring in the input sequence.

10. The system of claim 9, wherein the processor is configured to insert a term boundary node between any two neighbouring nodes which correspond to any two neighbouring sets of characters of the input sequence.

11. The system of claim 9, wherein the processor is configured to insert a term boundary node as an alternative to any node that represents a set of characters of the input sequence.

12. The system of claim 8, wherein the processor is configured to insert one or more wildcard nodes into the graph, each of the one or more wildcard nodes enabling any character to be inserted into the graph in addition to the sets of characters of the input sequence.

13. The system of claim 7, wherein the processor is configured to generate a second probability estimate for the candidate by determining the cumulative probability of the path through the graph that represents that candidate.

14. The system of claim 13, wherein the processor is configured to combine first and second probabilities for each candidate, and include a candidate in the subset of one or more candidates if

a ratio of the combined probability for the most probable candidate and the candidate in question is above a threshold value.

15. The system of claim 14, wherein the processor is configured to determine a third probability for any candidate of the subset, wherein the third probability is determined by searching in the stored sequences for a sequence comprising a context sequence, and optionally valid orthographic and lexical variations thereof, in combination with the candidate, wherein the context sequence is user inputted text that precedes the input sequence and comprises one or more terms separated by one or more term boundaries.

16. The system of claim 15, wherein the overall probability of a candidate is the product of the second and third probabilities.

17. The system of claim 16, wherein the processor is configured to output one or more of the most probable candidates of the subset to a candidate display for presentation to a user.

18. The system of claim 1, wherein the processor is configured to output at least one of the one or more candidates to a display for presentation to a user.

19. The system of claim 1, wherein the term boundary is a space character.

20. A method of inferring term boundaries in an input sequence comprising a contiguous sequence of characters, the method comprising:

generating one or more candidates from the input sequence, wherein each candidate comprises two terms separated by one or more term boundaries;

searching, using a processor, for one or more terms of each candidate in stored sequences of terms, each sequence of terms having a corresponding probability of occurring; and

assigning a probability to each candidate based on the search.

21. The method of claim 20, further comprising generating a subset of the one or more candidates based on the corresponding probability assigned to each candidate.

22. The method of claim 21, wherein the one or more terms comprises the candidate, and for each candidate, the step of searching for the candidate in the stored sequences comprises searching for a sequence comprising a context sequence in combination with the candidate, wherein the context sequence is user inputted text that precedes the input sequence and comprises one or more terms separated by one or more term boundaries.

23. The method of claim 20, wherein the term boundary is a space character.

24. A system comprising:

a processor;

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

generate one or more candidates from an input sequence, the input sequence comprising a contiguous sequence of characters, wherein each candidate comprises two or more terms separated by one or more term boundaries;

wherein the processor generates one or more candidates from the input sequence by being configured to;

convert the input sequence into a graph comprising one or more paths; and

insert one or more term boundaries into the graph, between two neighbouring characters of the input sequence,

wherein the one or more paths of the graph correspond to the one or more candidates.

25. The system of claim 24, wherein the graph comprises a collection of nodes and directed edges, each edge connecting one node to another, wherein each character is assigned a node, the incoming edge for each node corresponding to the probability for the associated character.

26. The system of claim 25, wherein the graph is a representation of a prefix tree, and the prefix tree of terms comprises one or more nodes representing the last letter of a completed word, wherein when generating the prefix tree of terms, the processor is configured to insert a node corresponding to a space character into the prefix tree where there is a node corresponding to the last letter in a word.

27. The system of claim 26, wherein the processor is configured to generate at the node corresponding to the space character, a new prefix tree of terms generated by retaining the terms of a dictionary prefix tree which are allowed given the remaining characters of the contiguous sequence of characters.

28. The system of claim 24, wherein the processor is configured to convert user input signals into an input sequence by generating a sequence of sets of characters, each set of characters having a probability distribution over the characters in the set, such that there is a probability value associated with each character in each set.

29. A user interface comprising:

a text pane configured to display text that is currently being entered by a user;

a prediction pane to display a text prediction;

a virtual keyboard for accepting text entered by a user, wherein the keyboard does not include a key corresponding to a term boundary, and optionally a space.

30. The user interface of claim 29, wherein the prediction pane comprises two or more prediction panes, the two or more prediction panes comprising a first prediction pane displaying the user input sequence and a second prediction pane displaying a text prediction for that user input sequence.