Multi-gesture text input prediction

• US 9,710,453 B2
• Filed: 09/04/2014
• Issued: 07/18/2017
• 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): Tran, Tuyetlien T
• Application Number:
  US14/477,404
• Publication Number:
  US 20150082229A1
• Time in Patent Office: 1,048 Days
• Field of Search: 715773, 715863, 715864
• 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:

displaying, by a computing device, a plurality of alphabet characters and a spacebar;

receiving, by the computing device, an indication of a first gesture that selects a first set of alphabet characters from the plurality of alphabet characters, wherein the first gesture does not select the spacebar;

determining, by the computing device and based at least in part on the first set of alphabet characters, a first candidate string;

displaying, by the computing device, the first candidate string; and

after receiving the indication of the first gesture, after displaying the first candidate string, and prior to receiving any indications of gestures that select the spacebar;

receiving, by the computing device, an indication of a second gesture that selects a second set of alphabet characters from the plurality of alphabet characters, wherein the second gesture is disjoint from the first gesture and does not select the spacebar;

determining, by the computing device, whether the second set of alphabet characters is included in the first candidate string;

responsive to determining that the second set of alphabet characters is included in the first candidate string, continuing, by the computing device, the displaying of the first candidate string; and

responsive to determining that the second set of alphabet characters is not included in the first candidate string;

determining, by the computing device, a second candidate string that includes the second set of alphabet characters; and

displaying, by the computing device, the second candidate string and one or more space characters that separate the first candidate string from the second candidate string.

2. The method of claim 1, wherein the first set of alphabet characters comprises a portion of the first candidate string.

3. The method of claim 1, wherein the second candidate string is further determined based at least in part on both a language model and a spatial model.

4. The method of claim 3, wherein:

the language model generates lexical cost values based at least in part on N-gram frequency information;

the spatial model generates locational cost values based at least in part on at least one location of the second gesture with respect to a location of a character from the plurality of alphabet characters; and

the second candidate string is further determined, based at least in part on the lexical cost values and the locational cost values.

5. The method of claim 1, wherein the first gesture comprises a continuous motion gesture and wherein the second gesture comprises a tap gesture.

6. The method of claim 1, further comprising:

displaying, by the computing device, a graphical keyboard comprising a plurality of keys,

wherein each of the plurality of alphabet characters and the spacebar corresponds to a respective key of the plurality of keys.

7. The method of claim 6, wherein the first candidate string, the second candidate string, and the one or more space characters that separate the first candidate string from the second candidate string are displayed in a suggestion region of the graphical keyboard.

8. The method of claim 1, wherein the first candidate string, the second candidate string, and the one or more space characters that separate the first candidate string from the second candidate string are displayed in a text display region of a graphical user interface.

9. A computing device comprising:

a display;

at least one processor; and

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

display, at the display, a plurality of alphabet characters;

receive an indication of a first gesture that selects a first set of alphabet characters from the plurality of alphabet characters, wherein the first gesture does not select the spacebar;

determine, based at least in part on the first set of alphabet characters, a first candidate string;

display the first candidate string; and

after receiving the indication of the first gesture, after displaying the first candidate string, and prior to receiving any indications of gestures that select the spacebar, receive an indication of a second gesture that selects a second set of alphabet characters from the plurality of alphabet characters, wherein the second gesture is disjoint from the first gesture and does not select the spacebar;

determine whether the second set of alphabet characters is included in the first candidate string;

responsive to determining that the second set of alphabet characters is included in the first candidate string, continue the display of the first candidate string; and

responsive to determining that the second set of alphabet characters is not included in the first candidate string;

determine a second candidate string that includes the second set of alphabet characters; and

display, at the display, the second candidate string and one or more space characters that separate the first candidate string from the second candidate string.

10. The computing device of claim 9, wherein the at least one module is operable by the at least one processor to determine the second candidate string in response to determining that the second set of alphabet characters is not included in the first candidate string word.

11. The computing device of claim 9, wherein the first set of alphabet characters comprises a portion of the first candidate word.

12. The computing device of claim 9, wherein the at least one module is operable by the at least one processor to determine the second candidate string based at least in part on both a language model and a spatial model.

13. The computing device of claim 12, wherein:

the language model generates lexical cost values based at least in part on N-gram frequency information;

the spatial model generates locational cost values based at least in part on at least one location of the second gesture with respect to a location of a character from the plurality of alphabet characters; and

the at least one module is operable by the at least one processor to further determine the second candidate string, based at least in part on the lexical cost values and the locational cost values.

14. The computing device of claim 9, wherein each of the first gesture and the second gesture comprises a respective continuous motion gesture.

15. The computing device of claim 9, wherein the at least one module is further operable by the at least one processor to:

display, at the display, a graphical keyboard comprising a plurality of keys,

wherein each of the plurality of alphabet characters and the spacebar corresponds to a respective key of the plurality of keys.

16. The computing device of claim 15, wherein the at least one module is further operable by the at least one processor to display, at the display, the first candidate string, the second candidate string, and the one or more space characters that separate the first candidate string from the second candidate string in a suggestion region of the graphical keyboard.

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

display, at the display, a plurality of alphabet characters;

receive an indication of a first gesture that selects a first set of alphabet characters from the plurality of alphabet characters, wherein the first gesture does not select the spacebar;

determine, based at least in part on the first set of alphabet characters, a first candidate string;

display the first candidate string; and

after receiving the indication of the first gesture, after displaying the first candidate string, and prior to receiving any indications of gestures that select the spacebar, receive an indication of a second gesture that selects a second set of alphabet characters from the plurality of alphabet characters, wherein the second gesture is disjoint from the first gesture and does not select the spacebar;

determine whether the second set of alphabet characters is included in the first candidate string; and

responsive to determining that the second set of alphabet characters is included in the first candidate string, continue the display of the first candidate string; and

responsive to determining that the second set of alphabet characters is not included in the first candidate string;

determine a second candidate string that includes the second set of alphabet characters; and

display, at the display, the second candidate string and one or more space characters that separate the first candidate string from the second candidate string.

18. The non-transitory computer-readable storage medium of claim 17, wherein the instructions that cause the at least one processor to determine the second candidate string in response to determining that the second set of alphabet characters is not included in the first candidate string word.

19. The non-transitory computer-readable storage medium of claim 17, wherein:

the instructions that cause the at least one processor to display, at the display the second candidate string and the one or more space characters that separate the first candidate string from the second candidate string in a suggestion region of a graphical keyboard comprising a plurality of keys,

each of the plurality of alphabet characters and the spacebar corresponds to a respective key of the plurality of keys.