Feature-based autocorrection

• US 8,713,433 B1
• Filed: 01/03/2013
• Issued: 04/29/2014
• Est. Priority Date: 10/16/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Ouyang, Yu, Zhai, Shumin
• Primary Examiner(s): RIES, LAURIE ANNE
• Application Number:
  US13/733,701
• Publication Number:
  US 20140104175A1
• Time in Patent Office: 481 Days
• Field of Search: 715/261
• US Class Current: 715/261
• CPC Class Codes: G06F 16/245 Query processing
• 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/242 Dictionaries
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique
• CPC Class Codes: G06F 40/279 Recognition of textual entities
• CPC Class Codes: H04L 51/02 using automatic reactions or user delegation, e.g. automatic replies or chatbot-generated messages
• CPC Class Codes: H04L 51/063 Content adaptation, e.g. replacement of unsuitable content

Abstract

A computing device is described that outputs for display at a presence-sensitive screen, a graphical keyboard having keys. The computing device receives an indication of a selection of one or more of the keys. Based on the selection the computing device determines a character string from which the computing device determines one or more candidate words. Based at least in part on the candidate words and a plurality of features, the computing device determines a spelling probability that the character string represents an incorrect spelling of at least one candidate word. The plurality of features includes a spatial model probability associated with at least one of the candidate words. If the spelling probability satisfies a threshold, the computing device outputs for display the at least one candidate word.

Claims

1. A method comprising:

outputting, by a computing device and for display at a display device, a graphical keyboard comprising a plurality of keys;

receiving, by the computing device and from an input device, an indication of a selection of one or more of the plurality of keys;

determining, by the computing device and based at least in part on the indication of the selection, a character string;

determining, by the computing device and based at least in part on the character string, a plurality of candidate words;

determining, by the computing device, and based at least in part on the plurality of candidate words and a plurality of features, a spelling probability that the character string comprises an incorrect spelling of at least one of the plurality of candidate words, the plurality of features comprising at least a spatial model probability associated with at least one of the one or more candidate words; and

responsive to determining that the spelling probability satisfies a threshold, outputting, by the computing device, for display at the display device, the at least one of the plurality of candidate words.

2. The method of claim 1, further comprising:

determining, by the computing device, a plurality of words that were received by the computing device prior to receiving the indication of the selection of one or more of the plurality of keys; and

determining, by the computing device and based on the plurality of words, at least one language model probability for at least one of the one or more candidate words, wherein the at least one language model probability indicates whether the at least one of the one or more candidate words is positioned subsequent to the plurality of words in a sequence of words comprising the plurality of words and the at least one of the one or more candidate words.

3. The method of claim 1, further comprising:

determining, by the computing device, a plurality of words that are received by the computing device subsequent to receiving the indication of the selection of one or more of the plurality of keys; and

determining, by the computing device and based on the plurality of words, at least one language model probability for at least one of the one or more candidate words, wherein the at least one language model probability indicates whether the at least one of the one or more candidate words is positioned prior to the plurality of words in a sequence of words comprising the plurality of words and the at least one of the one or more candidate words.

4. The method of claim 1, further comprising:

determining, by the computing device, a first plurality of words that were received by the computing device prior to receiving the indication of the selection of one or more of the plurality of keys;

determining, by the computing device, a second plurality of words received by the computing device subsequent to receiving the indication of the selection of one or more of the plurality of keys; and

determining, by the computing device and based on the first and second pluralities of words, at least one language model probability for at least one of the one or more candidate words, wherein the language model probability indicates whether the at least one of the one or more candidate words is positioned subsequent to the first plurality of words and prior to the second plurality of words in a sequence of words comprising the plurality of first words, the at least one of the one or more candidate words, and the plurality of second words.

5. The method of claim 1, wherein the plurality of features comprises a typing speed of the selection of one or more of the plurality of keys, the method further comprising:

determining, by the computing device, a first point in time when the computing device begins receiving the indication of the selection of one or more of the plurality of keys;

determining, by the computing device, a second point in time when the computing device stops receiving the indication of the selection of one or more of the plurality of keys;

determining, by the computing device, a quantity of characters included in the character string;

determining, by the computing device, a duration of time from the first point in time to the second point in time; and

determining, by the computing device and based on the duration of time and the quantity of characters, the typing speed of the selection.

6. The method of claim 1, wherein the plurality of features comprises a backspace usage percentage associated with the selection of one or more of the plurality of keys, the method further comprising:

determining, by the computing device, a quantity of key selections included in the selection of one or more of the plurality of keys;

determining, by the computing device, a quantity of backspace key selections included in the selection of one or more of the plurality of keys and a quantity of delete key selections included in the selection of one or more of the plurality of keys; and

determining the backspace usage percentage, by the computing device and based at least in part on;

the quantity of backspace key selections, the quantity of delete key selections, and the total quantity of key selections.

7. The method of claim 1, wherein the plurality of features comprises a suggestion bar usage percentage, the method further comprising:

outputting, by the computing device and for display at the display device a suggestion bar region that includes one or more suggested word replacements; and

determining, by the computing device, that the suggestion bar usage percentage comprises a ratio of;

a quantity of selections, within a duration of time, of the one or more suggested word replacements, and

a total quantity words that are generated, within the duration of time, by the computing device and based at least in part on indications of user input received by the computing device.

