Alternative hypothesis error correction for gesture typing

• US 10,241,673 B2
• Filed: 11/09/2017
• Issued: 03/26/2019
• Est. Priority Date: 05/03/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Ouyang, Yu, Zhai, Shumin
• Primary Examiner(s): Ma, Calvin C
• Application Number:
  US15/808,233
• Publication Number:
  US 20180074698A1
• Time in Patent Office: 502 Days
• Field of Search: 345168, 345173, 345174, 715773
• 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:

detecting, by a computing device, a gesture that selects one or more keys from a plurality of keys of a graphical keyboard;

generating, by the computing device, based on the one or more keys, an initial plurality of characters selected by the gesture;

updating, based on a word in a dictionary, the initial plurality of characters to include an additional character not selected by the gesture;

determining whether an alignment score of the gesture matching a selection of the initial plurality of characters with the additional character satisfies a first threshold; and

responsive to determining that the alignment score of the gesture matching the selection of the initial plurality of characters with the additional character does not satisfy the first threshold, determining whether the word in the dictionary is intended by the gesture by at least;

determining, by the computing device, that a substring of the initial plurality of characters matches at least a portion of an alternative plurality of characters intended by the gesture, wherein the alternative plurality of characters is determined from correction data that indicates one or more misspellings of the word in the dictionary;

determining whether an alternative alignment score of the gesture matching a selection of the at least a portion of the alternative plurality of characters satisfies a second threshold; and

responsive to determining that the alternative alignment score of the gesture matching the selection of the at least a portion of the alternative plurality of characters satisfies the second threshold, outputting, by the computing device and for display, the word in the dictionary as a candidate word.

2. The method of claim 1, wherein the one or more misspellings of the word in the dictionary comprise a phonetic substitution of the substring of the initial plurality of characters.

3. The method of claim 1, wherein the additional character comprises a wildcard character that represents each possible character in a character set.

4. The method of claim 1, wherein the alternative plurality of characters includes an alternative character, wherein the alternative character is based on a feature of the gesture or the graphical keyboard other than a distance that the alignment point is away from a neighboring key of the graphical keyboard that is associated with the alternative character.

5. The method of claim 1, further comprising:

determining, by the computing device, a quantity of error correction operations applied to the initial plurality of characters; 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 initial plurality of characters by at least;

refraining from determining whether the alignment score of the gesture matches the selection of the initial plurality of characters with the additional character satisfies; and

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

6. The method of claim 1, further comprising:

determining, by the computing device and responsive to determining an alternative character for the alternative plurality of characters, 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.

7. The method of claim 1, wherein the second threshold is based on a quantity of a first subset of multiple characters associated with one or more alignment scores that are greater than alignment scores associated with multiple characters in a second subset of multiple characters.

14. The method of claim 1, wherein the first threshold and the second threshold are different thresholds.

15. The method of claim 1, further comprising:

responsive to determining that the alignment score of the gesture matching the selection of the initial plurality of characters with the additional character satisfies the first threshold, outputting, by the computing device and for display, the word in the dictionary as the candidate word without further determining whether the word in the dictionary is intended by the gesture.

16. The method of claim 1, wherein the correction data is determined from one or more rules indicating relationships between the one or more misspellings and the word in the dictionary.

20. The method of claim 1, wherein the correction data is determined from one or more rules indicating relationships between the one or more misspellings and the word in the dictionary.

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

detecting a gesture that selects one or more keys from a plurality of keys of a graphical keyboard;

generate, based on the one or more keys, an initial plurality of characters selected by the gesture;

update, based on a word in a dictionary, the initial plurality of characters to include an additional character not selected by the gesture;

determine whether an alignment score of the gesture matching a selection of the initial plurality of characters with the additional character satisfies a first threshold; and

responsive to determining that the alignment score of the gesture matching the selection of the initial plurality of characters with the additional character does not satisfy the first threshold, determine whether the word in the dictionary is intended by the gesture by at least;

determining that a substring of the initial plurality of characters matches at least a portion of an alternative plurality of characters intended by the gesture, wherein the alternative plurality of characters is determined from correction data that indicates one or more misspellings of the word in the dictionary;

determining whether an alternative alignment score of the gesture matching a selection of the at least a portion of the alternative plurality of characters satisfies a second threshold; and

responsive to determining that the alternative alignment score of the gesture matching the selection of the at least a portion of the alternative plurality of characters satisfies the second threshold, outputting, for display, the word in the dictionary as a candidate word.

9. The computer-readable storage medium of claim 8, wherein one or more misspellings of the word in the dictionary comprise a phonetic substitution of the substring of the initial plurality of characters.

10. The computer-readable storage medium of claim 8, wherein the at least one alternative character comprises a wildcard character that represents each possible character in a character set.

17. The computer-readable storage medium of claim 8, wherein the first threshold and the second threshold are different thresholds.

18. The computer-readable storage medium of claim 8, wherein the correction data is determined from one or more rules indicating relationships between the one or more misspellings and the word in the dictionary.

11. A computing device comprising:

a display configured to present a graphical keyboard comprising a plurality of keys;

a presence-sensitive input component configured to detect a gesture that selects one or more keys from the plurality of keys of the graphical keyboard; and

at least one processor configured to;

generate, based on the one or more keys, an initial plurality of characters selected by the gesture;

update, based on a word in a dictionary, the initial plurality of characters to include an additional character not selected by the gesture;

determine whether an alignment score of the gesture matching a selection of the initial plurality of characters with the additional character satisfies a first threshold; and

responsive to determining that an alignment score of the gesture matching the initial plurality of characters with the additional character does not satisfy a threshold, determine whether the word in the dictionary is intended by the gesture by at least;

determining that a substring of the initial plurality of characters matches at least a portion of an alternative plurality of characters intended by the gesture, wherein the alternative plurality of characters is determined from correction data that indicates one or more misspellings of the word in the dictionary;

determining whether an alternative alignment score of the gesture matching a selection of the at least a portion of the alternative plurality of characters satisfies a second threshold; and

responsive to determining that the alternative alignment score of the gesture matching the selection of the at least a portion of the alternative plurality of characters satisfies the second threshold, outputting, for display, the word in the dictionary as a candidate word.

12. The computing device of claim 11, wherein one or more misspellings of the word in the dictionary comprise a phonetic substitution of the substring of the initial plurality of characters.

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

generate the initial plurality of characters, update the initial plurality of characters, determine the alternative alignment score, and output the candidate word, while the presence-sensitive input component detects the gesture at the graphical keyboard.

19. The computing device of claim 11, wherein the first threshold and the second threshold are different thresholds.