Spell-check for a keyboard system with automatic correction
AssigneeNuance Communications, Inc.
InventorsDavid KAY, Erland Unruh, Gaurav Tandon
Life of this patent
Estimating the term…
Abstract
An adaptation of standard edit distance spell-check algorithms leverages probability-based regional auto-correction algorithms and data structures for ambiguous keypads and other predictive text input systems to provide enhanced typing correction and spell-check features. Strategies for optimization and for ordering results of different types are also provided.
Claims23
A text input apparatus, comprising:
- a user input device comprising a 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 keyboard region, wherein when a user contacts the user input device within the keyboard region, one or more input values based on the contact locations are generated;
- a memory containing a vocabulary database comprising a dictionary containing entries;
- an output device with a text display area;
- and
- a processor that receives as an input sequence a series of one or more of said input values from said input device;
- said processor programmed to execute a set-edit-distance algorithm to calculate a matching metric between said input sequence and a candidate string, to access a database to retrieve one or more candidate strings, to calculate said set-edit-distance between said input sequence and a candidate string by comparing sets of possible characters corresponding to said input sequence with characters in the candidate string, and to output one or more candidate strings ranked by matching metric;
- wherein if a candidate string character is in a set of said sets of possible characters per input, set-edit-distance does not increase;
- and
- wherein if a candidate string character is not in said set of possible characters per input, set-edit-distance is increased according to a predetermined rule,
- said processor coupled to the user input device, memory, and output device.
A text input method, comprising the steps of:
- providing a user input device comprising a 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 keyboard region, wherein when a user contacts the user input device within the keyboard region, one or more input values based on the contact locations are generated;
- providing a memory containing a vocabulary database comprising a dictionary containing entries;
- providing an output device with a text display area;
- and
- providing a processor that receives as an input sequence a series of one or more of said input values from said input device;
- said processor programmed to execute a set-edit-distance algorithm to calculate a matching metric between said input sequence and a candidate string, to access a database to retrieve one or more candidate strings, to calculate said set-edit-distance between said input sequence and a candidate string by comparing sets of possible characters corresponding to said input sequence with characters in the candidate string, and to output one or more candidate strings ranked by matching metric;
- wherein if a candidate string character is in a set of said sets of possible characters per input, set-edit-distance does not increase;
- and
- wherein if a candidate string character is not in said set of possible characters per input, set-edit-distance is increased according to a predetermined rule,
- said processor coupled to the user input device, memory, and output device.
A computer-readable storage medium storing one or more sequences of instructions for inputting text, which instructions, when executed by one or more processors, cause the one or more processors to carry out the steps of:
- receiving as an input sequence a series of one or more of input values from an input device;
- executing a set-edit-distance algorithm to calculate a matching metric between said input sequence and a candidate string, to access a database to retrieve one or more candidate strings, to calculate said set-edit-distance between said input sequence and a candidate string by comparing sets of possible characters corresponding to said input sequence with characters in the candidate string, and to output one or more candidate strings ranked by matching metric;
- wherein when a candidate string character is in a set of said sets of possible characters per input, set-edit-distance does not increase;
- and
- wherein when a candidate string character is not in said set of possible characters per input, set-edit-distance is increased according to a predetermined rule.
Dependencies are inferred from the claim text.