8. The method of claim 1, wherein the spatial model probability associated with the at least one of the one or more candidate words is a candidate word spatial model probability associated with the at least one of the one or more candidate words, the method further comprising:

determining, by the computing device, a character string spatial model probability that indicates whether the character string represents an accurate sequence of characters based on the selection of the one or more plurality of keys;

determining, by the computing device, that the character string is not included in a lexicon;

responsive to determining that the character string is not included in the lexicon, determining, by the computing device, that the character string spatial model probability of the character string is greater than a character string threshold; and

responsive to determining the character string spatial model probability of the character string is greater than the character string threshold, determining, by the computing device, the plurality of candidate words comprises the character string.

9. The method of claim 8, wherein the indication of the selection of one or more of the plurality of keys comprises at least one input location of the input device, the method further comprising:

determining, by the computing device, a Euclidian distance associated with the at least one input location and a key location associated with one of the plurality of keys; and

determining, by the computing device and based on the Euclidian distance, the character string spatial model probability of the character string.

10. The method of claim 1, wherein the indication of the selection comprises at least one input location of the input device, the method further comprising:

determining, by the computing device, a Euclidian distance associated with the at least one input location and a key location of at least one of the plurality of keys; and

determining, by the computing device and based on the Euclidian distance, the spatial model probability associated with at least one of the candidate words.

11. The method of claim 1, wherein outputting the at least one of the plurality of candidate words further comprises:

outputting, by the computing device and for display at the display device, the character string; and

outputting, by the computing device and for display at the display device, the at least one of the plurality of candidate words within a predefined distance above the character string.

12. The method of claim 11, wherein outputting the character string further comprises:

outputting, by the computing device and for display at the display device, the character string with a format, wherein the format includes at least one of an underline, a highlight, a font size, and a font color.

13. The method of claim 11, further comprising:

receiving, by the computing device, an indication of a user input detected at an input location of the input device;

determining, by the computing device and based at least in part on the indication of the user input, a selected candidate word, wherein the selected candidate word is one of the plurality of candidate words that is outputted above the character string; and

outputting, by the computing device and for display at the display device, the selected candidate word to replace the character string.

14. The method of claim 1, wherein the at least one of the plurality of candidate words is outputted at a first point in time, the method further comprising:

determining, by the computing device, an elapsed time between the first point in time and a second point in time;

responsive to determining that the elapsed time is greater than a time threshold, refraining from outputting for display, by the computing device, the plurality of candidate words.

15. The method of claim 1, further comprising:

sending, by the computing device and to a remote computing system that is operatively coupled to the computing device, the character string; and

receiving, by the computing device and from the remote computing system, the plurality of candidate words.

16. The method of claim 1, further comprising:

determining, by the computing device and based at least in part on a lexicon, a first spelling probability that the character string comprises an incorrect spelling of a first word of the plurality of candidate words;

determining, by the computing device and based at least in part on a lexicon, a second spelling probability that the character string comprises an incorrect spelling of a second word of the plurality of candidate words;

determining, by the computing device, a value comprising a difference between the first spelling probability and the second spelling probability;

responsive to determining the value does not exceed an ambiguity threshold, outputting, by the computing device and for display at the display device, the first word and the second word.

17. The method of claim 1, further comprising:

receiving, by the computing device, an indication of a user input detected at an input location of the input device that corresponds to a region of the display device at which at least one of the plurality of candidate words is displayed; and

responsive to receiving the indication of the user input, outputting, by the computing device and for display at the display device, at least one additional candidate word of the plurality of candidate words.

18. The method of claim 1, wherein the character string is a first word in a lexicon, the method further comprising:

responsive to determining a context associated with the character string, selecting, by the computing device and based at least in part on the context, a second word in the lexicon as the at least one of the plurality of candidate words.

19. A computer-readable storage medium encoded with instructions that, when executed, cause at least one processor of a computing device to:

output, for display at a display device, a graphical keyboard comprising a plurality of keys;

receive, from an input device, an indication of a selection of one or more of the plurality of keys;

determine, based at least in part on the indication of the selection, a character string;

determine, based at least in part on the character string, a plurality of candidate words;

determine, based at least in part on the plurality of candidate words and a plurality of features, a spelling probability that the character string comprises an incorrect spelling of at least one of the plurality of candidate words, the plurality of features comprising at least a spatial model probability associated with each of the one or more candidate words; and

responsive to determining that the spelling probability satisfies a threshold, output, the at least one of the plurality of candidate words.

20. A computing system comprising:

an input device;

a display device;

at least one processor; and

at least one module operable by the at least one processor to;

receive, from the input device, an indication of a selection of one or more of a plurality of keys of a keyboard associated with the input device;

determine, based at least in part on the indication of the selection, a character string;

determine, based at least in part on the character string, a plurality of candidate words;

determine, based at least in part on the plurality of candidate words and a plurality of features, a spelling probability that the character string comprises an incorrect spelling of at least one of the plurality of candidate words, the plurality of features comprising at least a spatial model probability associated with each of the one or more candidate words; and

responsive to determining that the spelling probability satisfies a threshold, output, for display at the display device, the at least one of the plurality of candidate words.

21. The computing device of claim 20, wherein the at least one module is further operable by the at least one processor to output a graphical keyboard for display at the display device, wherein the keyboard associated with the input device comprises the graphical keyboard.