Gesture keyboard input of non-dictionary character strings using substitute scoring

• US 8,756,499 B1
• Filed: 04/29/2013
• Issued: 06/17/2014
• Est. Priority Date: 04/29/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kataoka, Satoshi, Kuroyanagi, Keisuke
• Primary Examiner(s): RIES, LAURIE ANNE
• Application Number:
  US13/872,937
• Time in Patent Office: 414 Days
• Field of Search: 715/259
• US Class Current: 715/259
• 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

Abstract

In one example, a computing device may include at least one processor that outputs a graphical keyboard. The at least one processor may determine a selection of one or more keys; and determine a character string based on the one or more keys in the selection, wherein the character string is not included in a vocabulary used by the computing device to identify character strings. The at least one processor may, in response to determining that the character string is not included in the vocabulary used by the computing device to identify character strings, associate the character string with an out-of-vocabulary language model score; and determine, based at least in part on a spatial model score associated with the gesture and the out-of-vocabulary language model score, a combined score that indicates a probability that the character string corresponds to the gesture; and output for display the character string.

Claims

1. A method comprising:

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

responsive to receiving an indication of a gesture detected at a presence-sensitive input device, determining, by the computing device, a selection of one or more of the plurality of keys;

determining, by the computing device, a character string based on the one or more of the plurality of keys of the selection, wherein the character string is not included in a vocabulary used by the computing device to identify character strings;

responsive to determining that the character string is not included in the vocabulary used by the computing device to identify character strings, associating, by the computing device, the character string with an out-of-vocabulary language model score, the out-of-vocabulary language model score being a substitute score that is determined without application of a language model to the character string;

determining, by the computing device and based at least in part on a spatial model score associated with the gesture and the out-of-vocabulary language model score, a combined score that indicates a probability that the character string corresponds to the gesture; and

outputting, by the computing device and for display, the character string.

2. The method of claim 1, wherein associating the character string with the out-of-vocabulary language model score further comprises:

determining, by the computing device, for each respective character string from a plurality of character strings included in the vocabulary, a respective probability associated with the respective character string from a plurality of probabilities;

determining, by the computing device, a lowest probability included in the plurality of probabilities; and

using, by the computing device, the lowest probability as the out-of-vocabulary language model score.

3. The method of claim 1, wherein associating the character string with the out-of-vocabulary language model score further comprises:

in response to determining that the character string is not included in the vocabulary used by the computing device to identify character strings, selecting, by the computing device, a predefined value as the out-of-vocabulary language model score.

4. The method of claim 1, wherein the character string is an out-of-vocabulary character string, the method further comprising:

determining, by the computing device, a plurality of different character strings corresponding to the one or more of the plurality of keys in the selection, wherein each of the plurality of different character strings is included in the vocabulary;

determining, by the computing device, a respective language model score for each different character string of the plurality of different character strings;

determining, by the computing device, a respective combined score for each different character string of the plurality of character strings, the respective combined score based at least in part on the spatial model score and the respective language model score for the respective different character string of the plurality of character strings; and

in response to determining that the respective combined score for at least one of the different character strings of the plurality of character strings satisfies a threshold, outputting, by the computing device and for display, the at least one of the different strings with the out-of-vocabulary character string.

5. The method of claim 1, wherein the character string is an out-of-vocabulary character string, further comprising:

determining, by the computing device, a plurality of character string suggestion regions in a graphical user interface that is output for display by the computing device;

determining, by the computing device, a plurality of different character strings corresponding to the one or more of the plurality of keys in the selection, wherein each different character string of the plurality of different character strings is included in the vocabulary;

determining, by the computing device, a respective language model score for each different character string of the plurality of different character strings;

determining, by the computing device, a respective combined score for each different character string of the plurality of character strings, the respective combined score based at least in part on the spatial model score and the respective language model score for the respective different character string of the plurality of character strings;

determining, by the computing device, a quantity of probable character strings in the plurality of character strings, wherein the probable character strings are associated with combined scores that indicate higher probabilities than the combined score of the out-of-vocabulary character string;

