SPELL-CHECK FOR A KEYBOARD SYSTEM WITH AUTOMATIC CORRECTION

• US 20080189605A1
• Filed: 01/31/2008
• Published: 08/07/2008
• Est. Priority Date: 02/01/2007
• Status: Active Grant

• Current Assignee: Cerence Operating Company (Cerence Inc.)
• Original Assignee: Tegic Communications, Inc. (Microsoft Corporation)
• Inventors: Kay, David, Unruh, Erland, Tandon, Gaurav
• Granted Patent: US 8,201,087 B2
• Time in Patent Office: Days
• US Class Current: 715/257
• 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 an auto-correcting 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 auto-correcting keyboard region, wherein each time a user contacts the user input device within the auto-correcting keyboard region, a location associated with the user contact is determined and the determined contact location is added to a current input sequence of contact locations;

a memory containing a plurality of objects, wherein each object is further associated with a frequency of use, and wherein each of the plurality of objects in memory is further associated with one or a plurality of predefined groupings of objects;

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 said 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 said set 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. A text input apparatus, comprising:

a user input device in which the user'"'"'s input is ambiguous, said input device comprising an auto-correcting 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 auto-correcting keyboard region, wherein each time a user contacts the user input device within the auto-correcting keyboard region, a location associated with the user contact is determined and the determined contact location is added to a current input sequence of contact locations;

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 said 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 said set 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.

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

4. The apparatus of claim 3, wherein if there is insufficient information from the dictionary and/or user inputs, then a current input is rejected for lack of information to make a determination and the user continues with an input sequence.

5. The apparatus of claim 4, wherein if there is sufficient information to proceed, then the results for the input sequence and dictionary inputs are compared with other top matches in a word choice list and a word is discarded if it is ranked too low on the list.

6. The apparatus of claim 5, wherein if there is sufficient information to proceed, then a lowest-ranked word in said list is dropped if the list is full, and a word is inserted into the list based on ranking.

7. The apparatus of claim 2, wherein said 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.

8. The apparatus of claim 2, wherein said edit distance algorithm uses word frequency as a factor in determining a word match.

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

10. The apparatus of claim 2, 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.

11. The apparatus of claim 10, said tuning component either providing results that emphasize regional aspects of user input or that emphasize word completions based on an input sequence so far.

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

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

14. The apparatus of claim 2, said processor further implementing a regional correction algorithm that is executed in connection with said 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.

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

16. The apparatus of claim 2, said processor executing said 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.

17. The apparatus of claim 2, said processor executing said edit distance algorithm as follows:

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

edit distance;

tap frequency, of comparison;

stem edit distance;

word frequency; and

source.

18. The apparatus of claim 17, wherein tap frequency is calculated as:

probability of letter 1*probability of letter 2* . . .

19. The apparatus of claim 2, 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.

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

21. The apparatus of claim 2, further comprising said processor programmed for executing configuration parameters may 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 exact or not.

22. The apparatus of claim 2, 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.

23. The apparatus of claim 2, 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.

24. The apparatus of claim 2, 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.

25. The apparatus of claim 2, 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.

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

27. The apparatus of claim 2, 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.

28. A text input method, comprising the steps of:

using for text input a user input device in which the user'"'"'s input is ambiguous, said input device comprising an auto-correcting 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 auto-correcting keyboard region, wherein each time a user contacts the user input device within the auto-correcting keyboard region, a location associated with the user contact is determined and the determined contact location is added to a current input sequence of contact locations;

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 said 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 said set 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,

coupling said processor to the user input device, memory, and output device.

29. A predictive text input apparatus, comprising:

an input device that produces a set of characters comprising an output string in response to user operation thereof, each said user operation corresponding to an intended meaning for said output string and having an actual, ambiguous meaning;

a processor that receives as an input word said output string from said input device and that is programmed to execute a set-edit-distance algorithm that turns said input word into an output word that best matches said intended meaning;

said processor programmed to access a database to retrieve one or more target words and to use a matrix determine said set-edit-distance between said input word and a target word by comparing said set of characters in the input word with each character in the target word;

wherein if a target character is in said input set of characters, set-edit-distance does not increase; and

wherein if a target character is not in said input set of characters, set-edit-distance is increased according to a predetermined rule.

30. The apparatus of claim 29, said processor programmed to use character probabilities in determining a final set-edit-distance score.

31. A text input apparatus, comprising:

an input device that produces an input in response to user operation thereof, each said user operation corresponding to an intended meaning for said input and wherein at least one said input corresponds to a set comprising a plurality of possible characters;

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 said 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 said set 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.

32. The apparatus of claim 31, said processor programmed to use the probabilities of said possible characters in determining a final set-edit-distance score.