Spell-check for a keyboard system with automatic correction

• US 8,225,203 B2
• Filed: 11/04/2010
• Issued: 07/17/2012
• Est. Priority Date: 02/01/2007
• Status: Active Grant

• Current Assignee: Cerence Operating Company (Cerence Inc.)
• Original Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Inventors: Unruh, Erland
• Primary Examiner(s): Nguyen, Maikhanh
• Application Number:
  US12/939,918
• Publication Number:
  US 20110193797A1
• Time in Patent Office: 621 Days
• Field of Search: 715/200, 715/205, 715/209, 715/227, 715/229, 715/231, 715/253, 715/254, 715/255, 715/256, 715/259, 715/260, 715/261, 715/273, 715/700, 715/762, 715/771, 715/773, 715/831, 704/1, 704/9, 704/10, 704/239, 704/240, 704/257, 345/170, 345/171, 345/172, 345/173
• US Class Current: 715/255
• CPC Class Codes: G06F 3/0233 Character input methods
• CPC Class Codes: G06F 3/0237 using prediction or retrieval techniques
• CPC Class Codes: G06F 3/04883 for inputting data by handwriting, e.g. gesture or text
• 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/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

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.

Claims

1. A text input apparatus, comprising:

a display including a touch sensitive display surface;

digital data storage containing a vocabulary database including multiple vocabulary entries; and

coupled to the display and the storage, a processor programmed to perform operations comprising;

directing the display to show an arrangement of keys, each key representing one or more characters;

via the display surface, receiving user input comprising a single continuous trace contacting multiple of the keys in an order, including a start key, an end key, and any intervening keys between the start key and the end key;

defining an input sequence including the contacted keys and also including any auxiliary keys comprising keys exhibiting prescribed proximity to the contacted keys;

comparing the input sequence to candidate entries from the vocabulary, including the following operations for each candidate entry;

computing a set-edit-distance metric to calculate a matching metric between said input sequence and the candidate entry;

where;

the set-edit-distance computation imposes a penalty for, omitting from the candidate word all keys from a first group comprising the start key and auxiliary keys to the start key;

the set-edit-distance computation imposes a penalty for omitting from the candidate word all keys from a second group comprising the end key and auxiliary keys to the end key;

the set-edit-distance computation imposes a penalty for omitting from the candidate word all keys from a third group comprising any contacted keys and their auxiliaries where at least a prescribed minimum change in direction of the trace occurs;

the set-edit-distance computation does not impose any penalty for omitting from the candidate word any key of the input sequence outside all of the first, second, and third groups; and

the set-edit-distance computation does not impose any penalty for using any key in the input sequence twice or more in succession in the candidate word; and

ranking the candidate words according to criteria including at least the computed set-edit-distance metric, and providing an output of at least some of the ranked candidate words.

2. The apparatus of claim 1, where:

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.

3. The apparatus of claim 1, where:

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.

4. The apparatus of claim 3, where:

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.

5. The apparatus of claim 3, where:

the keyboard-geometry-based probability of a given key varies with radius of the key from a point on the trace.

6. The apparatus of claim 3, where:

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.

7. The apparatus of claim 1, where:

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.

8. The apparatus 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.

9. The apparatus 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.

10. A method, comprising operations of:

directing a display to show an arrangement of keys, each key representing one or more characters, where the display includes a touch sensitive surface;

via the display surface, receiving user input comprising a single continuous trace contacting multiple of the keys in an order, including a start key, an end key, and any intervening keys between the start key and the end key;

defining an input sequence including the contacted keys and also including any auxiliary keys comprising keys exhibiting prescribed proximity to the contacted keys;

comparing the input sequence to candidate entries from a vocabulary containing multiple vocabulary entries, the comparing operation including the following operations for each candidate entry;

computing a set-edit-distance metric to calculate a matching metric between said input sequence and the candidate entry;

where;

the set-edit-distance computation imposes a penalty for omitting from the candidate word all keys from a first group comprising the start key and auxiliary keys to the start key;

the set-edit-distance computation imposes a penalty for omitting from the candidate word all keys from a second group comprising the end key and auxiliary keys to the end key;

the set-edit-distance computation imposes a penalty for omitting from the candidate word all keys from a third group comprising any contacted keys and their auxiliaries where at least a prescribed minimum change in direction of the trace occurs;

the set-edit-distance computation does not impose any penalty for omitting from the candidate word any key of the input sequence outside all of the first, second, and third groups; and

the set-edit-distance computation does not impose any penalty for using any key in the input sequence twice or more in succession in the candidate word; and

ranking the candidate words according to criteria including at least the computed set-edit-distance metric, and providing an output of at least some of the ranked candidate words;

where at least one of the operations is performed by a processor.

11. The method of claim 10, where:

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.

12. The method of claim 10, where:

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.

13. The method of claim 12, where:

for each of the intervening keys, the keyboard-geometry-based probability is reduced according to speed at which the trace passed over the intervening key.

14. The method of claim 12, where:

the keyboard-geometry-based probability of a given key varies with radius of the key from a point on the trace.

15. The method of claim 12, where:

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.

16. The method of claim 10, where:

the ranking operation is conducted so as to rank candidate words according to criteria including set-edit-distance metric and a language-model-based probability.

17. The method of claim 10, 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.

18. The method of claim 10, where the operations further include:

computing stem-edit-distance and using the computed stem-edit-distance to break ties between similarly ranked candidate words.

19. 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 10.