Keystroke resolution

• US 8,830,182 B1
• Filed: 02/09/2010
• Issued: 09/09/2014
• Est. Priority Date: 02/09/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Alakuijala, Jyrki A.
• Primary Examiner(s): Boddie, William
• Assistant Examiner(s): Parker, Jeffrey A
• Application Number:
  US12/702,983
• Time in Patent Office: 1,673 Days
• Field of Search: 345173-178, 345/156
• US Class Current: 345/173
• CPC Class Codes: G06F 3/0237 using prediction or retrieval techniques
• 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

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for resolving keystrokes input into an electronic device. One of the methods includes receiving multiple keystrokes in the electronic device. Multiple characters that correspond to the multiple keystrokes are stored in a storage location for a predetermined time interval. In response to the predetermined time interval elapsing, the characters that correspond to the multiple keystrokes are reordered with respect to each other based on a statistical model.

Claims

1. A computer-implemented method, comprising:

receiving, by a processor, an indication of a first plurality of keystrokes;

storing, by the processor, and in a buffer already containing at least one character received during a first predetermined time interval, a plurality of characters corresponding to the first plurality of keystrokes; and

responsive to completion of a second predetermined time interval, reordering, by the processor and based on the at least one character from the previous predetermined time interval and a statistical model, characters from the plurality of characters corresponding to the first plurality of keystrokes, but not the at least one character, wherein the second predetermined time interval occurs subsequent to the first predetermined time interval.

2. The method of claim 1, further comprising:

after reordering the characters from the plurality of characters corresponding to the first plurality of keystrokes, but not the at least one character, clearing all characters from the buffer;

storing, by the processor, and in the buffer, a second plurality of characters corresponding to a second plurality of keystrokes;

responsive to completion of a third predetermined time interval, reordering the second plurality of characters based on the statistical model.

3. The method of claim 1, wherein the reordering of the characters from the plurality of characters corresponding to the first plurality of keystrokes but not the at least one character, based on the at least one character and the statistical model comprises:

determining a plurality of permutations of the characters corresponding to the first plurality of keystrokes and the at least one character;

comparing each permutation from the plurality permutations to one or more dictionaries;

calculating, based on the comparing, a score for each permutation; and

selecting a permutation associated with a highest calculated score from the plurality of permutations.

4. The method of claim 3, wherein:

the comparing of each permutation from the plurality permutations to one or more dictionaries comprises comparing each permutation to a first dictionary and to a second dictionary; and

the calculating, based on the comparing, of the score for each permutation comprises applying a first weighting to a match of the respective permutation to an entry in the first dictionary and applying a second weighting to a match of the respective permutation to an entry in the second dictionary, the first weighting exceeding the second weighting.

5. The method of claim 3, wherein the one or more dictionaries comprises a first dictionary that includes commonly occurring words and a second dictionary that includes an expanded set of words that is larger in number than the commonly occurring words.

6. The method of claim 3, wherein the one or more dictionaries includes an n-gram dictionary comprising a set of n-grams, and wherein each n-gram from the set of n-grams comprises a set of n-characters.

7. The method of claim 1, wherein the second predetermined time interval is a time interval in the range of approximately 20 to 50 milliseconds.

8. The method of claim 1, wherein the second predetermined time interval is dynamically extended in duration until a pause in receiving keystrokes is detected.

9. The method of claim 8, wherein a pause in receiving keystrokes is detected if a keystroke is not received for at least approximately 50 ms.

10. The method of claim 1, wherein the second predetermined time interval is dynamically shortened in duration if a keystroke indicating a word termination is received.

11. A computer-implemented method, comprising:

receiving a plurality of keystrokes within a first predetermined time interval;

storing a plurality of characters that correspond to the plurality of keystrokes in a buffer for a second predetermined time interval;

receiving data indicating one or more previously received characters comprising a partial-character string positioned adjacent to the plurality of characters, which together form a continuous character string;

in response to the second predetermined time interval elapsing, reordering the characters that correspond to the plurality of keystrokes with respect to each other based on a statistical model, wherein the reordering comprises;

determining a plurality of permutations of the characters that correspond to the plurality of keystrokes;

combining each permutation with the partial-character string to form a plurality of continuous character strings;

comparing each of the continuous character strings to one or more dictionaries;

calculating a score for each continuous character string based on the comparison; and

selecting the permutation that corresponds to the continuous character string associated with the highest score.

12. A system comprising:

a keyboard operable to receive from a user keystrokes that represent characters;

one or more data processing apparatuses comprising;

a buffer operable to receive and buffer a plurality of characters represented by keystrokes received from the keyboard in a predetermined time interval;

a reordering subsystem operable to, in response to the predetermined time interval elapsing, reorder the plurality of characters from the buffer based on a statistical model, the reordering including comparing permutations of the characters to one or more dictionaries; and

a memory comprising the one or more dictionaries;

the buffer further operable to;

after the plurality of characters in the buffer are reordered, clear characters that have been in the buffer longer than the predetermined interval and retain one or more characters from the plurality of characters in the buffer; and

receive an additional keystroke and add a character that is represented by the additional keystroke to the one or more characters retained in the buffer; and

the reordering subsystem further operable to, in response to the additional character being received in the buffer, reorder the characters from the buffer based on the statistical model.

13. The system of claim 12, wherein:

the one or more dictionaries include a first dictionary comprising a set of commonly occurring words and a second dictionary comprising an expanded set of words.

14. The system of claim 12, wherein:

the one or more dictionaries include an n-gram dictionary comprising a set of n-grams, and where an n-gram comprises a grouping of n characters.

15. A computer-readable storage device encoded with a computer program product, the computer program product including instructions that, when executed, perform operations comprising:

responsive to receiving a plurality of keystrokes storing data representing a plurality of characters that correspond to the plurality of keystrokes in a buffer for a predetermined time interval;

in response to the predetermined time interval elapsing, updating, based on a statistical model, the data in the buffer representing the plurality of characters to reflect reordering the plurality of characters with respect to each other;

after reordering the plurality of characters, clearing data from the buffer representing characters that have been represented in the buffer longer than the predetermined interval, wherein one or more characters from the plurality of characters remain represented in the buffer;

receiving an additional keystroke and adding data to the buffer representing a character that corresponds to the additional keystroke; and

in response to receiving the additional keystroke, updating, based on the statistical model, the buffer to reflect reordering of the characters represented in the buffer, including the one or more characters from the plurality of characters that remain represented in the buffer and the character that corresponds to the additional keystroke.

16. The computer-readable storage device of claim 15, wherein reordering the plurality of characters based on the statistical model comprises:

determining a plurality of permutations of characters from the plurality of characters;

comparing permutations from the plurality of permutations to one or more dictionaries;

calculating a score for each of the permutations based on the comparison; and

selecting a permutation associated with the highest score.