Alternative hypothesis error correction for gesture typing

• US 9,081,500 B2
• Filed: 05/31/2013
• Issued: 07/14/2015
• Est. Priority Date: 05/03/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Ouyang, Yu, Zhai, Shumin
• Primary Examiner(s): HERNANDEZ, JESUS J
• Application Number:
  US13/907,614
• Publication Number:
  US 20140327622A1
• Time in Patent Office: 774 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 3/0236 using selection techniques to select from displayed items
• 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 3/04897 Special input arrangements or commands for improving display capability
• 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
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

In one example, a method may include outputting, by a computing device and for display, a graphical keyboard comprising a plurality of keys, and receiving an indication of a gesture. The method may include determining an alignment score that is based at least in part on a word prefix and an alignment point traversed by the gesture. The method may include determining at least one alternative character that is based at least in part on a misspelling that includes at least a portion of the word prefix. The method may include determining an alternative alignment score based at least in part on the alternative character; and outputting, by the computing device and for display, based at least in part on the alternative alignment score, a candidate word based at least in part on the alternative character.

Claims

1. A method comprising:

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

receiving, by the computing device, an indication of a gesture detected at a presence-sensitive input device;

determining, by the computing device, an alignment score that is based at least in part on a word prefix and an alignment point traversed by the gesture, wherein the alignment score represents a probability that the alignment point indicates a key of the plurality of keys;

determining, by the computing device and based at least in part on the alignment score, that at least a portion of the word prefix matches correction data, wherein the correction data indicates one or more alternative characters that are based at least in part on one or more misspellings of at least one word in a vocabulary;

determining, by the computing device and based at least in part on the determining that at least the portion of the word prefix matches correction data, at least one alternative character indicated by the correction data, the at least one alternative character based at least in part on a misspelling that includes at least a portion of the word prefix, wherein the alternative character is not based on a distance that the alignment point is away from a neighboring key that is associated with the alternative character;

generating, by the computing device, an alternative word prefix comprising at least a portion of the word prefix and the at least one alternative character;

determining, by the computing device, an alternative alignment score for the alternative word prefix that is based at least in part on the alternative character; and

outputting, by the computing device, for display, and based at least in part on the alternative alignment score, a candidate word.

2. The method of claim 1,

wherein the word prefix includes a first substring and a second substring, the second substring including the at least one character, and

wherein determining that at least a portion of the word prefix matches correction data further comprises:

determining, by the computing device, that the second substring of the word prefix matches a first string in the correction data;

determining, by the computing device and based at least in part on the first string in the correction data, a second string in the correction data that comprises the at least one alternative character; and

wherein generating the alternative word prefix comprises generating, by the computing device, the alternative word prefix comprising the first substring of the word prefix and the second string in the correction data.

3. The method of claim 2, wherein the second string in the correction data comprises a phonetic substitution of the second substring in the word prefix.

4. The method of claim 1, further comprising:

determining, by the computing device, a substring of the word prefix that matches a first string in the correction data;

determining, by the computing device and based at least in part on the first string in the correction data, the at least one alternative character; and

wherein generating the alternative word prefix comprises generating, by the computing device, the alternative word prefix comprising the word prefix and the at least one alternative character.

5. The method of claim 4, wherein the alternative character comprises a wildcard character that represents each possible character in character set.

6. The method of claim 1, wherein the at least one alternative character comprises at least one placeholder value, wherein determining at least one alternative character further comprises:

inserting, by the computing device, at least one placeholder value in the alternative word prefix, wherein the at least one placeholder value indicates at least one arbitrary character that is not included in in one or more candidate words that are based on the alternative word prefix.

7. The method of claim 1, wherein the gesture is a first gesture, the method further comprising:

responsive to receiving an indication of a second gesture that is subsequent to the first gesture, refraining, by the computing device, from inserting one or more characters in the alternative word prefix; and

responsive to receiving an indication of a third gesture that is subsequent to the second gesture, inserting, by the computing device, the at least one character in the alternative word prefix.

8. The method of claim 1,

