Proximity based keystroke resolution

• US 8,179,370 B1
• Filed: 02/09/2010
• Issued: 05/15/2012
• Est. Priority Date: 02/09/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Yamasani, Amith, Arscott, Simon
• Primary Examiner(s): OSORIO, RICARDO
• Application Number:
  US12/703,020
• Time in Patent Office: 826 Days
• Field of Search: 345/168, 345/169, 345/156, 345/157, 400/472, 340/407.1, 341/21
• US Class Current: 345/168
• CPC Class Codes: G06F 3/0237 using prediction or retrieval techniques

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for resolving keystrokes. One of the methods includes receiving a first keystroke and a second keystroke input by a user on a keyboard. The first keystroke corresponds to a first key on the keyboard and the second keystroke corresponds to a second key on the keyboard that is different from the first key. The first keystroke and the second keystroke are determined to have been input at substantially the same time and the first key is determined to be adjacent the second key on the keyboard. In response to the determinations, a suggestion is generated that only one of the two keystrokes was intended to be input.

Claims

1. A computer-implemented method for resolving keystrokes, the method comprising:

receiving a first keystroke and a second keystroke input by a user on a keyboard, wherein the first keystroke corresponds to a first key on the keyboard and the second keystroke corresponds to a second key on the keyboard that is different from the first key;

determining that the first keystroke and the second keystroke were input substantially simultaneously and that the first key is adjacent the second key on the keyboard; and

in response to the determination, generating a suggestion that only one of the first keystroke and the second keystroke was intended to be input; and

communicating the suggestion to the user, comprising;

determining one or more permutations of character strings that include either a first character corresponding to the first key or a second character corresponding to the second key and one or more characters input by the user immediately preceding the first keystroke and the second keystroke, including determining permutations in which at least one of the one or more characters input preceding the first keystroke and the second keystroke is replaced by a proximal character, wherein the proximal character corresponds to a third key on the keyboard adjacent a fourth key that corresponds to the replaced at least one of the one or more characters;

determining, for each respective of the one or more permutations, a probability that the respective permutation was intended to be input by the user; and

displaying, to the user and on a display device, one or more suggested character strings based on the determined probabilities.

2. The method of claim 1, further comprising:

displaying, on the display device, a character string, wherein the character string includes the first character and the second character preceded by the one or more characters input by the user;

receiving an input from the user selecting one of the suggested character strings; and

replacing the displayed character string with the selected suggested character string.

3. The method of claim 1, wherein the one or more suggested character strings includes a suggested character string that includes a permutation having a plurality of characters, wherein at least some of the plurality of characters are reordered from an order in which the plurality of characters were input by the user.

4. The method of claim 1, wherein communicating the suggestion to the user comprises:

receiving an input from the user indicating a termination of a character string;

for each of the one or more permutations, determining a probability that the permutation is the character string intended to be input by the user; and

if a permutation with the highest probability has a probability exceeding a predetermined threshold confidence, then selecting the permutation with the highest probability and automatically replacing the one or more characters input by the user with a character string corresponding to the permutation with the highest probability, otherwise, displaying to the user, on the display device, one or more suggested character strings based on the determined probabilities.

5. The method of claim 4, further comprising:

determining a plurality of permutations of character strings, wherein each of the plurality of permutations of character strings includes both the first character and the second character and one or more other characters input by the user in a single character string;

for each respective of the plurality of permutations, determining a probability that the permutation from the plurality is the character string intended to be input by the user; and

suggesting one or more most probable of the plurality of permutations of character strings to the user in addition to the one or more suggested character strings based on the determined probabilities.

6. The method of claim 1, further comprising:

receiving a third keystroke corresponding to a third key input by the user on the keyboard;

determining that the third keystroke was input at substantially the same time as the first and second keystrokes and that a key corresponding to the third keystroke is adjacent at least one of either the first key or the second key; and

in response to the determination, generating a suggestion that only one of the three keystrokes was intended to be input.

7. The method of claim 1, wherein determining, for each respective of the one or more permutations, a probability that the respective permutation is the character string intended to be input by the user comprises checking each respective permutation against entries in one or more dictionaries for a match.

8. The method of claim 7, wherein at least one of the one or more dictionaries comprises a dynamically updated dictionary that has new entries added or probabilities of existing entries updated dynamically over time.

9. A computer-readable medium having instructions encoded thereon, which, when executed by a processor, cause the processor to perform operations comprising:

