Virtual Keyboard Systems with Automatic Correction

Abstract

There is disclosed an enhanced text entry system which uses word-level analysis to correct inaccuracies automatically in user keystroke entries on reduced-size or virtual keyboards. 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 region. The actual interaction locations for the keystrokes may occur outside the boundaries of the specific keyboard key regions associated with the actual characters of the word interpretations proposed or offered for selection, where the distance from each interaction location to each corresponding intended character may in general increase with the expected frequency of the intended word in the language or in a particular context. Likewise, in a virtual keyboard system, the keys actuated may differ from the keys actually associated with the letters of the word interpretations. Each such sequence corresponds to a complete word, and the user can easily select the intended word from among the generated interpretations. Additionally, when the system cannot identify a sufficient number of likely word interpretation candidates of the same length as the input sequence, candidates are identified whose initial letters correspond to a likely interpretation of the input sequence.

1 . A text entry system comprising: 
 a user input device comprising: 
 an auto-correcting keyboard region comprising a plurality of the characters of a character set, wherein locations having known coordinates in the auto-correcting keyboard region are associated with one or more of the character set members, wherein a location is determined when a user interacts with the user input device within the auto-correcting keyboard region and the determined interaction location is added to a current input sequence; and  
 one or more additional interaction locations associated with one or more characters of said character set, wherein a character set member is determined when a user interacts with one of said locations and a representation of the determined character set member is added to said current input sequence,  
   memory containing a plurality of objects, wherein one or more objects comprise a string of one or a plurality of characters forming all or part of a word or phrase;    an output device and    a processor coupled to the user input device, memory, and output device, said processor comprising: 
 a distance value calculation component which, for a determined interaction location in said current input sequence, calculates a set of distance values between the interaction location and the known coordinate locations corresponding to one or a plurality of characters within the auto-correcting region;  
 an object evaluation component which, for said current input sequence, identifies one or a plurality of candidate objects in memory, and for one or more identified candidate objects, evaluates identified candidate objects by calculating a matching metric based on the calculated distances and any determined character set members and ranks the evaluated candidate objects based on the calculated matching metric values; and  
 a selection component for identifying candidate objects according to their evaluated ranking, presenting any identified objects to the user, and enabling the user to select one of the presented objects for output to the output device.  
   
     
     
         2 . The system of  claim 1 , wherein one or more of the plurality of objects in said memory is further associated with one or a plurality of predefined groupings of objects.  
     
     
         3 . The system of  claim 1 , wherein one or more of the plurality of objects in said memory are further associated with one or a plurality of modules, wherein each module comprises or generates a set of objects having one or a plurality of common characteristics.  
     
     
         4 . The system of  claim 1 , wherein one or more of the plurality of objects in said memory is further associated with a promotion value.  
     
     
         5 . The system of  claim 4  said object evaluation component further comprising: 
 a method for applying a weighting function according to the promotion value.    
     
     
         6 . The system of  claim 1 , wherein the character set members are arranged on the auto-correcting keyboard region in approximately alphabetic order for a language.  
     
     
         7 . The system of  claim 1 , wherein the character set members are arranged on the auto-correcting keyboard region in approximately any standard keyboard layout.  
     
     
         8 . The system of  claim 1 , wherein the auto-correcting keyboard region comprises one or a plurality of known locations associated with one or a plurality of punctuation characters and/or diacritic marks, and wherein the memory comprises one or a plurality of objects which include one or a plurality of the punctuation characters and/or diacritic marks associated with locations in said region.  
     
     
         9 . The system of  claim 1 , further comprising: 
 means for providing feedback to the user identifying the character set members near a current interaction location.    
     
     
         10 . The system of  claim 9 , wherein the feedback is presented visually on the output device and one or more character set members corresponding to known locations closest to the current interaction location are indicated by one or more of: size, color, background shading, and font attribute.  
     
     
         11 . The system of  claim 1 , wherein the user input device further comprises means for changing some or all of the auto-correcting keyboard region to a determined key state, wherein a character set member is determined when a user interacts with one of the keys in the changed region and a representation of the determined character set member is added to said current input sequence.  
     
     
         12 . The system of  claim 1 , wherein the word evaluation component determines for a determined interaction location in said current input sequence, a closest known location corresponding to a character set member, and constructs an exact typing object composed of said corresponding and other determined character set members in an order corresponding to said current input sequence.  
     
     
         13 . The system of  claim 1 , wherein the selection component identifies a highest ranked candidate object and presents the identified object on the output device.  
     
     
         14 . The system of  claim 13 , wherein the selection component presents the identified object on the output device at or near the current interaction location.  
     
     
         15 . The system of  claim 13 , further comprising a user input region or device that is associated with an object selection function, wherein an interaction with said device replaces the object presented on the output device with a next highest ranked object of the identified one or a plurality of candidate objects.  
     
     
         16 . The system of  claim 1 , wherein the set of distance values calculated by the distance value calculation component are weighted or scaled based on any of: 
 the calculated distance from the determined interaction location to the known coordinate location corresponding to each character set member relative to a determined value, said calculated distance relative to the shortest distance to a known coordinate location corresponding to a character set member, and a promotion value associated with each character set member.    
     
     
         17 . The system of  claim 16 , wherein the word evaluation component calculates the matching metric for each candidate object based on the product of the distance values calculated for each character set member in the corresponding position of the candidate object.  
     
     
         18 . The system of  claim 17 , wherein ranking of the evaluated candidate objects by the word evaluation component is a function of their calculated matching metric value and the product of the most significant distance values of the sets calculated for all of the determined interaction locations in said current input sequence.  
     
     
         19 . The system of  claim 17 , wherein ranking of the evaluated candidate objects by the word evaluation component is a function of the calculated matching metric value and an associated promotion value.  
     
     
         20 . The system of  claim 1 , wherein for a character set member corresponding to a known coordinate location in the auto-correcting region, a region is predefined around one or a plurality of said known coordinate locations, wherein the distance between an input interaction location failing within said predefined region and the known coordinate location within said predefined region is calculated as a distance of zero.  
     
     
         21 . The system of  claim 1 , wherein at least one of the locations with known coordinates in the auto-correcting region corresponds to a plurality of characters of a character set, one or a plurality of which comprise at least one diacritic mark, wherein the plurality of character set members comprise variant forms of another character set member and wherein objects in memory contain said variant forms.  
     
     
         22 . The system of  claim 1 , wherein a candidate is selected through an alternate input modality.  
     
     
         23 . The system of  claim 1 , wherein user inputs for said current input sequence are provided through a combination of different modalities.  
     
     
         24 . The system of  claim 1 , wherein the selection component detects a distinctive manner of selection that is used to select a candidate object, wherein upon detecting that an object has been selected through said distinctive manner, the system replaces a current input sequence with an input sequence composed of representations of the determined characters comprising the selected object; and wherein a next interaction in the auto-correcting region is appended to the current input sequence.  
     
     
         25 . The system of  claim 24 , wherein said distinctive manner of selection eliminates all candidates except those candidates that incorporate said selected object.  
     
     
         26 . The system of  claim 1 , wherein the processor further comprises: 
 a frequency promotion component for adjusting a promotion value associated with each object in memory as a function of the number of times the object is selected by the user for output on the output device.    
     
     
         27 . The system of  claim 26 , wherein the frequency promotion component analyzes additional information files that are accessible to the text entry system to identify new objects contained in said files that are not included among the objects already in said memory of said text entry system; and wherein said newly identified objects are added to the objects in memory.  
     
     
         28 . The system of  claim 1 , wherein one or a plurality of objects in memory are associated with a secondary object in memory, and wherein when the selection component identifies one of said objects for presentation to the user based on the matching metric calculated by the word evaluation component, the selection component presents the associated secondary object for selection.  
     
     
         29 . The system of  claim 1 , wherein the user input device comprises any of: 
 a mouse, a trackball, a trackpad, a joystick, an eye- or body-movement tracking device, and a device for decoding brainwaves.    
     
     
         30 . The system of  claim 1 , further comprising: 
 a linguistic model comprising any of. 
 frequency of occurrence of a linguistic object in formal or conversational written text;  
 frequency of occurrence of a linguistic object when following a preceding linguistic object or linguistic objects;  
 proper or common grammar of the surrounding sentence;  
 application context of current linguistic object entry; and  
 frequency of use or repeated use of the linguistic object by the user or within an application program.  
   
     
     
         31 . A text entry system comprising: 
 a user input device comprising a virtual keyboard including an auto-correcting region comprising a plurality of the characters of a character set, wherein one or more of the plurality of characters corresponds to a location with known coordinates in the auto-correcting region, wherein a location associated with the user interaction is determined when a user interacts with the user input device within the auto-correcting region, and the determined interaction location is added to a current input sequence of interaction locations;    a memory containing a plurality of objects, wherein one or more objects comprise a string of one or a plurality of characters forming all or part of a word or phrase;    an output device; and    a processor coupled to the user input device, memory, and output device, said processor comprising: 
 an object evaluation component which, for the current input sequence, identifies and ranks one or a plurality of candidate objects in memory, using information regarding both preceding and succeeding user interactions; and  
 a selection component for organizing said one or a plurality of candidate objects according to their evaluated ranking, presenting one or more of the objects to the user, and enabling the user to select one of the presented objects for output to the output device.  
   
     
     
         32 . The system of  claim 31  wherein one or more of the plurality of objects in said memory is further associated with one or a plurality of predefined groupings of objects.  
     
     
         33 . The system of  claim 31 , wherein one or more of the plurality of objects in said memory are further associated with one or a plurality of modules, wherein each module comprises or generates a set of objects having one or a plurality of common characteristics.  
     
     
         34 . The system of  claim 31  wherein one or more of the plurality of objects in said memory is further associated with a promotion value.  
     
     
         35 . The system of  claim 34 , said object evaluation component further comprising: 
 a method for applying a weighting function according to the promotion value.    
     
     
         36 . The system of  claim 31 , wherein the character set members are arranged on the auto-correcting keyboard region in approximately alphabetic order for a language.  
     
     
         37 . The system of  claim 31 , wherein the character set members are arranged on the auto-correcting keyboard region in approximately any standard keyboard layout.  
     
     
         38 . The system of  claim 31 , wherein the auto-correcting keyboard region comprises one or a plurality of known locations associated with one or a plurality of punctuation characters and/or diacritic marks, and wherein the memory comprises one or a plurality of objects which include one or a plurality of the punctuation characters and/or diacritic marks associated with locations in said region.  
     
     
         39 . The system of  claim 31 , further comprising: 
 means for providing feedback to the user identifying the character set members near a current interaction location.    
     
     
         40 . The system of  claim 39 , wherein the feedback is presented visually on the output device and one or more character set members corresponding to known locations closest to the current interaction location are indicated by one or more of: size, color, background shading, and font attribute.  
     
     
         41 . The system of  claim 31 , wherein the user input device further comprises means for changing some or all of the auto-correcting keyboard region to a determined key state, wherein a character set member is determined when a user interacts with one of the keys or with a known location in the changed region and a representation of the determined character set member is added to the current input sequence.  
     
     
         42 . The system of  claim 31 , wherein the object evaluation component determines, for a determined interaction location in an input sequence, a closest known location corresponding to a character set member, and constructs an exact typing object composed of said corresponding character set members in an order corresponding to the input sequence.  
     
     
         43 . The system of  claim 31 , wherein the selection component identifies a highest ranked candidate object and presents the identified object on the output device.  
     
     
         44 . The system of  claim 43 , wherein the selection component presents the identified object on the output device at or near the current interaction location.  
     
     
         45 . The system of  claim 43 , further comprising a user input region or device that is associated with an object selection function, wherein an interaction with said device replaces the object presented on the output device with a next highest ranked object of the said one or a plurality of candidate objects.  
     
     
         46 . The system of  claim 31 , wherein for a character set member corresponding to a known coordinate location in the auto-correcting region, a region is predefined around one or a plurality of said known coordinate locations, wherein any user interaction location within said predefined region is determined as occurring at a known coordinate location.  
     
     
         47 . The system of  claim 31 , wherein at least one of the locations with known coordinates in the auto-correcting region corresponds to a plurality of characters of a character set, one or a plurality of which comprise at least one diacritic mark, wherein the plurality of character set members comprise variant forms of another character set member and wherein objects in memory contain said variant forms.  
     
     
         48 . The system of  claim 31 , wherein a candidate is selected through an alternate input modality.  
     
     
         49 . The system of  claim 31 , wherein user inputs for the current input sequence are provided through a combination of different modalities.  
     
     
         50 . The system of  claim 31 , wherein the selection component detects a distinctive manner of selection that is used to select a candidate object, wherein upon detecting that an object has been selected through said distinctive manner, the system replaces a current input sequence of actual interaction locations with an input sequence of interaction locations corresponding to the coordinate locations of the character set members comprising the selected object; and wherein a next interaction in the auto-correcting region is appended to the current input sequence.  
     
     
         51 . The system of  claim 50 , wherein said distinctive manner of selection eliminates all candidates except those candidates that incorporate said selected object.  
     
     
         52 . The system of  claim 31 , wherein the processor further comprises 
 a frequency promotion component for adjusting a promotion value associated with each object in memory as a function of the number of times the object is selected by the user for output on the output device.    
     
     
         53 . The system of  claim 52 , wherein the frequency promotion component analyzes additional information files that are accessible to the text entry system to identify new objects contained in said files that are not included among the objects already in said memory of said text entry system; and wherein said newly identified objects are added to the objects in memory.  
     
     
         54 . The system of  claim 31 , wherein the user input device comprises any of, a mouse, a trackball, a trackpad, a joystick, and a device for decoding brainwaves.  
     
     
         55 . A text entry system, comprising: 
 a user input device comprising a keyboard including an auto-correcting region comprising a plurality of the characters of a character set, wherein one or more of the plurality of characters corresponds to a location with known coordinates in the auto-correcting region, wherein a location associated with the user interaction is determined when a user interacts with the user input device within the auto-correcting region, and the determined interaction location is added to a current input sequence of interaction locations,    a memory containing a plurality of objects, wherein one or more objects comprise a string of one or a plurality of characters forming all or part of a word or phrase;    an output device, and    a processor coupled to the user input device, memory, and output device, said processor comprising: 
 an evaluation component which uses information regarding both preceding and succeeding user interactions in the current input sequence and the plurality of objects in said memory to determine an intended character for each user interaction and  
 a selection component for presenting to the user one or more sequences of characters, some or all of each sequence of characters corresponding to the current input sequence, and enabling the user to select one sequence of characters for output to the output device.