Touch keyboard using language and spatial models

• US 8,832,589 B2
• Filed: 03/07/2013
• Issued: 09/09/2014
• Est. Priority Date: 01/15/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Zhai, Shumin, Chelba, Ciprian Ioan
• Primary Examiner(s): Pesin, Boris
• Assistant Examiner(s): Ell, Matthew
• Application Number:
  US13/789,106
• Publication Number:
  US 20140201671A1
• Time in Patent Office: 551 Days
• Field of Search: 715/773
• US Class Current: 715/783
• 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/242 Dictionaries
• CPC Class Codes: G06F 40/263 Language identification
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: H04L 51/02 using automatic reactions or user delegation, e.g. automatic replies or chatbot-generated messages
• CPC Class Codes: H04L 51/063 Content adaptation, e.g. replacement of unsuitable content

Abstract

A computing device outputs for display at a presence-sensitive display, a graphical keyboard comprising a plurality of keys, receives an indication of at least one gesture to select a group of keys of the plurality of keys, and determines at least one characteristic associated with the at least one gesture to select the group of keys of the plurality of keys. The computing device modifies a spatial model based at least in part on the at least one characteristic and determines a candidate word based at least in part on data provided by the spatial model and a language model, wherein the spatial model provides data based at least in part on the indication of the at least one gesture and wherein the language model provides data based at least in part on a lexicon. The computing device outputs for display at the presence-sensitive display, the candidate word.

Claims

1. A method comprising:

outputting, by a computing device and for display at a presence-sensitive display, a graphical keyboard comprising a plurality of keys;

receiving, by the computing device, an indication of at least one gesture to select at least one key of the plurality of keys;

determining, by the computing device, a location at the presence-sensitive display at which the at least one gesture to select the at least one key is detected;

modifying, by the computing device and based at least in part on a location of a next key of the plurality of keys relative to the location of the at least one gesture, a spatial model for the next key;

determining, by the computing device, a candidate word based at least in part on data provided by the modified spatial model and a language model, wherein the modified spatial model provides a first portion of the data based at least in part on an indication of at least one subsequent gesture and wherein the language model provides a second portion of the data based at least in part on a lexicon; and

outputting, by the computing device and for display at the presence-sensitive display, the candidate word.

2. The method of claim 1, further comprising determining an input speed associated with the at least one gesture,

wherein modifying the spatial model for the next key comprises, responsive to determining that the input speed satisfies a threshold value, modifying, by the computing device, a standard deviation value of the spatial model for the next key.

3. The method of claim 2, wherein modifying the standard deviation value of the spatial model for the next key comprises, responsive to determining that the input speed is greater than the threshold value, increasing the standard deviation value.

4. The method of claim 1, wherein modifying the spatial model for the next key comprises:

determining, by the computing device, a distance between the location of the at least one gesture and a statistical location of the spatial model for the next key; and

in response to determining that the distance satisfies the threshold value, modifying the statistical location based at least in part on the determined location.

5. The method of claim 4, wherein the statistical location is a first statistical location, wherein modifying the first statistical location comprises:

determining, by the computing device, a vertical modifier value by dividing a vertical component of the location of the at least one gesture by a positive integer value;

determining, by the computing device, a horizontal modifier value by dividing a horizontal component of the location of the at least one gesture by the positive integer value; and

determining, by the computing device, a second statistical location by adding the vertical modifier value to a vertical component of the first statistical location and adding the horizontal modifier value to a horizontal component of the first statistical location.

6. The method of claim 1, wherein modifying the spatial model for the next key comprises:

determining, by the computing device, a distance between the location of the at least one gesture and the location of the next key; and

in response to determining that the distance satisfies a threshold value, modifying, by the computing device and based at least in part on the determined distance, a standard deviation value of the spatial model for the next key.

7. The method of claim 1, further comprising:

receiving, by the computing device and subsequent to the modifying, an indication of the at least one subsequent gesture to select at least one subsequent key of the plurality of keys;

determining, by the computing device, a location at the presence-sensitive display at which the at least one subsequent gesture to select the at least one subsequent key is detected; and

modifying, by the computing device and based at least in part on the location of the next key relative to the location of the at least one subsequent gesture, the spatial model for the next key, and

wherein determining the candidate word is further based at least in part on data provided by the spatial model as modified based at least in part on the location of the next key relative to the location of the at least one subsequent gesture.

8. The method of claim 1, wherein the location of the at least one gesture corresponds to a row of keys of the graphical keyboard, and wherein modifying the spatial model for the next key comprises:

