Virtual Keyboard System with Automatic Correction

• US 20110234524A1
• Filed: 03/25/2011
• Published: 09/29/2011
• Est. Priority Date: 12/22/2003
• Status: Active Grant

• Current Assignee: Cerence Operating Company (Cerence Inc.)
• Original Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Inventors: Longe, Michael R., Meurs, Pim Van
• Granted Patent: US 8,570,292 B2
• Time in Patent Office: Days
• US Class Current: 345/173
• CPC Class Codes: G06F 3/0237 using prediction or retrieval techniques
• CPC Class Codes: G06F 3/0238 Programmable keyboards key guide holders G06F3/0224
• CPC Class Codes: G06F 3/0488 using a touch-screen or digitiser, e.g. input of commands through traced gestures
• 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 3/0489 using dedicated keyboard keys or combinations thereof
• 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
• CPC Class Codes: G06F 40/40 Processing or translation of natural language natural language analysis G06F40/20; semantic analysis G06F40/30

Abstract

There is disclosed an enhanced text entry system which uses word-level analysis to automatically correct inaccuracies in user keystroke entries on reduced keyboards such as those implemented on a touch-sensitive panel or display screen, or on mechanical keyboard systems. A method and system are defined which determine one or more alternate textual interpretations of each sequence of inputs detected within a designated auto-correcting keyboard region.

Claims

1. A text entry system comprising:

a user input device comprising a touch sensitive surface including an auto-correcting keyboard region comprising a plurality of the characters of an alphabet, wherein each of the plurality of characters corresponds to a location with known coordinates in the auto-correcting keyboard region, wherein each time a user contacts the user input device within the auto-correcting keyboard region, a location associated with the user contact is determined and the determined contact location is added to a current input sequence of contact locations;

a nontransitory memory containing a plurality of objects, wherein each object is a string of one or a plurality of characters forming a word or a part of a word, wherein each object is further associated with a frequency of use;

an output device with a text display area; and

a processor coupled to the user input device, memory, and output device, said processor comprising;

a distance value calculation component which, for each determined contact location in the input sequence of contacts, calculates a set of distance values between the contact locations and the known coordinate locations corresponding to one or a plurality of characters within the auto-correcting keyboard region;

a word evaluation component which, for each generated input sequence, identifies one or a plurality of candidate objects in memory, and for each of the one or a plurality of identified candidate objects, evaluates each identified candidate object by calculating a matching metric based on the calculated distance values and the frequency of use associated with the object, and ranks the evaluated candidate objects based on the calculated matching metric values;

a word choice list component configured to display a word choice list on said output device, said word choice list comprising a list of an exact typing object composed of said determined corresponding characters in the order corresponding to the input sequence of contact locations and one or a plurality of candidate objects according to their evaluated ranking.

2. The text entry system of claim 1, wherein:

each of the plurality of objects in memory is further associated with one or a plurality of predefined groupings of objects; and

the word evaluation component, for each generated input sequence, limits the number of objects for which a matching metric is calculated by identifying one or a plurality of candidate groupings of the objects in memory, and for one or a plurality of objects associated with each of the one or a plurality of identified candidate groupings of objects, calculates a matching metric based on the calculated distance values and the frequency of use associated with each candidate object, and ranks the evaluated candidate objects based on the calculated matching metric values.

3. The system of claim 1, wherein the characters of the alphabet are arranged on the auto-correcting keyboard region in approximately a standard “

QWERTY”

layout.

4. The system of claim 1, wherein said auto-correcting keyboard region includes one or a plurality of known locations associated with one or a plurality of punctuation characters, wherein said memory includes one or a plurality of objects in memory which include one or a plurality of the punctuation characters associated with locations in said auto-correcting keyboard region.

5. The system of claim 1, wherein objects in memory are further associated with one or a plurality of modules, wherein each module comprises a set of objects with one or a plurality of common characteristics.

6. The system of claim 5, wherein the text entry system comprises a module selector whereby a user can determine which modules are to be evaluated by the word evaluation component in order to identify candidate objects.

7. The system of claim 5, wherein the plurality of modules comprises word stem modules and suffix modules, wherein each word stem module comprises a logical organization of uninflected word stem objects, and wherein each suffix module comprises a logical organization of suffixes which can be appended to word stems to form inflected words, whereby

each word stem module is associated with one or a plurality of suffix modules, whereby whenever the word evaluation component calculates a matching metric value for a given word stem in a given word stem module with respect to an initial sequence of contacts within an input sequence such that the calculated matching metric value ranks higher than a predetermined threshold, the word evaluation component evaluates the remaining contacts of the input sequence with respect to the associated suffix modules, whereby whenever the word evaluation component calculates a matching metric value for a given suffix in one of said associated suffix modules that ranks higher than a second predetermined threshold, said suffix is appended to said word stem to form a completed word corresponding to a matching metric value that is a function of said determined word stem matching metric value and said determined suffix matching metric value.

8. The system of claim 1, wherein the word evaluation component calculates the matching metric for each candidate object by summing the distance values calculated from each contact location in the input sequence to the location assigned to the character in the corresponding position of the candidate object, and applying a weighting function according to the frequency of use associated with the object.

9. The system of claim 8, wherein each character of the alphabet associated with the auto-correcting keyboard region is assigned a Cartesian coordinate and wherein the distance value calculation component calculates the distance between the contact location and the location corresponding to a character according to standard Cartesian coordinate distance analysis.