receiving a first keystroke and a second keystroke input by a user on a keyboard, wherein the first keystroke corresponds to a first key on the keyboard and the second keystroke corresponds to a second key on the keyboard that is different from the first key;

determining that the first keystroke and the second keystroke were input substantially simultaneously and that the first key is adjacent the second key on the keyboard; and

in response to the determination, generating a suggestion that only one of the first keystroke and the second keystroke was intended to be input; and

communicating the suggestion to the user, comprising;

determining one or more permutations of character strings that include either a first character corresponding to the first key or a second character corresponding to the second key and one or more characters input by the user immediately preceding the first keystroke and the second keystroke, including determining permutations in which at least one of the one or more characters input preceding the first keystroke and the second keystroke is replaced by a proximal character, wherein the proximal character corresponds to a third key on the keyboard adjacent a fourth key that corresponds to the replaced at least one of the one or more characters;

determining, for each respective of the one or more permutations, a probability that the respective permutation was intended to be input by the user; and

displaying, to the user and on a display device, one or more suggested character strings based on the determined probabilities.

10. The computer-readable medium of claim 9, the operations further comprising:

displaying, on the display device, a character string, wherein the character string includes the first character and the second character preceded by the one or more characters input by the user;

receiving an input from the user selecting one of the suggested character strings; and

replacing the displayed character string that includes the first character and the second character preceded by the one or more characters input by the user with the selected suggested character string.

11. The computer-readable medium of claim 9, wherein communicating the suggestion to the user comprises:

receiving an input from the user indicating a termination of a character string;

for each of the one or more permutations, determining a probability that the permutation is the character string intended to be input by the user; and

if a permutation with the highest probability has a probability exceeding a predetermined threshold confidence, then selecting the permutation with the highest probability and automatically replacing the one or more characters input by the user with a character string corresponding to the permutation with the highest probability, otherwise, displaying to the user, on the display device, one or more suggested character strings based on the determined probabilities.

12. The computer readable medium of claim 9, wherein determining, for each respective of the one or more permutations, a probability that the respective permutation is the character string intended to be input by the user comprises checking each respective permutation against entries in one or more dictionaries for a match.

13. The computer readable medium of claim 12, wherein at least one of the one or more dictionaries comprises a dynamically updated dictionary that has new entries added or probabilities of existing entries updated dynamically over time.

14. A system comprising:

a processor;

receiving a first keystroke and a second keystroke input by a user on a keyboard, wherein the first keystroke corresponds to a first key on the keyboard and the second keystroke corresponds to a second key on the keyboard that is different from the first key;

determining that the first keystroke and the second keystroke were input substantially simultaneously and that the first key is adjacent the second key on the keyboard; and

in response to the determination, generating a suggestion that only one of the first keystroke and the second keystroke was intended to be input; and

communicating the suggestion to the user, comprising;

determining one or more permutations of character strings that include either a first character corresponding to the first key or a second character corresponding to the second key and one or more characters input by the user immediately preceding the first keystroke and the second keystroke, including determining permutations in which at least one of the one or more characters input preceding the first keystroke and the second keystroke is replaced by a proximal character, wherein the proximal character corresponds to a third key on the keyboard adjacent a fourth key that corresponds to the replaced at least one of the one or more characters;

determining, for each respective of the one or more permutations, a probability that the respective permutation was intended to be input by the user; and

displaying, to the user and on a display device, one or more suggested character strings based on the determined probabilities.

15. The system of claim 14, comprising:

displaying, on the display device, a character string, wherein the character string includes the first character and the second character preceded by the one or more characters input by the user;

receiving an input from the user selecting one of the suggested character strings; and

replacing the displayed character string that includes the first character and the second character preceded by the one or more characters input by the user with the selected suggested character string.

16. The system of claim 14, wherein communicating the suggestion to the user comprises:

receiving an input from the user indicating a termination of a character string;

for each of the one or more permutations, determining a probability that the permutation is the character string intended to be input by the user; and

if a permutation with the highest probability has a probability exceeding a predetermined threshold confidence, then selecting the permutation with the highest probability and automatically replacing the one or more characters input by the user with a character string corresponding to the permutation with the highest probability, otherwise, displaying to the user, on the display device, one or more suggested character strings based on the determined probabilities.

17. The system of claim 14, wherein determining, for each respective of the one or more permutations, a probability that the respective permutation is the character string intended to be input by the user comprises checking each respective permutation against entries in one or more dictionaries for a match.

18. The system of claim 17, wherein at least one of the one or more dictionaries comprises a dynamically updated dictionary that has new entries added or probabilities of existing entries updated dynamically over time.