System and Method for Inputting Text into Electronic Devices

• US 20120029910A1
• Filed: 03/30/2010
• Published: 02/02/2012
• 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
• Granted Patent: US 9,659,002 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• 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-47. -47. (canceled)

48. 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 text input 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.

49. The system of claim 48, wherein the text predictions are generated concurrently from the plurality of language models in real time.

50. The system of claim 48, wherein the plurality of language models comprises a model of human language and at least one language model specific to an application.

51. The system of claim 50, wherein the plurality of language models comprises at least one additional language model.

52. The system as in any one of claims 48-51, further comprising a mechanism configured to compare a sequence of terms stored in a language model to a sequence of terms stored in one or more other language models and to remove duplicate or multiple entries by retaining only the most probable of the duplicate or multiple entries.

53. The system of claim 48, wherein the text prediction engine comprises a mechanism to combine the predictions generated by each language model.

54. The system of claim 53, wherein the mechanism is configured to insert the predictions into an ordered associative structure or a multimap structure and return the p most probable terms as the predictions for provision to the user interface.

55. The system of claim 48, wherein each of the plurality of 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.

56. The system of claim 55, wherein the language model 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.

57. The system of claim 56, wherein the language model 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.

58. The system of claim 57, wherein the language model 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 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.

59. A touch-screen interface that comprises:

a single or multi-character entry mechanism;

a word prediction pane; and

a typing pane to display inputted text.

60. The interface of claim 59, wherein the interface further comprises a menu button which toggles the screen between prediction, numbers and punctuation, and further punctuation screens.

61. The interface as in claim 59 or 60, further comprising a delete button and an undo button, the interface configured to undo a previous word selection in the typing pane by erasing the previous word selection from the typing pane and returning to a previous prediction pane in response to a press of the undo button or in response to a left-to-right gesture on the delete button.

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

receiving text input into a user interface;

generating concurrently, using a text prediction engine comprising a plurality of language models, text predictions from the plurality of language models; and

providing text predictions to the user interface for user selection.

63. The method of claim 62, wherein each of the plurality of 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.

64. The method of claim 63, wherein the language model comprises a mechanism to compute the intersection of the predictions determined by the approximate or probabilistic trie and the n-gram map, the method further comprising computing the intersection of the predictions.

65. The method of claim 64, wherein the language model comprises a Bloom filter which comprises an n+1 gram map, the method further comprising returning a new 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.

66. The method of claim 62, wherein the text prediction engine comprises a mechanism to combine the predictions generated from each language model among the plurality of language models, the method further comprising combining the predictions.

67. The method of claim 66, wherein combining the predictions comprises inserting the predictions into an ordered associative structure or a multimap structure, and returning the p most probable terms for provision to the user interface.