10. The system of claim 8, wherein each character of the alphabet associated with the auto-correcting keyboard region is assigned a Cartesian coordinate and wherein the distance value calculation component calculates the distance between the contact location and the location corresponding to a character as the square of the standard Cartesian coordinate distance.

11. The system of claim 8, wherein the frequency of use associated with each candidate object in memory comprises the ordinal ranking of the object with respect to other objects in memory, wherein an object associated with a higher relative frequency corresponds to a numerically lower ordinal ranking.

12. The system of claim 11, wherein the frequency weighting function applied by the word evaluation component to the summed distance values for a candidate object comprises multiplying the sum of the distance values by the base 2 logarithm of the ordinal ranking of the object.

13. The system of claim 8, wherein the word evaluation component adds an increment value to the sum of the distance values prior to applying a weighting function according to the frequency of use associated with the candidate object.

14. The system of claim 13, wherein the increment value is a fixed value that is approximately twice the average distance between adjacent locations on the auto-correcting keyboard region corresponding to characters.

15. The system of claim 2, wherein objects in memory are stored such that objects are classified into groupings comprising objects of the same length, wherein the word evaluation component limits the number of objects for which a matching metric is calculated by initially identifying candidate groupings of objects of the same length as the number of inputs in the input sequence, wherein if fewer than a threshold number of candidate objects are evaluated to have a matching metric score better than a threshold value, the word evaluation component identifies candidate groupings of objects of progressively longer lengths and calculates the matching metric for the objects in the identified groupings until said threshold number of candidate objects are evaluated to have a matching metric score better than said threshold, wherein the word evaluation component calculates the matching metric for each candidate object by summing the distance values calculated from each contact location in the input sequence to the location assigned to the character in the corresponding position of the candidate object and adding an increment value, and applying to this sum a weighting function according to the frequency of use associated with the object, and wherein the increment value added to the sum of the distance values is a value that is based on the difference between the number of characters in the candidate object and the number of inputs in the current input sequence.

16. The system of claim 2, wherein the word evaluation component calculates the matching metric for each candidate object by summing the distance values calculated from each contact location in the input sequence to the location assigned to the character in the corresponding position of the candidate object, and applying a weighting function according to the frequency of use associated with the object, wherein the frequency of use associated with each candidate object in memory comprises the ordinal ranking of the object with respect to other objects in one or a plurality of sub-groupings in memory with which said object is associated, wherein an object associated with a higher relative frequency corresponds to a numerically lower ordinal ranking, wherein for each calculated distance value between a contact location in the input sequence and the known coordinate location corresponding to a character within the auto-correcting keyboard region wherein said calculated distance exceeds a threshold distance value, for each object in memory in which said character occurs at a position in the sequence of the characters of said object corresponding to the position of said contact location in said input sequence, said object is ranked by the word evaluation component as an object that is excluded from presentation to the user for selection, wherein one or a plurality of the identified candidate groupings of the objects in memory comprise objects that are excluded from presentation to the user for selection, wherein at least one of the calculated distance values included in the calculated sum of distance values for each object in said one or identified candidate groupings of objects exceeds a threshold distance value, wherein the auto-correcting keyboard region is separated into two or more predefined clustering regions, each of which contains the known locations of one or a plurality of characters, and wherein each objects in memory is assigned to a predefined group according to which of said two or more predefined clustering regions contain the known locations corresponding to one or a plurality of the initial characters of said object, wherein the auto-correcting keyboard region is separated into three predefined clustering regions, and wherein each object in memory is assigned to one of nine predefined groupings based which of the three predefined clustering regions contain the known locations corresponding to each of the first two characters of said object.

17. The system of claim 1, wherein for each character corresponding to a known location in the auto-correcting keyboard region, a region is predefined around one or a plurality of said known locations wherein the distance between an input contact location falling within said predefined region and the known character location within said predefined region is calculated as a distance of zero, wherein the relative sizes of said predefined regions correspond to the relative frequencies of occurrence of the characters associated with the known locations within said predefined regions, wherein said predefined region around the known location of a character corresponds to a displayed key on the touch screen.

18. The system of claim 1, wherein at least one of the locations with known coordinates in the auto-correcting keyboard region corresponds to a plurality of characters, one or a plurality of which include various diacritic marks, wherein the plurality of characters comprise variant forms of a single base character, and wherein objects in memory are stored with their correct accented characters.

19. The system of claim 1, wherein the text entry system includes a delete key region associated with a delete function, wherein when the current input sequence includes at least one contact and said delete key region is contacted, the last input contact from the current input sequence of contacts is deleted, without terminating the current input sequence.

20. The system of claim 1, wherein the text entry system includes an Edit Word key region associated with an Edit Word function, wherein when no current input sequence exists and said Edit Word key region is contacted,

when the text insertion point in the text display area on the output device is contained within a previously output word, the system establishes a new current input sequence consisting of a sequence of contact locations corresponding to the coordinate locations associated with the characters of said word, and

when the text insertion point in the text display area on the output device is located between two previously output words, the system establishes a new current input sequence consisting of a sequence of contact locations corresponding to the coordinate locations associated with the characters of the word adjacent to the text insertion point, and

wherein the text entry system processes said new current input sequence and determines a corresponding ranking of new candidate objects, and

wherein selection of one of the new candidate objects replaces the previously output word used to establish said new current input sequence.