Spell-check for a keyboard system with automatic correction

• US 9,092,419 B2
• Filed: 05/18/2012
• Issued: 07/28/2015
• Est. Priority Date: 02/01/2007
• Status: Expired due to Fees

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Inventors: Kay, David, Unruh, Erland, Tandon, Gaurav
• Primary Examiner(s): Huynh, Cong-Lac
• Application Number:
  US13/475,736
• Publication Number:
  US 20120254744A1
• Time in Patent Office: 1,166 Days
• Field of Search: 715/257
• US Class Current: 1/1
• CPC Class Codes: G06F 3/0237 using prediction or retrieval techniques
• 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

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.

Claims

1. 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 the 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.

2. The apparatus of claim 1, wherein said processor performs incremental filtering and regional/probability calculations on said list of candidate matches.

3. The apparatus of claim 1, wherein said set-edit-distance algorithm assigns one discrete value to a word no matter what single letter in the word is wrong or how wrong it is.

4. The apparatus of claim 1, wherein said set-edit-distance algorithm uses word frequency as a factor in determining a word match.

5. The apparatus of claim 1, wherein said set-edit-distance algorithm uses regional-correction probabilities to determine a most likely word given the rest of the letter matches and/or word frequency.

6. The apparatus of claim 1, said processor further comprising:

a component for tuning the ordering of words in the selection list to mirror the intent or entry style of the user.

7. The apparatus of claim 1, said set-edit-distance algorithm identifying a shortest edit distance comprising an interpretation that minimizes differences between user inputs and a target word.

8. The apparatus of claim 1, said set-edit-distance algorithm scoring a pair of transposed letters the same as a single-letter replacement error, rather than as two independent errors.

9. The apparatus of claim 1, said processor further implementing a regional correction algorithm that is executed in connection with said set-edit-distance algorithm to compare an input sequence against each vocabulary database entry, wherein user inputs are ambiguous and comprise a set of one or more (letter+probability) pairs, wherein said probability reflects a likelihood that an identified letter is what the user intended, said probability determined by said processor based upon one or more of the following:

Cartesian distance from a stylus tap location to a center of each adjacent letter on a keyboard displayed on a touch screen, the frequency of the adjacent letter, and/or the distribution of taps around each letter;

radial distance between a joystick tilt direction to assigned pie slices of nearby letters of the alphabet;

a degree of similarity between a handwritten letter and a set of possible letter shapes/templates; and

probability that a letter/grapheme is represented in a phoneme or full-word utterance processed by a speech recognition front-end.

10. The apparatus of claim 1, wherein edit distance is applied to ambiguous sets, and wherein penalties are assigned to each difference between an entered and a target vocabulary word.

11. The apparatus of claim 1, said processor executing said set-edit-distance algorithm as follows:

if there are two possible transformations that result in a match, choose the one with the lowest edit distance;

if a letter is in an input'"'"'s probability set, also calculate a regional-correction probability score for that letter;

accumulate all regional-correction probability scores for all letters in a word to calculate a spell correction tap frequency; and

for 0 edit-distance words having the same word length and each letter in the vocabulary word is present in the inputs'"'"' probability sets, use only single tap probabilities.

12. The apparatus of claim 1, said processor executing said set-edit-distance algorithm as follows:

calculating or accumulating values for matching and word list ordering using any of the following;

edit distance;

tap frequency;

stem edit distance;

word frequency; and

source.

13. The apparatus of claim 1, further comprising said processor executing any of the following optimizations:

discarding a possible word match by allowing only one edit/correction for every three actual inputs, up to a maximum of three edits against any one compared word;

minimizing edit distance calculations, where first pass calculating cells which may allow a comparison are rejected entirely;

starting from the results of a previous pass or temporarily whittling down a previous word list, until the user pauses entry;

providing levels of filtering before, during, or after edit distance matrix calculations are completed, comprising any of;

first letter exact, otherwise withdraw target word from consideration;

first letter near-miss, regional, in probability set;

a first letter of a vocabulary word must match one of the first two inputs to allow one add, one drop, or one transposed pair;

a first letter of a vocabulary word must be in a probability set of one of the first two inputs; and

no filtering.

14. The apparatus of claim 1, wherein word Frequency is approximated based on Zipf'"'"'s Law.

15. The apparatus of claim 1, further comprising said processor programmed for executing configuration parameters that include any of:

number of word completions per near-miss section;

number of spell corrections; and

spell correction either regional/probability set or classic edit distance binary.

16. The apparatus of claim 1, further comprising said processor programmed for determining word list sort order based on factors comprising any of regional probability, edit distance, word recency/frequency, as stored in each database, word length, stem edit distance, and/or which of two or more different list profiles or strategies is being used.

17. The apparatus of claim 1, further comprising said processor programmed for executing a word ordering based upon the following determinations in order:

full word always comes before word completion;

source dictionary;

edit distance;

stem edit distance; and

frequency.

18. The apparatus of claim 1, further comprising said processor programmed for executing a word ordering based upon the following determinations in order:

stem edit distance;

word completion or not;

source;

edit distance; and

frequency.

19. The apparatus of claim 1, further comprising said processor programmed for executing one or more auto-substitution macros, comprising any of:

if an input sequence approximately matches both a shortcut and a stem of expanded text, ranking of the macro may be increased; and

if a word in a mobile message is text slang or misspelled, find a valid sponsored keyword.

20. The apparatus of claim 1, further comprising said processor programmed for using a spell-corrected word choice as a basis for further inputs and word completions.

21. The apparatus of claim 1, further comprising said processor programmed for ambiguous entry for search and discovery, wherein if the user'"'"'s input sequence is not closely matched by content of a mobile device, one or more spell-corrected interpretations which do result in matches are offered.

22. 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 the 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.

23. 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 the 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.