determining, by the computing device, whether the next key is located in the row of keys of the graphical keyboard; and

in response to determining that the next key is located in the row of keys, modifying, by the computing device, a standard deviation value of the spatial model for the next key.

9. The method of claim 8, wherein modifying the standard deviation value of the spatial model for the next key comprises increasing, by the computing device, a horizontal standard deviation value of the spatial model for the next key while maintaining a vertical standard deviation value of the spatial model for the next key.

10. The method of claim 1, wherein the candidate word is a first candidate word, the method further comprising:

determining, by the computing device, a second candidate word based at least in part on one or more words displayed in a text area of the presence-sensitive display; and

outputting, for display at the presence-sensitive display, the second candidate word subsequent to the one or more words displayed in the text area.

11. The method of claim 10, wherein determining the second candidate word comprises:

determining, by the computing device and based at least in part on the language model, at least one frequency value, wherein the at least one frequency value is associated with a sequence of words, and wherein the frequency value represents a frequency of occurrence of the sequence of words in an n-gram dictionary of the language model; and

selecting, by the computing device, the second candidate word based at least in part on the at least one frequency value.

12. The method of claim 1, wherein determining the candidate word comprises:

determining, by the computing device and based at least in part on the modified spatial model, at least one candidate string and at least one cost value; and

determining, by the computing device and based at least in part on the language model, the candidate word,

wherein the candidate word includes the at least one candidate string as a prefix, and

wherein the candidate word is associated with a predicted cost value, the predicted cost value being based at least in part on the at least one cost value of the at least one candidate string.

13. The method of claim 12, wherein the at least one gesture comprises a plurality of tap gestures and wherein determining a plurality of candidate strings and associated cost values comprises:

determining a plurality of tap locations each associated with a respective tap gesture of the plurality of tap gestures;

determining respective cost values for each of at least two keys of the plurality of keys, wherein each of the respective cost values represents a probability that a tap location of the plurality of tap locations indicates a key of the plurality of keys; and

comparing the respective cost values for each of at least two keys of the plurality of keys to determine a candidate string having a combined cost value.

14. The method of claim 1, wherein determining the candidate word comprises:

determining, by the computing device and based at least in part on the language model, at least one frequency value, wherein the at least one frequency value is associated with a respective sequence of characters, and wherein the at least one frequency value represents a respective frequency of occurrence of the respective sequence of characters in the lexicon; and

selecting, by the computing device and based at least in part on the determined at least one frequency value, the candidate word.

15. The method of claim 1, wherein the indication of the at least one subsequent gesture comprises an indication of at least one gesture to select the next key.

16. The method of claim 1, wherein modifying the spatial model comprises modifying at least one of:

a standard deviation value of the spatial model, a statistical location value of the spatial model, and a covariance value of the spatial model.

17. The method of claim 1, wherein the at least one gesture comprises at least one sliding gesture.

18. The method of claim 1, wherein outputting the candidate word comprises:

outputting, by the computing device and for display at the presence-sensitive display, characters of the candidate word associated with the at least one key in a first visual style; and

outputting, by the computing device and for display at the presence-sensitive display;

characters of the candidate word that are not associated with the at least one key in a second visual style.

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

outputting, for display at a presence-sensitive display, a graphical keyboard comprising a plurality of keys;

receiving an indication of at least one gesture to select at least one key of the plurality of keys;

determining a location at the presence-sensitive display at which the at least one gesture to select the at least one key is detected;

modifying, based at least in part on a location of a next key of the plurality of keys relative to the location of the at least one gesture, a spatial model for the next key;

determining a candidate word based at least in part on data provided by the modified spatial model and a language model, wherein the modified spatial model provides a first portion of the data based at least in part on an indication of at least one subsequent gesture and wherein the language model provides a second portion of the data based at least in part on a lexicon; and

outputting, for display at the presence-sensitive display, the candidate word.

20. A computing device comprising:

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

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

output, for display at the presence-sensitive display, a graphical keyboard comprising a plurality of keys;

receive, at the presence-sensitive display, an indication of at least one gesture to select at least one key of the plurality of keys;

determine a location at the presence-sensitive display at which the at least one gesture to select the at least one key is detected;

modify, based at least in part on a location of a next key of the plurality of keys relative to the location of the at least one gesture, a spatial model for the next key;

determine a candidate word based at least in part on data provided by the modified spatial model and a language model, wherein the modified spatial model provides a first portion of the data based at least in part on an indication of at least one subsequent gesture and wherein the language model provides a second portion of the data based at least in part on a lexicon; and

output, for display at the presence-sensitive display, the candidate word.