ALTERNATIVE HYPOTHESIS ERROR CORRECTION FOR GESTURE TYPING

• US 20150277757A1
• Filed: 06/12/2015
• Published: 10/01/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
• Granted Patent: US 9,841,895 B2
• Time in Patent Office: Days
• 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-20. -20. (canceled)

21. A method comprising:

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

responsive to detecting a first portion of a gesture at a presence-sensitive input device, generating a word prefix comprising a plurality of characters;

responsive to detecting, by the computing device and during the gesture, a second portion of the gesture at the presence-sensitive input device;

updating, based on a word in a dictionary, the word prefix to include an additional character;

responsive to determining that an alignment score of the gesture matching the word prefix with the additional character does not satisfy a threshold, determining, using correction data that indicates at least one alternative word prefix that is based at least in part on a misspelling of the word in the dictionary, an alternative alignment score, wherein the alternative word prefix comprises at least a portion of the word prefix;

determining, by the computing device and based on the alternative alignment score for the alternative word prefix, a candidate word; and

outputting, by the computing device and for display, the candidate word.

22. The method of claim 21, further comprising:

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

determining, by the computing device and based at least in part on the substring of the word prefix matching the string in the correction data, at least one alternative character; and

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

23. The method of claim 22, wherein the string in the correction data comprises a phonetic substitution of the substring of the word prefix.

24. The method of claim 22, wherein the at least one alternative character comprises a wildcard character that represents each possible character in a character set.

25. The method of claim 21, further comprising:

generating, by the computing device, the alternative word prefix comprising at least a substring of the word prefix; and

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 the candidate word that is based on the alternative word prefix.

26. The method of claim 21, further comprising:

determining, by the computing device, a transposition of a substring of the word prefix, wherein character positions of at least two characters of the substring are transposed in the transposition; and

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

27. The method of claim 21, wherein the alternative word prefix includes an alternative character, 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.

28. The method of claim 21, further comprising:

responsive to receiving a third portion of the gesture, 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 a subsequent error correction operation to the word prefix.

29. The method of claim 21, further comprising:

determining, by the computing device and responsive to determining an alternative character for the alternative word prefix, a penalty value,

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

30. The method of claim 21, wherein outputting the candidate word comprises:

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

31. 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;

in response to detecting a first portion of a gesture at a presence-sensitive input device, generate a word prefix comprising a plurality of characters;

in response to detecting, during the gesture, a second portion of the gesture at the presence-sensitive input device;

update, based on a word in a dictionary, the word prefix to include an additional character;

responsive to determining that an alignment score of the gesture matching the word prefix with the additional character does not satisfy a threshold, determine, using correction data that indicates at least one alternative word prefix that is based at least in part on a misspelling of the word in the dictionary, an alternative alignment score, wherein the alternative word prefix comprises at least a portion of the word prefix;

determine, based on the alternative alignment score for the alternative word prefix, a candidate word; and

output, for display, the candidate word.

32. The non-transitory computer-readable storage medium of claim 31, comprising instructions that, when executed, cause the at least one processor of the computing device to:

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

determine, based at least in part on the substring of the word prefix matching the string in the correction data, at least one alternative character; and

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

33. The non-transitory computer-readable storage medium of claim 31, wherein the string in the correction data comprises a phonetic substitution of the substring of the word prefix.

34. The non-transitory computer-readable storage medium of claim 31, comprising instructions that, when executed, cause the at least one processor of the computing device to:

generate the alternative word prefix comprising at least a substring of the word prefix; and

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 one or more candidate words that are based on the alternative word prefix.

35. The non-transitory computer-readable storage medium of claim 31, comprising instructions that, when executed, cause the at least one processor of the computing device to:

determine a transposition of a substring of the word prefix, wherein character positions of at least two characters of the substring are transposed in the transposition; and

generate the alternative word prefix comprising at least the transposition.

36. The non-transitory computer-readable storage medium of claim 31, wherein the alternative word prefix includes an alternative character, 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.

37. A computing device comprising:

at least one processor; and

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

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

generate a word prefix comprising a plurality of characters, in response to detecting a first portion of a gesture at a presence-sensitive input device;

in response to detecting, during the gesture, a second portion of the gesture at the presence-sensitive input device;

update, based on a word in a dictionary, the word prefix to include an additional character;

responsive to determining that an alignment score of the gesture matching the word prefix with the additional character does not satisfy a threshold, determine, using correction data that indicates at least one alternative word prefix that is based at least in part on a misspelling of the word in the dictionary, an alternative alignment score, wherein the alternative word prefix comprises at least a portion of the word prefix;

determine, based on the alternative alignment score for the alternative word prefix, a candidate word; and

output, for display, the candidate word.

38. The computing device of claim 37, wherein the at least one module is operable by the at least one processor to:

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

determine, based at least in part on the substring of the word prefix matching the string in the correction data, at least one alternative character; and

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

39. The computing device of claim 37, wherein the string in the correction data comprises a phonetic substitution of the substring of the word prefix.

40. The computing device of claim 37, wherein the at least one module is operable by the at least one processor to:

generate the alternative word prefix comprising at least a substring of the word prefix; and

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 one or more candidate words that are based on the alternative word prefix.

41. The computing device of claim 37, wherein the at least one module is operable by the at least one processor to:

determine a transposition of a substring of the word prefix, wherein character positions of at least two characters of the substring are transposed in the transposition; and

generate the alternative word prefix comprising at least the transposition.

42. The computing device of claim 37, wherein the alternative word prefix includes an alternative character, 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.