Multi-gesture text input prediction

• US 8,843,845 B2
• Filed: 04/08/2013
• Issued: 09/23/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, Bi, Xiaojun
• Primary Examiner(s): ITURRALDE, ENRIQUE W
• Application Number:
  US13/858,684
• Publication Number:
  US 20140104177A1
• Time in Patent Office: 533 Days
• Field of Search: 715/780, 715/221, 715/223, 715255-257, 715/705, 715/710, 715/714, 715/727, 715/728, 715/809, 715/816
• US Class Current: 715/773
• CPC Class Codes: G06F 3/017 Gesture based interaction, e.g. based on a set of recognized hand gestures interaction based on gestures traced on a digitiser G06F3/04883
• CPC Class Codes: G06F 3/0237 using prediction or retrieval techniques
• CPC Class Codes: G06F 3/04842 Selection of displayed objects or displayed text elements G06F3/0482 takes precedence
• 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/274 Converting codes to words; Guess-ahead of partial word inputs

Abstract

A computing device outputs a keyboard for display, receives an indication of a first gesture to select a first sequence of one or more keys, determines a set of candidate strings based in part on the first sequence of keys, and outputs for display at least one of the set of candidate strings. The computing device receives an indication of a second gesture to select a second sequence of one or more keys, and determines that characters associated with the second sequence of keys are included in a first candidate word based at least in part on the set of candidate strings, or are included in a second candidate word not based on the first sequence of keys. The computing device modifies the set of candidate strings based at least in part on the determination and outputs for display at least one of the modified candidate strings.

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 first gesture detected at a presence-sensitive input device, the first gesture to select a first sequence of one or more keys from the plurality of keys;

determining, by the computing device, a set of candidate strings based at least in part on characters associated with the first sequence of one or more keys;

outputting, by the computing device and for display, at least one of the set of candidate strings;

receiving, by the computing device, an indication of a second gesture detected at the presence-sensitive input device, the second gesture to select a second sequence of one or more keys from the plurality of keys;

determining, by the computing device, whether characters associated with the second sequence of one or more keys are included in a first candidate word of a lexicon, the first candidate word being based at least in part on the characters associated with the first sequence of one or more keys, and;

if the computing device determines that the characters associated with the second sequence of one or more keys are included in the first candidate word, modifying, by the computing device, the set of candidate strings based at least in part on the first candidate word, and

if the computing device determines that the characters associated with the second sequence of one or more keys are not included in the first candidate word, modifying, by the computing device, the set of candidate strings based at least in part on a second candidate word of the lexicon, the second candidate word not being based on the characters associated with the first sequence of one or more keys; and

outputting, by the computing device and for display, at least one of the modified set of candidate strings.

2. The method of claim 1, further comprising outputting, by the computing device and for display, one or more auto-completion suggestions overlaid on the graphical keyboard, wherein the one or more auto-completion suggestions are based at least in part on the set of candidate strings.

3. The method of claim 2, further comprising:

receiving, by the computing device, an indication of a third gesture to select an auto-completion suggestion from the one or more auto-completion suggestions; and

outputting, by the computing device and for display, a hard-commit word, wherein the hard-commit word is based at least in part on the selected auto-completion suggestion.

4. The method of claim 1, wherein at least one of the candidate strings comprises a plurality of words.

5. The method of claim 1, wherein the second gesture comprises a tap gesture to select a key.

6. The method of claim 1, wherein determining whether the characters associated with the second sequence of one or more keys are included in the first candidate word comprises:

determining, by the computing device, a first candidate string in which the characters associated with the second sequence of one or more keys are included in the first candidate word;

determining, by the computing device, a second candidate string in which the characters associated with the second sequence of one or more keys are included in the second candidate word; and

comparing, by the computing device, a cost value associated with the first candidate string and a cost value associated with the second candidate string, wherein the first and second cost values are determined based at least in part on the lexicon.

7. The method of claim 6, wherein the first candidate word comprises a predicted word that is based at least in part on the set of candidate strings.

8. The method of claim 1, wherein at least one candidate string of the set of candidate strings is associated with a cost value, the method further comprising:

outputting, by the computing device and for display, a text display region;

determining, by the computing device, the cost value associated with at least one candidate string based at least in part on the characters associated with the first sequence of one or more keys; and

outputting, by the computing device and for display, a soft-commit word in the text display region, wherein the soft-commit word is determined based at least in part on the candidate string having a lowest associated cost value.

9. The method of claim 1, further comprising outputting, by the computing device and for display, at least one suggestion region, wherein:

the at least one candidate string of the set of candidate strings is output in the suggestion region; and

the at least one candidate string of the set of modified candidate strings is output in the suggestion region.

10. The method of claim 1, wherein at least one candidate string of the set of candidate strings is associated with a cost value, and wherein the set of candidate strings includes only candidate strings associated with respective cost values that satisfy a threshold cost value.

11. The method of claim 1, wherein the lexicon is implemented, by the computing device, as a trie data structure.

