VIRTUAL KEYBOARD SYSTEM WITH AUTOMATIC CORRECTION

• US 20140052437A1
• Filed: 10/25/2013
• Published: 02/20/2014
• Est. Priority Date: 05/27/1999
• Status: Active Grant

• Current Assignee: Cerence Operating Company (Cerence Inc.)
• Original Assignee: Tegic Communications, Inc. (Microsoft Corporation)
• Inventors: LONGE, Michael R., VAN MEURS, Pim
• Granted Patent: US 9,400,782 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• 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:

an auto-correcting keyboard region comprising a plurality of the characters of an alphabet, each of said characters having a contact location within said auto-correcting keyboard region,

a word evaluation component which identifies at least one candidate object, and for any identified candidate object, evaluates said identified candidate object by calculating a matching metric;

wherein when the word evaluation component calculates a matching metric value for a given word stem with respect to an initial sequence of contacts within an input sequence that ranks higher than a predetermined threshold, the word evaluation component evaluates remaining contacts of the input sequence with respect to at least one associated suffix that can be appended to said given word stem to form at least one inflected word, and

wherein when the word evaluation component calculates a matching metric value for a given suffix that ranks higher than a second predetermined threshold, said suffix is appended to said word stem to form a completed word.

2. 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.

3. The system of claim 1, wherein the word evaluation component calculates the matching metric for each candidate object by summing 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 a frequency of use associated with the object.

4. The system of claim 3, wherein each character of the alphabet associated with the auto-correcting keyboard region is assigned a Cartesian coordinate and wherein a 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.

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

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

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

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

9. The system of claim 1, wherein each character corresponds 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 a known character location within said predefined region is calculated as a distance of zero, wherein the relative sizes of said predefined regions correspond to relative frequencies of occurrence of characters associated with known locations within said predefined regions.

10. The system of claim 1, further comprising:

a word choice list component configured to display a word choice list comprising one or more typing objects corresponding to characters of a completed word.

11. The system of claim 1, further comprising:

a plurality of modules comprising 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;

wherein each word stem module is associated with one or a plurality of suffix modules;

wherein 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; and

wherein 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.

12. The system of claim 1, further comprising:

said word evaluation component limiting a 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.

13. 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 a frequency of use associated with the object;

wherein the frequency of use associated with each candidate object comprises an ordinal ranking of the object with respect to other objects in one or a plurality of sub-groupings 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 in which said calculated distance exceeds a threshold distance value, for each object 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 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;

wherein each object 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 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.

14. 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; and

wherein said predefined region around the known location of a character corresponds to a displayed key on the touch screen.

15. 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 are stored with their correct accented characters.

16. The system of claim 1, further comprising:

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.

17. The system of claim 1, further comprising:

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 a text insertion point in the text display area on the output device is contained within a previously output word, a new current input sequence is established consisting of a sequence of contact locations corresponding to the coordinate locations associated with the characters of said word;

when the text insertion point in the text display area on the output device is located between two previously output words, a new current input sequence is established 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;

wherein said new current input sequence is processed and a corresponding ranking of new candidate objects is determined; and

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