Incremental multi-word recognition

• US 9,542,385 B2
• Filed: 09/11/2015
• Issued: 01/10/2017
• Est. Priority Date: 10/16/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Zhai, Shumin, Ouyang, Yu, Wakasa, Ken, Kataoka, Satoshi
• Primary Examiner(s): Nguyen, Kevin
• Application Number:
  US14/851,759
• Publication Number:
  US 20150378983A1
• Time in Patent Office: 487 Days
• Field of Search: 715/723, 715/72, 715780-781, 715863-864, 715/825, 715/835, 715/773
• US Class Current: 1/1
• 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/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
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates

Abstract

In one example, a computing device includes at least one processor that is operatively coupled to a presence-sensitive display and a gesture module operable by the at least one processor. The gesture module may be operable by the at least one processor to output, for display at the presence-sensitive display, a graphical keyboard comprising a plurality of keys and receive an indication of a continuous gesture detected at the presence-sensitive display, the continuous gesture to select a group of keys of the plurality of keys. The gesture module may be further operable to determine, in response to receiving the indication of the continuous gesture and based at least in part on the group of keys of the plurality of keys, a candidate phrase comprising a group of candidate words.

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, a plurality of indications of gestures detected at a presence-sensitive input device, a first indication of the plurality of indications of gestures being associated with traversal of a first key from the plurality of keys and a second indication of the plurality of indications of gestures being associated with traversal of a second key from the plurality of keys, wherein a first character is associated with the first key and a second character is associated with the second key;

outputting, by the computing device and based at least in part on the first and second indications of the plurality of indications of gestures traversing the first key and subsequently the second key, a candidate phrase comprising a group of candidate words, wherein at least one of a first candidate word or a second candidate word from the group of candidate words comprises the second character subsequent to the first character;

determining, by the computing device and based at least in part on the candidate phrase, a next word that is subsequent to the first candidate word and the second candidate word in the candidate phrase; and

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

2. The method of claim 1, further comprising:

selecting, by the computing device and based at least in part on the plurality of indications of gestures, the first key and the second key of the plurality of keys;

determining, by the computing device and based at least in part on the first key, a word-level token comprising a single string of a plurality of predicted characters;

determining, by the computing device, that the word-level token represents a candidate word included in a lexicon; and

determining, by the computing device and in response to determining that the word-level token represents the candidate word in the lexicon, a phrase-level token based at least in part on the word-level token and the second key, wherein the phrase-level token comprises a plurality of character strings.

3. The method of claim 2, further comprising:

determining, by the computing device, the candidate phrase based at least in part on the phrase-level token.

4. The method of claim 2, wherein the plurality of character strings of the phrase-level token comprises a first character string and a second character string, wherein the word-level token comprises the first character string.

5. The method of claim 2, wherein the word-level token comprises a first word-level token comprising a first single string of the plurality of predicted characters, the method further comprising:

determining, by the computing device and based at least in part on the first key and the second key, a second word-level token comprising a second single string of the plurality of predicted characters.

6. The method of claim 5, wherein determining the phrase-level token further comprises:

determining, based on a plurality of features associated with the plurality of indications of gestures, a group of alignment points traversed by the plurality of indications of gestures;

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

determining a first combined cost value based at least in part on the cost value for the first key and the cost value for the second key;

determining a second combined cost value based at least in part on the cost value for the first key and the cost value for the third key;

comparing the first combined cost value and the second combined cost value; and

determining the second word-level token based on the comparing of the first combined cost value and the second combined cost value.

7. The method of claim 6, wherein the plurality of features associated with the plurality of indications of gestures comprises at least one of:

a length of a segment of the plurality of indications of gestures, wherein the segment comprises a path traversed by the plurality of indications of gestures;

a direction of the segment of the plurality of indications of gestures;

a curvature of the segment of the plurality of indications of gestures;

a local speed that represents a rate at which the segment of the plurality of indications of gestures was detected; and

a global speed that represents a rate at which the plurality of indications of gestures was detected.

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

determining respective physical cost values for each of at least the first key, the second key, and the third 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 respective lexical cost values for each of at least the first key, the second key, and the third key, wherein each of the respective lexical cost values represents a probability that a letter represented by a key of the plurality of keys is included in a candidate word; and

determining the respective cost values for each of at least the first key, the second key, and the third key based on the respective physical cost values and the respective lexical cost values for each of at least the first key, the second key, and the third key.

9. The method of claim 2, wherein the phrase-level token is a first phrase-level token comprising a first plurality of character strings, the method further comprising:

determining, by the computing device, that the first phrase-level token satisfies a threshold;

responsive to determining that the first phrase-level token satisfies the threshold, selecting, by the computing device, a character string of the first plurality of character strings of the first phrase-level token as a committed character string; and

removing, by the computing device, the committed character string from the first plurality of character strings of the phrase-level token to determine a second phrase-level token comprising a second plurality of character strings.

