Systems and methods for character correction in communication devices
View Patent ↗Systems and methods for character error correction are provided, useful for a user of mobile appliances to produce written text with reduced errors. The system includes an interface, a word prediction engine, a statistical engine, an editing distance calculator, and a selector. A string of characters, known as the inputted word, may be entered into the mobile device via the interface. The word prediction engine may then generate word candidates similar to the inputted word using fuzzy logic and user preferences generated from past user behavior. The statistical engine may then generate variable is error costs determined by the probability of erroneously inputting any given character. The editing distance calculator may then determine the editing distance between the inputted word and each of the word candidates by grid comparison using the variable error costs. The selector may choose one or more preferred candidates from the word candidates using the editing distances.
1. A method, comprising the steps of:
receiving text data from an interface, wherein the interface comprises a plurality of keys, wherein each of the plurality of keys corresponds to one or more characters, wherein the text data comprises a sequential string of characters that are input through the plurality of keys, wherein the sequential string of characters corresponds to at least a portion of a word;
comparing the sequential string of characters with a word corpus;
generating at least two candidate words, wherein each of the at least two candidate words comprises a string of characters from the word corpus;
calculating a probability of erroneously inputting any given character of the sequential string of characters through the interface, wherein the erroneous inputting of a character of the sequential string of characters comprises any of
poor spelling,
mis-striking a key of the plurality of keys, wherein the wrong key is entered, or
mis-actuation of a key of the plurality of keys, wherein the key is not entered properly and either the character is not entered or is double entered; generating variable error costs, wherein the variable error costs are determined
by the calculated probability of erroneously inputting any given character of the sequential string of characters through the interface;
calculating the editing distance for each of the at least two candidate words by using the generated variable error costs, wherein the editing distance is the degree of attenuation between the candidate word and the sequential string of characters.. wherein the calculating the editing distance for each of the at least two candidate words comprises a grid comparison between each candidate word of the at least two candidate words and the sequential string of characters, and wherein the grid comparison calculates cell values along grid rows, and further wherein values of cells within a row M, where M comprises a location within a matrix, are purged from memory after all cells in the row M+1 have been calculated; and
selecting a preferred candidate word from the at least two candidate words by using the calculated editing distance, wherein the preferred candidate word has the smallest calculated editing distance of all the calculated editing distances of the at least two candidate words.
2. An apparatus, comprising:
a mechanism for receiving text data from an interface, wherein the interface comprises a plurality of keys, wherein each of the plurality of keys corresponds to one or more characters, wherein the text data comprises a sequential string of characters that are input through the plurality of keys, wherein the sequential string of characters corresponds to at least a portion of a word;
at least one processor programmed to
compare the sequential string of characters with a word corpus,
generate at least two candidate words, wherein each of the at least two candidate words comprises a string of characters from the word corpus,
calculate a probability of erroneously inputting any given character of the sequential string of characters through the interface, wherein the erroneous inputting of a character of the string of characters comprises any of
poor spelling,
mis-striking a key of the plurality of keys, wherein the wrong key is entered, or
mis-actuation of a key of the plurality of keys, wherein the key is not entered properly and either the character is not entered or is double entered,
generate variable error costs, wherein the variable error costs are determined by the calculated probability of erroneously inputting any given character of the sequential string of characters, and
calculate an editing distance for each of the at least two candidate words using the generated variable error costs, wherein the editing distance is the degree of attenuation between each of the at least two candidate words and the sequential string of characters, wherein the calculating the editing distance for each of the at least two candidate words comprises a grid comparison between each candidate word of the at least two candidate words and the sequential string of characters, and wherein the grid comparison calculates cell values along grid rows, and further wherein values of cells within a row M, where M comprises a location within a matrix, are purged from memory after all cells in the row M+1 have been calculated; and
a selector configured to select a preferred candidate from the at least two candidate words using the editing distance, wherein the preferred candidate word has the smallest editing distance of all the editing distances of the at least two candidate words.
3. A device, comprising:
an interface, wherein the interface comprises a plurality of keys, wherein each of the plurality of keys corresponds to one or more characters;
at least one processor programmed to
receive a sequential string of characters that are input through the plurality of keys, wherein the received sequential string of characters corresponds to at least a portion of a word,
compare the received sequential string of characters with a word corpus, generate the at least two candidate words, wherein each of the at least
two candidate words comprises a string of characters from the word corpus, calculate a
probability of erroneously inputting any given character of the received sequential string of characters through the interface, wherein the erroneous inputting of a character of the string of characters comprises any of
poor spelling,
mis-striking a key of the plurality of keys, wherein the wrong key is entered, or
mis-actuation of a key of the plurality of keys, wherein the key is not entered properly and either the character is not entered or is double entered,
generate variable error costs, wherein the variable error costs are determined by the calculated probability of erroneously inputting any given character of the received sequential string of characters, and
calculate an editing distance for each of the at least two candidate words using the generated variable error costs, wherein the editing distance is the degree of attenuation between each of the candidate words and the received sequential string of characters, wherein the calculating the editing distance for each of the at least two candidate words comprises a grid comparison between each candidate word of the at least two candidate words and the sequential string of characters, and wherein the grid comparison calculates cell values along grid rows, and further wherein values of cells within a row M, where M comprises a location within a matrix, are purged from memory after all cells in the row M+1 have been calculated; and
a selector configured to select a preferred candidate from the at least two candidate words using the editing distance, wherein the preferred candidate word has the smallest editing distance of all the editing distances of the at least two candidate words.
4. The method of claim 3 , wherein the step of selecting the at least two candidate words from the word corpus by fuzzy logic utilizes user preferences, and wherein user preferences are generated from past user behavior.
5. The method of claim 1 , wherein the variable error costs comprises any of replacement error costs, addition error costs or deletion error costs.
6. The method of claim 1 , wherein the preferred candidate word comprises more than one candidate of the at least two candidate words, and wherein each of the more than one candidate of the preferred candidate word has an editing distance below a threshold value.
7. The method of claim, wherein the step of calculating each editing distance queries previously stored editing distances for a partial match, and when if the partial match is found, inputting the stored editing distance into the grid comparison.
8. The method of claim 1 , wherein the method is performed continuously as the characters are input through the plurality of keys.
9. The method of claim 1 , wherein the method is initiated once a word delineator is encountered in the sequential string of characters.
10. An apparatus, comprising:
a mechanism for receiving text data from an interface, wherein the interface comprises a plurality of keys, wherein each of the plurality of keys corresponds to one or more characters, wherein the text data comprises a sequential string of characters that are input through the plurality of keys, wherein the sequential string of characters corresponds to at least a portion of a word;
at least one processor programmed to
compare the sequential string of characters with a word corpus,
generate at least two candidate words, wherein each of the at least two candidate words comprises a string of characters from the word corpus,
calculate a probability of erroneously inputting any given character of the sequential string of characters through the interface, wherein the erroneous inputting of a character of the string of characters comprises any of
poor spelling,
mis-striking a key of the plurality of keys, wherein the wrong key is entered, or
mis-actuation of a key of the plurality of keys, wherein the key is not entered properly and either the character is not entered or is double entered,
generate variable error costs, wherein the variable error costs are determined by the calculated probability of erroneously inputting any given character of the sequential string of characters, and
calculate an editing distance for each of the at least two candidate words using the generated variable error costs, wherein the editing distance is the degree of attenuation between each of the at least two candidate words and the sequential string of characters, wherein the calculating the editing distance for each of the at least two candidate words comprises a grid comparison between each candidate word of the at least two candidate words and the sequential string of characters, and wherein the grid comparison calculates cell values along grid rows, and further wherein values of cells within a row M, where M comprises a location within a matrix, are purged from memory after all cells in a row M+1 have been calculated; and
a selector configured to select a preferred candidate from the at least two candidate words using the editing distance, wherein the preferred candidate word has the smallest editing distance of all the editing distances of the at least two candidate words.
11. The apparatus of claim 10 , wherein the characters comprise any of alphabetic symbols, syllabic symbols, or ideographic symbols.
12. The apparatus of claim 10 wherein the generation of the at least two candidate words comprises a selection of the at least two candidate words from the word corpus by fuzzy logic, wherein if an error is detected in a candidate word, then the candidate word can be tested again after substituting in turn each character of the sequential string of characters with an adjacent letter from the interface.
13. The apparatus of claim 12 , wherein the selection of the at least two candidate words from the word corpus by fuzzy logic utilizes user preferences, and wherein user preferences are generated from past user behavior.
14. The apparatus of claim 10 , wherein the variable error costs comprises any of replacement error costs, addition error costs or deletion error costs.
15. The apparatus of claim 10 , wherein the preferred candidate word comprises more than one candidate of the at least two candidate words, and wherein each of the more than one candidate of the preferred candidate word has an editing distance below a threshold value.
16. The apparatus of claim 10 , wherein the calculation of each of the editing distances comprises a query of previously stored editing distances for a partial match, and if the partial match is found, the stored editing distance is input into the grid comparison.
17. The apparatus of claim 10 , wherein the at least one processor is programmed to operate continuously as the characters are input through the plurality of keys.
18. The apparatus of claim 10 , wherein the at least one processor is programmed to operate once a word delineator is encountered in the sequential string of characters.
19. A device, comprising:
an interface, wherein the interface comprises a plurality of keys, wherein each of the plurality of keys corresponds to one or more characters,
at least one processor programmed to
receive a sequential string of characters that are input through the plurality of keys, wherein the received sequential string of characters corresponds to at least a portion of a word,
compare the received sequential string of characters with a word corpus,
generate the at least two candidate words, wherein each of the at least two candidate words comprises a string of characters from the word corpus,
calculate a probability of erroneously inputting any given character of the received sequential string of characters through the interface, wherein the erroneous inputting of a character of the string of characters comprises any of
poor spelling,
mis-striking a key of the plurality of keys, wherein the wrong key is entered, or
mis-actuation of a key of the plurality of keys, wherein the key is not entered properly and either the character is not entered or is double entered,
generate variable error costs, wherein the variable error costs are determined by the calculated probability of erroneously inputting any given character of the received sequential string of characters, and
calculate an editing distance for each of the at least two candidate words using the generated variable error costs, wherein the editing distance is the degree of attenuation between each of the candidate words and the received sequential string of characters, wherein the calculating the editing distance for each of the at least two candidate words comprises a grid comparison between each candidate word of the at least two candidate words and the sequential string of characters, and wherein the grid comparison calculates cell values along grid rows, and further wherein values of cells within a row M, where M comprises a location within a matrix, are purged from memory after all cells in a row M+1 have been calculated; and
a selector configured to select a preferred candidate from the at least two candidate words using the editing distance, wherein the preferred candidate word has the smallest editing distance of all the editing distances of the at least two candidate words.
20. The device of claim 19 , wherein the characters comprise any of alphabetic symbols, syllabic symbols, or ideographic symbols.
21. The device of claim 19 , wherein the generation of the at least two candidate words comprises a selection of the at least two candidate words from the word corpus by fuzzy logic, wherein if an error is detected in a candidate word, then the candidate word can be tested again after substituting in turn each character of the received sequential string of characters with an adjacent letter from the interface.
22. The device of claim 21 , wherein the selection of the at least two candidate words from the word corpus by fuzzy logic utilizes user preferences, and wherein user preferences are generated from past user behavior.
23. The device of claim 19 , wherein the variable error costs comprises any of replacement error costs, addition error costs or deletion error costs.
24. The device of claim 19 , wherein the preferred candidate word comprises more than one candidate of the at least two candidate words, and wherein each of the more than one candidate of the preferred candidate word has an editing distance below a threshold value.
25. The device of claim 19 , wherein the at least one processor is programmed to operate continuously as the characters are input through the plurality of keys.
26. The device of claim 19 , wherein the at least one processor is programmed to operate once a word delineator is encountered in the received sequential string of characters.