wherein the word prefix includes a first substring and a second substring;

wherein determining the at least one alternative character further comprises determining, by the computing device, a transposition of the second substring, wherein character positions of at least two characters of the second substring are transposed in the transposition, wherein the at least one alternative character is included in the transposition; and

wherein generating the alternative word prefix comprises generating, by the computing device, the alternative word prefix comprising at least the transposition.

9. The method of claim 8, further comprising:

determining, by the computing device, that at least one of the first substring and the second substring matches a string in the correction data; and

determining, by the computing device and based at least in part on the match, the transposition.

10. The method of claim 1,

wherein determining the at least one alternative character comprises applying a first error correction operation based at least in part on a substring of the word prefix, the method, further comprising:

responsive to receiving a subsequent indication of a gesture detected at a presence-sensitive input device, determining, by the computing device, a quantity of error correction operations applied to the word prefix; and

responsive to determining that the quantity of error correction operations satisfies a threshold, refraining, by the computing device, from applying an error correction operation to the word prefix.

11. The method of claim 1, wherein determining the alternative alignment score that is based at least in part on the alternative character further comprises:

determining, by the computing device and responsive to determining the at least one alternative character, a penalty value; and

determining, by the computing device and based at least in part on the penalty value, the alternative alignment score.

12. The method of claim 11, wherein determining the at least one alternative character comprises determining at least one error correction operation based at least in part on a substring of the word prefix, the method further comprising:

determining, by the computing device, a type of an error correction operation from a plurality of error correction operations; and

selecting, by the computing device, the penalty value from a plurality of penalty values, wherein each penalty value in the plurality of penalty values is ordered in a ranked ordering, wherein each penalty value is associated with at least one type of error correction operation.

13. The method of claim 1, wherein outputting the candidate word based at least in part on the alternative alignment score, further comprises:

responsive to determining that the alternative alignment score satisfies a threshold, outputting, by the computing device and for display, the candidate word based at least in part on the alternative character, wherein the threshold comprises a value that is equal to a quantity of a first subset of word prefixes associated with one or more alignment scores that are greater than alignment scores associated word prefixes in a second subset of word prefixes.

14. The method of claim 1, wherein determining the at least one alternative character comprises applying a first error correction operation based at least in part on a substring of the word prefix, the method further comprising:

responsive to receiving a subsequent indication of a gesture detected at a presence-sensitive input device, determining, by the computing device, a degree of similarity between the word prefix and at least one candidate word in a lexicon, wherein the degree of similarity is within a range of degrees of similarity; and

responsive to determining that the degree of similarity does not satisfy a threshold, refraining, by the computing device, from applying an error correction operation to the word prefix.

15. The method of claim 1, further comprising:

responsive to determining, by the computing device, that the alignment score fails to satisfy a threshold, determining the at least one alternative character that is based at least in part on the misspelling that includes at least the portion of the word prefix.

16. A non-transitory computer-readable storage medium encoded with instructions that, when executed, cause at least one processor to:

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

receive an indication of a gesture detected at a presence-sensitive input device;

determine an alignment score that is based at least in part on a word prefix and an alignment point traversed by the gesture, wherein the alignment score represents a probability that the alignment point indicates a key of the plurality of keys;

determine, based at least in part on the alignment score, that at least a portion of the word prefix matches correction data, wherein the correction data indicates one or more alternative characters that are based at least in part on one or more misspellings of at least one word in a vocabulary;

determine, based at least in part on the determining that at least the portion of the word prefix matches correction data, at least one alternative character indicated by the correction data, the at least one alternative character based at least in part on a misspelling that includes at least a portion of the word prefix, wherein the alternative character is not based on a distance that the alignment point is away from a neighboring key that is associated with the alternative character;

generate an alternative word prefix comprising at least a portion of the word prefix and the at least one alternative character;

determine an alternative alignment score for the alternative word prefix that is based at least in part on the alternative character; and

output for display, and based at least in part on the alternative alignment score, a candidate word based at least in part on the alternative character.