10. The method of claim 9, further comprising:

outputting, by the computing device and based at least in part on the first phrase-level token, the candidate phrase for display at a text-suggestion region; and

responsive to determining that the first phrase-level token satisfies the threshold;

outputting, by the computing device, the committed character string for display at a committed-text region, wherein the committed-text region is different than the text-suggestion region; and

outputting, by the computing device, the second plurality of character strings for display at the text-suggestion region.

11. The method of claim 9, wherein determining that the first phrase-level token satisfies the threshold comprises determining that a number of character strings of the first plurality of character strings satisfies a threshold number of character strings.

12. The method of claim 2, wherein determining the phrase-level token further comprises determining that the phrase-level token includes at least one delimiter character, the at least one delimiter character being positioned between a first character string and a second character string of the plurality of character strings.

13. The method of claim 1,

wherein the graphical keyboard is included in a graphical user interface that is output for display by the computing device,

wherein the graphical user interface includes a committed-text region, and

wherein the candidate phrase is included in the committed-text region.

14. The method of claim 2,

wherein the graphical user interface includes at least one text-suggestion region, and

wherein the next word is included in the at least one text-suggestion region.

15. The method of claim 2, wherein the plurality of indications of the gestures are a part of a single continuous gesture.

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

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

receive, a plurality of indications of gestures detected at a presence-sensitive input device, a first indication of the plurality of indications of gestures being associated with traversal of a first key from the plurality of keys and subsequently a second indication of the plurality of indications of gestures being associated with traversal of a second key of the plurality of keys, wherein a first character is associated with the first key and a second character is associated with the second key;

output, based at least in part on the first and second indications of the plurality of indications of gestures traversing the first key and subsequently the second key, a candidate phrase comprising a group of candidate words, wherein at least one of a first candidate word or a second candidate word from the group of candidate words comprises the second character subsequent to the first character;

determine, based at least in part on the candidate phrase, a next word that is subsequent to the first candidate word and the second candidate word in the candidate phrase; and

output, for display, the next word.

17. The non-transitory computer-readable storage medium of claim 16 encoded with instructions that, when executed, cause the at least one processor of the computing device to:

select, based at least in part on the plurality of indications of gestures, the first key and the second key of the plurality of keys;

determine, based at least in part on the first key, a word-level token comprising a single string of a plurality of predicted characters;

determine that the word-level token represents a candidate word included in a lexicon; and

determine, in response to determining that the word-level token represents the candidate word in the lexicon, a phrase-level token based at least in part on the word-level token and the second key, wherein the phrase-level token comprises a plurality of character strings.

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

wherein the graphical keyboard is included in a graphical user interface that is output for display by the computing device,

wherein the graphical user interface includes a committed-text region, and

wherein the candidate phrase is included in the committed-text region.

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

wherein the graphical user interface includes at least one text-suggestion region, and

wherein the next word is included in the at least one text-suggestion region.

20. A device comprising:

one or more computer processors; and

a memory comprising instructions that when executed by the one or more computer processors cause the one or more computer processors to;

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

receive a plurality of indications of gestures detected at a presence-sensitive input device, a first indication of the plurality of indications of gestures being associated with traversal of a first key from the plurality of keys and subsequently a second indication of the plurality of indications of gestures being associated with traversal of a second key of the plurality of keys, wherein a first character is associated with the first key and a second character is associated with the second key;

output, based at least in part on the first and second indications of the plurality of indications of gestures traversing the first key and subsequently the second key, a candidate phrase comprising a group of candidate words, wherein at least one of a first candidate word or a second candidate word from the group of candidate words comprises the second character subsequent to the first character;

determine, based at least in part on the candidate phrase, a next word that is subsequent to the first candidate word and the second candidate word in the candidate phrase; and

output, for display, the next word.

21. The device of claim 20, wherein the instructions when executed by the one or more computer processors cause the one or more computer processors to:

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

receive, a plurality of indications of gestures detected at a presence-sensitive input device, a first indication of the plurality of indications of gestures traversing a first key and subsequently a second indication of the plurality of indications of gestures traversing a second key, wherein a first character is associated with the first key and a second character is associated with the second key;

output, based at least in part on the first and second indications of the plurality of indications of gestures traversing the first key and subsequently the second key, a candidate phrase comprising a group of candidate words, wherein at least one of a first candidate word and a second candidate word from the group of candidate words comprises the second character subsequent to the first character;

determine, based at least in part on the candidate phrase, a next word that is subsequent to the first candidate word and the second candidate word; and

output, for display, the next word.

22. The device of claim 20,

wherein the graphical keyboard is included in a graphical user interface that is output for display by the computing device,

wherein the graphical user interface includes a committed-text region, and

wherein the candidate phrase is included in the committed-text region.

23. The device of claim 20,

wherein the graphical user interface includes at least one text-suggestion region, and

wherein the next word is included in the at least one text-suggestion region.