in response to determining that the quantity of probable character strings is greater than a quantity of character string suggestion regions in the plurality of character string suggestion regions, outputting, by the computing device and for display, the out-of-vocabulary character string in at least one of the plurality of character string suggestion regions.

6. The method of claim 1, further comprising:

determining, by the computing device, a penalty value; and

applying, by the computing device, the penalty value to at least one of the combined score of the character string, the a spatial model score, and the out-of-vocabulary language model score.

7. The method of claim 1, further comprising:

while receiving a plurality of indications of one or more gestures detected at a presence-sensitive screen, updating, by the computing device, the out-of-vocabulary language model score based on a language context, wherein the language context changes in response to at least one the plurality of indications of one or more gestures.

8. The method of claim 1, wherein the gesture further comprises a continuous gesture that traverses a plurality of locations of the presence-sensitive screen that correspond respectively to a plurality of keys of the graphical keyboard.

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

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

responsive to receiving an indication of a gesture detected at a presence-sensitive input device, determine a selection of one or more of the plurality of keys;

determine a character string based on the one or more of the plurality of keys in the selection, wherein the character string is not included in a vocabulary used by the computing device to identify character strings;

responsive to determining that the character string is not included in the vocabulary used by the computing device to identify character strings, associate the character string with an out-of-vocabulary language model score, the out-of-vocabulary language model score being a substitute score that is determined without application of a language model to the character string;

determine, based at least in part on a spatial model score associated with the gesture and the out-of-vocabulary language model score, a combined score that indicates a probability that the character string corresponds to the gesture; and

output for display the character string.

10. The computer-readable storage medium of claim 9, encoded with instructions that, when executed, cause at least one processor to:

determine a plurality of character strings included in the vocabulary, wherein each character string of the plurality of character strings is associated with a respective probability of a plurality of probabilities;

determine a lowest probability included in the plurality of probabilities; and

use the lowest probability as the out-of-vocabulary language model score.

11. The computer-readable storage medium of claim 9, encoded with instructions that, when executed, cause at least one processor to:

in response to determining that the character string is not included in the vocabulary used by the computing device to identify character strings, select a predefined value as the out-of-vocabulary language model score.

12. The computer-readable storage medium of claim 9, wherein the character string is an out-of-vocabulary character string, the computer-readable storage medium encoded with instructions that, when executed, cause at least one processor to:

determine a plurality of different character strings corresponding to the one or more of the plurality of keys in the selection, wherein each of the plurality of different character strings is included in the vocabulary;

determine a respective language model score for each different character string of the plurality of different character strings;

determine a respective combined score for each different character string of the plurality of character strings, the respective combined score based at least in part on the spatial model score and the respective language model score for the respective different character string of the plurality of character strings; and

in response to determining that the respective combined score for at least one of the different character strings of the plurality of character strings satisfies a threshold, output for display, the at least one of the different strings with the out-of-vocabulary character string.

13. The computer-readable storage medium of claim 9, wherein the character string is an out-of-vocabulary character string, the computer-readable storage medium encoded with instructions that, when executed, cause at least one processor to:

determine a plurality of character string suggestion regions in a graphical user interface that is output for display by the computing device;

determine a plurality of different character strings corresponding to the one or more of the plurality of keys in the selection, wherein each different character string of the plurality of different character strings is included in the vocabulary;

determine a respective language model score for each different character string of the plurality of different character strings;

determine a respective combined score for each different character string of the plurality of character strings, the respective combined score based at least in part on the spatial model score and the respective language model score for the respective different character string of the plurality of character strings;

determine a quantity of probable character strings in the plurality of character strings, wherein the probable character strings are associated with combined scores that indicate higher probabilities than the combined score of the out-of-vocabulary character string;

in response to determining that the quantity of probable character strings is greater than a quantity of character string suggestion regions in the plurality of character string suggestion regions, output for display, the out-of-vocabulary character string in at least one of the plurality of character string suggestion regions.

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

determine a penalty value; and

apply the penalty value to at least one of the combined score of the character string, the a spatial model score, and the out-of-vocabulary language model score.

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

