PREDICTIVE WORD COMPLETION

• US 20120324391A1
• Filed: 06/16/2011
• Published: 12/20/2012
• Est. Priority Date: 06/16/2011
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Tocci, Mark
• Application Number:
  US13/162,319
• Publication Number:
  US 20120324391A1
• Time in Patent Office: Days
• US Class Current: 715/773
• CPC Class Codes: G06F 3/0237 using prediction or retrieval techniques
• CPC Class Codes: G06F 3/048 Interaction techniques based on graphical user interfaces [GUI]

Abstract

This document describes predictive word completion. By predicting complete words after each user input on an input device, e.g., a virtual keyboard, a user may readily receive computer aid when inputting characters to increase accuracy and speed of the user'"'"'s typing.

Claims

1. A computer-implemented method, comprising:

receiving a set of characters responsive to a user input to a virtual keyboard, the set of characters corresponding to the user input and based on characters of the virtual keyboard that are proximate a received location on the virtual keyboard of the user input, the set of characters continuing a word fragment to provide a set of word fragments corresponding to the set of characters;

determining which word fragment is most-likely to be correct based on;

the received location; and

each word fragment of the set of word fragments being a valid word, a portion of a valid word, or correctable to become a valid word.

2. A computer-implemented method as recited in claim 1, wherein the received location indicates a probability that each character in the set of characters is correct.

3. A computer-implemented method as recited in claim 1, wherein the valid word or the portion of the valid word is based on a language model corresponding to a dictionary of valid words that pertain to a language.

4. A computer-implemented method as recited in claim 1, wherein the word fragment comprises a beginning portion of a valid word.

5. A computer-implemented method as recited in claim 1, wherein each word fragment in the set of word fragments comprises a correctly spelled word or an incorrectly spelled but often-used word.

6. A computer-implemented method as recited in claim 1, wherein the word fragment is correctable to become a valid word based on a correction model indicating that the word fragment is likely misspelled but intended to be the valid word.

7. A computer-implemented method as recited in claim 1, further comprising determining valid words for each word fragment in the set of word fragments.

8. A computer-implemented method as recited in claim 1, wherein determining which word fragment is most-likely correct is further based on a word-probability language model, the word-probability language model indicating a likelihood of correctness for each valid word.

9. Computer-readable storage media comprising instructions that are executable and, responsive to executing the instructions, cause a computing device to:

receive a user input corresponding to multiple characters;

analyze, based on a keypress model, the user input to determine a most-likely correct character of the multiple characters;

identify, based on a language model, one or more valid words having the most-likely correct character;

detect, based on a correction model, a potential spelling correction of a word fragment having the most-likely correct character and one or more additional previously received characters; and

predict one or more complete words based on a combination of the most-likely correct character, the one or more valid words, and the potential spelling correction.

10. Computer-readable storage media as recited in claim 9, wherein the instructions are executable to cause the computing device to predict the one or more complete words by expanding one or more branches of a dictionary trie to identify words likely to be used without expanding branches of the dictionary trie associated with words not likely to be used.

11. Computer-readable storage media as recited in claim 9, wherein the instructions are executable to cause the computing device to predict the one or more complete words by generating a predefined number of predicted complete words by expanding a most-probable path in a word-probability dictionary trie.

12. Computer-readable storage media as recited in claim 9, wherein the instructions are executable to cause the computing device to determine a maximum probability associated with the most-likely character to identify the one or more complete words.

13. Computer-readable storage media as recited in claim 9, wherein the instructions are executable to cause the computing device to determine a maximum probability of the most-likely character that is associated with a most-likely word.

14. Computer-readable storage media as recited in claim 9, wherein the instructions are executable to further cause the computing device to identify one or more subsequent child characters of the most-likely character that are associated with a most-likely word, the most-likely word correlating to a maximum probability of the most-likely character.

15. A computer-implemented method, comprising:

receiving a set of characters responsive to a user input to a virtual keyboard, the set of characters corresponding to the user input and based on characters of the virtual keyboard that are proximate a received location on the virtual keyboard of the user input, the set of characters continuing a word fragment;

determining, for each character of the set of characters, a selection probability that each character is correct based on the location;

determining spelling corrections of the word fragment to provide corrected word fragments;

determining, for each corrected word fragment of the corrected word fragments, a corrected probability that each corrected word fragment is correct based on a correction-probability model;

determining valid words for the word fragment and the corrected word fragments;

determining, for each valid word of the valid words for the word fragment and the corrected word fragments, a word probability that each valid word is correct based on a word-probability language model; and

predicting, based on the selection probability, the corrected probability, and the word probability, one or more complete words.

16. A computer-implemented method as recited in claim 15, wherein the selection probability is determined based on a percentage of the received location that corresponds to each respective character in the set of characters.

17. A computer-implemented method as recited in claim 15, wherein the received location is located between a plurality of virtual keys on the virtual keyboard.

18. A computer-implemented method as recited in claim 15, further comprising storing a single probability for each word in the word-probability language model.

19. A computer-implemented method as recited in claim 15, further comprising updating in real time probabilities associated with one or more words in the word-probability language model based on user-specific probabilities associated with complete words used by a particular user.

20. A computer-implemented method as recited in claim 19, wherein the updating further comprises adding one to a count associated with a total probability that is associated with complete words.