17. The non-transitory computer-readable storage medium of claim 16, wherein the word prefix includes a first substring and a second substring, the second substring including the at least one character, and

wherein the computer-readable storage medium is encoded with instructions that, when executed, cause at least one processor to:

determine that the second substring of the word prefix matches a first string in the correction data; and

determine based at least in part on the first string in the correction data, a second string in the correction data that comprises the at least one alternative character,

wherein the alternative word prefix comprises the first substring of the word prefix and the second string in the correction data.

18. The non-transitory computer-readable storage medium of claim 16, wherein the at least one alternative character comprises at least one placeholder value, and

wherein the computer-readable storage medium is encoded with instructions that, when executed, cause at least one processor to:

insert at least one placeholder value in the alternative word prefix, wherein the at least one placeholder value indicates at least one arbitrary character that is not included in in one or more candidate words that are based on the alternative word prefix.

19. The non-transitory computer-readable storage medium of claim 16, wherein the gesture is a first gesture, wherein the computer-readable storage medium is encoded with instructions that, when executed, cause at least one processor to:

responsive to receiving an indication of a second gesture that is subsequent to the first gesture, refrain from inserting one or more characters in the alternative word prefix; and

responsive to receiving an indication of a third gesture that is subsequent to the second gesture, insert the at least one character in the alternative word prefix.

20. The non-transitory computer-readable storage medium of claim 16,

wherein the word prefix includes a first substring and a second substring,

wherein the computer-readable storage medium is encoded with instructions that, when executed, cause at least one processor to:

determine a transposition of the second substring, wherein character positions of at least two characters of the second substring are transposed in the transposition, wherein the at least one alternative character is included in the transposition,

wherein the alternative word prefix comprises at least the transposition.

21. A computing device comprising at least one processor, wherein the at least one processor is configured to:

output for display a graphical keyboard comprising a plurality of keys;

receive an indication of a gesture detected at a presence-sensitive input device;

determine an alignment score that is based at least in part on a word prefix and an alignment point traversed by the gesture, wherein the alignment score represents a probability that the alignment point indicates a key of the plurality of keys;

determine, based at least in part on the alignment score, that at least a portion of the word prefix matches correction data, wherein the correction data indicates one or more alternative characters that are based at least in part on one or more misspellings of at least one word in a vocabulary;

responsive to determining that the alignment score fails to satisfy a threshold, determine, based at least in part on the at least the portion of the word prefix matching the correction data, at least one alternative word prefix comprising at least a portion of the word prefix and at least one alternative character;

determine an alternative alignment score that is based at least in part on the at least one alternative word prefix, wherein the alternative character is not based on a distance that the alignment point is away from a neighboring key that is associated with the alternative character; and

output for display, and based at least in part on the alternative alignment score, a candidate word.

22. The computing device of claim 21, wherein the word prefix includes a first substring and a second substring, the second substring, and wherein the at least one processor is configured to:

determine that the second substring of the word prefix matches a first string in correction data; and

determine based at least in part on the first string in the correction data, a second string in the correction data,

wherein the alternative word prefix comprises the first substring of the word prefix and the second string in the correction data.

23. The computing device of claim 21, wherein the at least one processor is configured to:

insert at least one placeholder value in the alternative word prefix, wherein the at least one placeholder value indicates at least one arbitrary character that is not included in in one or more candidate words that are based on the alternative word prefix.

24. The computing device of claim 21, wherein the gesture is a first gesture, wherein the at least one processor is configured to:

responsive to receiving an indication of a second gesture that is subsequent to the first gesture, refrain from inserting one or more characters in the alternative word prefix; and

responsive to receiving an indication of a third gesture that is subsequent to the second gesture, insert the at least one character in the alternative word prefix.

25. The computing device of claim 21, wherein the word prefix includes a first substring and a second substring, wherein the at least one processor is configured to:

determine a transposition of the second substring, wherein character positions of at least two characters of the second substring are transposed in the transposition, wherein the at least one alternative character is included in the transposition,

wherein the alternative word prefix comprises at least the transposition.