while receiving a plurality of indications of one or more gestures detected at a presence-sensitive screen, update the out-of-vocabulary language model score based on a language context, wherein the language context changes in response to at least one the plurality of indications of one or more gestures.

16. The computer-readable storage medium of claim 9, wherein the gesture further comprises a continuous gesture that traverses a plurality of locations of the presence-sensitive screen that correspond respectively to a plurality of keys of the graphical keyboard.

17. A computing device comprising at least one processor, wherein the at least one processor is configured to:

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

responsive to receiving an indication of a gesture detected at a presence-sensitive input device, determine a selection of one or more of the plurality of keys;

determine a character string based on the one or more of the plurality of keys in the selection, wherein the character string is not included in a vocabulary used by the computing device to identify character strings;

responsive to determining that the character string is not included in the vocabulary used by the computing device to identify character strings, associate the character string with an out-of-vocabulary language model score, the out-of-vocabulary language model score being a substitute score that is determined without application of a language model to the character string;

determine, based at least in part on a spatial model score associated with the gesture and the out-of-vocabulary language model score, a combined score that indicates a probability that the character string corresponds to the gesture; and

output for display the character string.

18. The computing device of claim 17, wherein the at least one processor is configured to:

determine a plurality of character strings included in the vocabulary, wherein each character string of the plurality of character strings is associated with a respective probability of a plurality of probabilities;

determine a lowest probability included in the plurality of probabilities; and

use the lowest probability as the out-of-vocabulary language model score.

19. The computing device of claim 17, wherein the at least one processor is configured to:

in response to determining that the character string is not included in the vocabulary used by the computing device to identify character strings, select a predefined value as the out-of-vocabulary language model score.

20. The computing device of claim 17, wherein the character string is an out-of-vocabulary character string, wherein the at least one processor is configured to:

determine a plurality of different character strings corresponding to the one or more of the plurality of keys in the selection, wherein each of the plurality of different character strings is included in the vocabulary;

determine a respective language model score for each different character string of the plurality of different character strings;

determine a respective combined score for each different character string of the plurality of character strings, the respective combined score based at least in part on the spatial model score and the respective language model score for the respective different character string of the plurality of character strings; and

in response to determining that the respective combined score for at least one of the different character strings of the plurality of character strings satisfies a threshold, output for display, the at least one of the different strings with the out-of-vocabulary character string.

21. The computing device of claim 17, wherein the character string is an out-of-vocabulary character string, wherein the at least one processor is configured to:

determine a plurality of character string suggestion regions in a graphical user interface that is output for display by the computing device;

determine a plurality of different character strings corresponding to the one or more of the plurality of keys in the selection, wherein each different character string of the plurality of different character strings is included in the vocabulary;

determine a respective language model score for each different character string of the plurality of different character strings;

determine a respective combined score for each different character string of the plurality of character strings, the respective combined score based at least in part on the spatial model score and the respective language model score for the respective different character string of the plurality of character strings;

determine a quantity of probable character strings in the plurality of character strings, wherein the probable character strings are associated with combined scores that indicate higher probabilities than the combined score of the out-of-vocabulary character string;

in response to determining that the quantity of probable character strings is greater than a quantity of character string suggestion regions in the plurality of character string suggestion regions, output for display, the out-of-vocabulary character string in at least one of the plurality of character string suggestion regions.

22. The computing device of claim 17, wherein the at least one processor is configured to:

determine a penalty value; and

applying the penalty value to at least one of the combined score of the character string, the a spatial model score, and the out-of-vocabulary language model score.

23. The computing device of claim 17, wherein the at least one processor is configured to:

while receiving a plurality of indications of one or more gestures detected at a presence-sensitive screen, update the out-of-vocabulary language model score based on a language context, wherein the language context changes in response to at least one the plurality of indications of one or more gestures.

24. The computing device of claim 17, wherein the gesture further comprises a continuous gesture that traverses a plurality of locations of the presence-sensitive screen that correspond respectively to a plurality of keys of the graphical keyboard.