Spell-check for a keyboard system with automatic correction

Abstract

User input is received, specifying a continuous traced path across a keyboard presented on a touch sensitive display. An input sequence is resolved, including traced keys and auxiliary keys proximate to the traced keys by prescribed criteria. For each of one or more candidate entries of a prescribed vocabulary, a set-edit-distance metric is computed between said input sequence and the candidate entry. Various rules specify when penalties are imposed, or not, in computing the set-edit-distance metric. Candidate entries are ranked and displayed according to the computed metric.

1 . A method, comprising operations of:
 receiving user input specifying a continuous traced path across a keyboard presented on a touch sensitive display;   resolving an input sequence of traced keys and auxiliary keys proximate to the traced keys by prescribed criteria;   for each of one or more candidate entries of a prescribed vocabulary, computing a set-edit-distance metric between said input sequence and the candidate entry; and   ranking candidate entries according to the computed set-edit-distance metrics, and displaying an output of some or all of the ranked candidate entries;   where at least one of the operations is performed by a processor.   
     
     
         2 . The method of  claim 1 , wherein the set-edit-distance computation imposes a penalty for omitting from the candidate entry all keys from a first group comprising a start key of the path and auxiliary keys to the start key. 
     
     
         3 . The method of  claim 1 , wherein the set-edit-distance computation imposes a penalty for omitting from the candidate entry all keys from a second group comprising an end key of the path and auxiliary keys to the end key. 
     
     
         4 . The method of  claim 1 , wherein the set-edit-distance computation imposes a penalty for omitting from the candidate entry all keys from a third group comprising any traced keys and their auxiliaries where at least a prescribed minimum change in direction of the path occurs. 
     
     
         5 . The method of  claim 1 , wherein the set-edit-distance computation does not impose any penalty for omitting from the candidate entry any key of the input sequence outside all of a first group comprising a start key of the path and auxiliary keys to the start key, a second group comprising an end key of the path and auxiliary keys to the end key, and a third group comprising any traced keys and their auxiliaries where at least a prescribed minimum change in direction of the path occurs. 
     
     
         6 . The method of  claim 1 , wherein the set-edit-distance computation does not impose any penalty the candidate entry using any key in the input sequence twice or more in succession. 
     
     
         7 . The method of  claim 1 , wherein:
 the set-edit-distance computation does not impose any penalty for a candidate word including characters of a prescribed group comprising any of:
 punctuation, digits, and symbols. 
   
     
     
         8 . The method of  claim 1 , wherein:
 the operations further include computing a keyboard-geometry-based probability in association with each computed set-edit-distance metric, using the computed probability to break ties between similarly ranked candidate words.   
     
     
         9 . The method of  claim 8 , wherein:
 for each of the intervening keys, the keyboard-geometry-based probability is reduced according to speed at which the traced passed over the intervening key.   
     
     
         10 . The method of  claim 8 , wherein:
 the keyboard-geometry-based probability of a given key varies with radius of the key from a point on the trace.   
     
     
         11 . The method of  claim 8 , wherein:
 the keyboard-geometry-based probability of a given key varies according to area of the given key intersecting a prescribed rectangular touch area centered upon a contacted key nearest to the given key.   
     
     
         12 . The method of  claim 1 , wherein:
 the ranking operation is conducted so as to rank candidate words according criteria including the set-edit-distance metric and a language-model-based probability.   
     
     
         13 . The method of  claim 1 , where the operations further include:
 tracking free cost adds and deletes and using the tracked free cost adds and deletes to break ties between similarly ranked candidate words.   
     
     
         14 . The method of  claim 1 , where the operations further include:
 computing stem-edit-distance and using the computed stem-edit-distance to break ties between similarly ranked candidate words.   
     
     
         15 . An apparatus comprising a touch sensitive display coupled to a processor, the processor programmed to perform operations of  claim 1 . 
     
     
         16 . An article of manufacture comprising at least one medium of digital data storage containing non-transitory storage of a program executable by a processor to perform the operations of  claim 1 . 
     
     
         17 . A method, comprising the operations of:
 performing, by a processor coupled to a display, a user input device comprising a keypad of multiple keys, or a touch sensitive display surface, and a digital data storage containing a vocabulary database including multiple vocabulary entries, the operations comprising:
 via the user input device, receiving user input comprising a sequence of keys comprising one of the following: keys contacted and proximate to a continuous trace entered via touch sensitive display surface, or pressed keypad keys where one or more of the pressed keypad keys concurrently represents multiple characters; 
 identifying different candidate words each representing a combination of characters potentially represented by the sequence of keys; 
 comparing the candidate words to entries of the vocabulary to score the compared vocabulary entries accordingly to likelihood of representing the user input; and 
 where the comparing operation avoids penalizing any vocabulary entry that includes any of the following that is not present in the input sequence: punctuation, symbols, digits, repetition of any character represented on a key of the user input, use of multiple characters represented together on one key of the user input.