Incremental multi-word recognition

• US 9,134,906 B2
• Filed: 03/04/2014
• Issued: 09/15/2015
• 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/196,552
• Publication Number:
  US 20140189568A1
• Time in Patent Office: 560 Days
• Field of Search: 715/773, 715/702, 715780-781, 715/705, 715863-864, 715816-817, 715/825, 715/835
• 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, an indication of a continuous gesture detected at a presence-sensitive input device, a portion of the continuous gesture traversing a first key and subsequently a second key in the plurality of keys, wherein a first character is associated with the first key and a second character is associated with the second key;

determining, by the computing device and based at least in part on the portion of the continuous gesture 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; and

outputting, by the computing device and for display, based at least in part on the group of candidate words, the candidate phrase comprising the first candidate word and the second candidate word.

2. The method of claim 1, further comprising:

selecting, by the computing device and based at least in part on the indication of the continuous gesture, 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 gesture, a group of alignment points traversed by the gesture;

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 gesture comprises at least one of:

a length of a segment of the gesture, wherein the segment comprises a path traversed by the gesture;

a direction of the segment of the gesture;

a curvature of the segment of the gesture;

a local speed that represents a rate at which the segment of the gesture was detected; and

a global speed that represents a rate at which the gesture 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, the first phrase-level token 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. 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 an indication of a continuous gesture detected at a presence-sensitive input device, a portion of the continuous gesture traversing a first key and subsequently a second key in the plurality of keys, wherein a first character is associated with the first key and a second character is associated with the second key;

determine based at least in part on the portion of the continuous gesture 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; and

output, for display and based at least in part on the group of candidate words, the candidate phrase comprising the first candidate word and the second candidate word.

14. The computer-readable storage medium of claim 13 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 indication of the continuous gesture, 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, responsive 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.

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

determine, responsive to determining the phrase-level token, the candidate phrase based at least in part on the phrase-level token.

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

determine 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.

17. A device comprising:

at least one processor that is operatively coupled to a presence-sensitive input device; and

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

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

receive an indication of a continuous gesture detected at a presence-sensitive input device, a portion of the continuous gesture traversing a first key and subsequently a second key in the plurality of keys, wherein a first character is associated with the first key and a second character is associated with the second key;

determine based at least in part on the portion of the continuous gesture 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; and

output, for display and based at least in part on the group of candidate words, the candidate phrase comprising the first candidate word and the second candidate word.

18. The device of claim 17, wherein the at least one module is operable to:

select, based at least in part on the indication of the continuous gesture, 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, responsive 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.

19. The device of claim 18, wherein the at least one module is operable to:

determine, responsive to determining the phrase-level token, the candidate phrase based at least in part on the phrase-level token.

20. The device of claim 18, wherein the at least one module is operable to:

determine 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.

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

determining, 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 and a second candidate word from the group of candidate words comprises the second character subsequent to the first character; and

outputting, by the computing device and for display, based at least in part on the group of candidate words, the candidate phrase comprising the first candidate word and the second candidate word.

24. The method of claim 21, further comprising:

selecting, by the computing device and based at least in part on the first indication and the second indication, 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.

25. The method of claim 24, further comprising:

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

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

determine 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; and

output, for display, based at least in part on the group of candidate words, the candidate phrase comprising the first candidate word and the second candidate word.

26. The non-transitory computer-readable storage medium of claim 22, further encoded with instructions that, when executed, cause at least one processor of a computing device to:

select, based at least in part on the first indication and the second indication, 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.

27. The non-transitory computer-readable storage medium of claim 26, further encoded with instructions that, when executed, cause at least one processor of a computing device to:

determine the candidate phrase based at least in part on the phrase-level token.

23. A device comprising:

at least one processor that is operatively coupled to a presence-sensitive input device; and

at least one module operable by the at least one processor 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;

determine 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; and

output, for display, based at least in part on the group of candidate words, the candidate phrase comprising the first candidate word and the second candidate word.

28. The device of claim 23, wherein the at least one module is operable by the at least one processor to:

select, based at least in part on the first indication and the second indication, 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.

29. The device of claim 28, wherein the at least one module is operable by the at least one processor to:

determine the candidate phrase based at least in part on the phrase-level token.