12. The method of claim 11, wherein determining the set of candidate strings further comprises:

determining, by the computing device, a first word-level token originating at an entry node of the trie; and

advancing, by the computing device, the first word-level token to a child node of the trie based at least in part on the characters associated with the first sequence of one or more keys.

13. The method of claim 12, further comprising:

determining, by the computing device, that the first word-level token is at a terminal node of the lexicon trie;

determining, by the computing device, a phrase-level token;

adding, by the computing device and to the phrase-level token, the first word-level token;

determining, by the computing device, a second word-level token; and

adding, by the computing device, the second word-level token to the phrase-level token.

14. The method of claim 1, wherein the indication of the first gesture includes a group of alignment points traversed by the gesture, the alignment points determined based on a plurality of features associated with the first gesture, the method further comprising:

determining, by the computing device, respective cost values for at least a first key and a second key, wherein the respective cost values represent a probability that an alignment point of the group of alignment points indicates a key included in the plurality of keys;

determining, by the computing device, at least one candidate string including a character associated with the first key, the candidate string having an associated cost value based at least in part on the cost value for the first key;

determining, by the computing device, at least one candidate string including a character associated with the second key, the candidate string having an associated cost value based at least in part on the cost value for the second key; and

adding, by the computing device, the determined candidate strings to the set of candidate strings.

15. The method of claim 14, wherein determining the respective cost values for each of at least the first key and the second key comprises:

determining, by the computing device, respective physical cost values for each of at least the first key and the second key, wherein each of the respective physical cost values represents a probability that at least one physical feature of an alignment point of the group of alignment points indicates at least one physical feature of a key of the plurality of keys;

determining, by the computing device, respective lexical cost values for each of at least the character associated with the first key and the character associated with the second key, wherein each of the respective lexical cost values represents a probability that a character associated with a key of the plurality of keys is included in a word in the lexicon; and

determining, by the computing device, the respective cost values for each of at least the first key and the second key based on the respective physical cost values for each of at least the first key and the second key and the respective lexical cost values for each of at least the character associated with the first key and the character associated with the second key.

16. The method of claim 15, wherein determining the respective lexical cost values for each of at least the character associated with the first key and the character associated with the second key comprises comparing each of at least the character associated with the first key and the character associated with the second key with a language model.

17. The method of claim 16, wherein the language model comprises an n-gram language model.

18. The method of claim 7 wherein the predicted word that is based at least in part on the set of candidate strings comprises the characters contained in one of the set of candidate strings.

19. The method of claim 1, wherein the presence-sensitive input device is included in a presence-sensitive display device, the presence-sensitive display device further comprising a display device.

20. A computer-readable storage device encoded with instructions that, when executed, cause one or more processors of a computing device to perform operations comprising:

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

receiving an indication of a first gesture detected at a presence-sensitive input device, the first gesture to select a first sequence of one or more keys from the plurality of keys;

determining a set of candidate strings based at least in part on characters associated with the first sequence of one or more keys;

outputting, for display, at least one of the set of candidate strings;

receiving an indication of a second gesture detected at the presence-sensitive input device, the second gesture to select a second sequence of one or more keys from the plurality of keys;

determining whether characters associated with the second sequence of one or more keys are included in a first candidate word of a lexicon, the first candidate word being based at least in part on the characters associated with the first sequence of one or more keys, and;

if the computing device determines that the characters associated with the second sequence of one or more keys are included in the first candidate word, modifying, by the computing device, the set of candidate strings based at least in part on the first candidate word, and

if the computing device determines that the characters associated with the second sequence of one or more keys are not included in the first candidate word, modifying, by the computing device, the set of candidate strings based at least in part on a second candidate word of the lexicon, the second candidate word not being based on the characters associated with the first sequence of one or more keys; and

outputting, for display, at least one of the modified set of candidate strings.

21. A computing device, comprising:

one or more processors; and

a memory storing instructions that when executed by the one or more processors, cause the one or more processors to;

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

receive an indication of a first gesture detected at an input device, the first gesture to select a first sequence of one or more keys from the plurality of keys;

determine a set of candidate strings based at least in part on characters associated with the first sequence of one or more keys;

output, for display, at least one of the set of candidate strings;

receive an indication of a second gesture detected at the input device, the second gesture to select a second sequence of one or more keys from the plurality of keys;

determine whether characters associated with the second sequence of one or more keys are included in a first candidate word of a lexicon, the first candidate word being based at least in part on the characters associated with the first sequence of one or more keys, and;

if the computing device determines that the characters associated with the second sequence of one or more keys are included in the first candidate word, modifying, by the computing device, the set of candidate strings based at least in part on the first candidate word, and

if the computing device determines that the characters associated with the second sequence of one or more keys are not included in the first candidate word, modifying, by the computing device, the set of candidate strings based at least in part on a second candidate word of the lexicon, the second candidate word not being based on the first sequence of one or more keys; and

output, for display, at least one of the modified set of candidate strings.