Text completion system for a miniature computer

• US 5,896,321 A
• Filed: 11/14/1997
• Issued: 04/20/1999
• Est. Priority Date: 11/14/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Miller, John W., Goldberg, Jossef
• Primary Examiner(s): Fears, Terrell W.
• Application Number:
  US08/970,310
• Time in Patent Office: 522 Days
• Field of Search: 365/189.01, 365/230.01, 365/230.03
• US Class Current: 365/189.15
• CPC Class Codes: G06F 3/023 Arrangements for converting discrete items of information into a coded form, e.g. arrangements for interpreting keyboard generated codes as alphanumeric codes, operand codes or instruction codes
• CPC Class Codes: G06F 3/0236 using selection techniques to select from displayed items
• CPC Class Codes: G06F 3/0237 using prediction or retrieval techniques
• CPC Class Codes: G06F 3/0488 using a touch-screen or digitiser, e.g. input of commands through traced gestures
• 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/274 Converting codes to words; Guess-ahead of partial word inputs

Abstract

A text completion system that automatically displays a list of completion suggestions for a partial data entry in response to a pause in receipt of the data entry. To avoid annoying the user by displaying an excessive number of wrong suggestions, the text completion system applies search criteria to the partial data entry. If the partial data entry satisfies the search criteria, the text completion system obtains a prioritized list of word predictions for the partial data entry from a word prediction system. To further avoid annoying the user by displaying very short completion suggestions, the text completion system applies display criteria to the word predictions to obtain a prioritized list of completion suggestions that satisfy the display criteria. This prioritized list of completion suggestions is then displayed in a pop-up list box, typically immediately under and to the right of the partial data entry. The completion suggestions are positioned in the list based on a computed indication of likelihood of being correct. The user may accept a completion suggestion from the list by touching a stylus to the display screen over the position of the desired completion suggestion, or by using traditional selection and acceptance keystrokes, such as the "arrow" keys to select a completion suggestion and the "enter" key to accept the selected completion suggestion. Thus, the text completion system allows the user to complete the partial data entry without having to type the remaining letters of the complete data entry.

Claims

1. A computer-readable medium having computer-executable instructions for performing the steps of:

monitoring the entry of a stream of characters into a data file associated with a program module running on a computer system, the stream of characters defining a plurality of complete data entries followed by a partial data entry;

displaying the stream of characters on a display screen;

detecting a pause of a predetermined duration in the entry of the stream of characters; and

in response to the pause, determining whether the partial data entry satisfies search criteria and, if the partial data entry satisfies the search criteria,

obtaining a prioritized list of word predictions for the partial data entry from a word prediction system,

applying display criteria to the prioritized list of word predictions to obtain a prioritized list of completion suggestions, and

displaying the prioritized list of completion suggestions on the display screen in association with the partial data entry.

2. The computer-readable medium of claim 1, further comprising the steps of:

receiving an acceptance command associated with a particular one of the completion suggestions; and

in response to the acceptance command,

completing the partial data entry with characters of the particular completion suggestion, and

discontinuing the display of the prioritized list of completion suggestions.

3. The computer-readable medium of claim 2, before the step of receiving the acceptance command, receiving a selection command associated with the particular completion suggestion.

4. The computer-readable medium of claim 1, wherein the step of determining whether the partial data entry satisfies the search criteria comprises the steps of:

receiving a command establishing a predetermined number of characters; and

determining whether the partial data entry comprises at least the predetermined number of characters.

5. The computer-readable medium of claim 1, wherein the step of determining whether the partial data entry satisfies the display criteria comprises the steps of:

receiving a command establishing a predetermined number of additional characters; and

determining whether a particular one of the completion suggestions comprises at least the predetermined number of additional characters more than the partial data entry.

6. The computer-readable medium of claim 1, wherein the step of obtaining the prioritized list of word predictions from the word prediction system comprises the steps of:

comparing the partial data entry to the entries in a dictionary to obtain a list of feasible words;

submitting the list of feasible words to a plurality of word prediction experts;

obtaining word predictions from each word prediction expert; and

positioning each word prediction in the prioritized list of word predictions based on a computed indication of likelihood of being a correct completion suggestion.

7. The computer-readable medium of claim 6, further comprising the steps of:

associating each entry in the dictionary with a word identification value; and

for entries in the list of feasible words,

obtaining a word prediction score from each word prediction expert,

computing a word value based on the word prediction scores and the word identification value, and

positioning the entry in the prioritized list of word predictions based on the word value.

8. The computer-readable medium of claim 7, wherein:

each word prediction expert is associated with a mutually exclusive set of bits within each word value assigned to the word prediction experts to reflect a priority order among the word prediction experts; and

each word value is computed by summing the word prediction scores associated with a particular one of the word predictions with a word identification value for the particular word prediction.

9. The computer-readable medium of claim 6, wherein the step of submitting the list of feasible words to the word prediction experts comprises the steps of submitting the list of feasible words to a first one of the word prediction experts, and within the first word prediction expert:

comparing the list of feasible words to a list of recently received words to determine whether a particular feasible word appears in the list of recently received words;

if the particular feasible word appears in the list of recently received words, determining whether the complete data entry immediately preceding the partial data entry in the stream of characters corresponds to the data entry immediately preceding the particular feasible word in the list of recently received words; and

if the complete data entry immediately preceding the partial data entry in the stream of characters corresponds to the data entry immediately preceding the particular feasible word in the list of recently received words, determining whether the two complete data entries immediately preceding the partial data entry in the stream of characters corresponds to the two data entries immediately preceding the particular feasible word in the list of recently received words.

10. The computer-readable medium of claim 9, wherein the step of submitting the list of feasible words to the word prediction experts comprises the steps of submitting the list of feasible words to a second one of the word prediction experts, and within the second word prediction expert:

comparing the list of feasible words to a list of entries in the dictionary including a word count for each dictionary entry, the word count for a particular dictionary entry indicating the historical frequency of the occurrence of the particular dictionary entry in the word prediction system.

11. The computer-readable medium of claim 10, wherein the step of submitting the list of feasible words to the word prediction experts comprises the steps of submitting the list of feasible words to a third one of the word prediction experts, and within the third word prediction expert:

comparing the list of feasible words to a list of entries in the dictionary including a probability score for each dictionary entry, the probability score for a particular dictionary entry indicating the frequency of the occurrence of the particular dictionary entry in a training corpus.

12. The computer-readable medium of claim 11, wherein the step of submitting the list of feasible words to the word prediction experts comprises the steps of submitting the list of feasible words to a fourth word prediction expert, and within the fourth word prediction expert:

identifying a context parameter associated with the partial data entry; and

determining whether an entry in the list of feasible words has previously occurred in the word prediction system in association with the context parameter.

13. The computer-readable medium of claim 12, wherein the context parameter is indicative of a user interface associated with a program module.

14. The computer-readable medium of claim 12, wherein the context parameter is indicative of a structured field within a user interface associated with a program module.

15. The computer-readable medium of claim 12, wherein the step of determining whether the entry in the list of feasible words has previously occurred in the word prediction system in association with the context parameter further comprises the steps of:

computing a hash value based on the context parameter and a word identification value associated with the entry in the list of feasible words;

identifying a memory address based on the hash value;

retrieving a stored value from the memory address; and

determining whether the stored value corresponds to a signature value based on the hash value.

16. The computer-readable medium of claim 1, further comprising the steps of:

receiving a delimiter character converting the partial data entry into a complete data entry; and

in response to the delimiter character,

updating the word prediction system for the complete data entry, and

discontinuing the display of the prioritized list of completion suggestions.

17. The computer-readable medium of claim 16, wherein the step of updating the word prediction system further comprises the steps of:

determining whether the complete data entry corresponds to a first entry in a dictionary; and

if the complete data entry corresponds to the first entry in the dictionary,

incrementing a first word count value associated with the first entry in the dictionary,

randomly selecting a second entry in the dictionary, and

decrementing a second word count value associated with the second entry in the dictionary.

18. The computer-readable medium of claim 16, wherein the step of updating the word prediction system further comprises the steps of:

determining whether the complete data entry corresponds to an entry in a dictionary; and

if the complete data entry does not correspond to an entry in the dictionary,

adding the complete data entry to the dictionary, and

deleting another data entry from the dictionary.

19. The computer-readable medium of claim 16, wherein the step of updating the word prediction system further comprises the step of adding the complete data entry to a list of recently received words.

20. The computer-readable medium of claim 16, wherein the step of updating the word prediction system further comprises the steps of:

identifying a context parameter associated with the partial data entry;

computing a hash value based on the context parameter and a word identification value associated with the entry in the list of feasible words;

identifying a memory address based on the hash value; and

storing a signature value based on the hash value at the memory address.

21. In a computer system, a word prediction system configured to implement a method for obtaining a prioritized list of word predictions for a partial data entry, comprising the steps of:

receiving a partial data entry;

comparing the partial data entry to the entries in a dictionary to obtain a list of feasible words;

submitting the list of feasible words to a plurality of word prediction experts;

obtaining a word prediction from each word prediction expert; and

positioning each word prediction in the prioritized list of word predictions based on a computed indication of likelihood of being a correct completion suggestion.

22. The word prediction system of claim 21, wherein:

each word prediction expert is associated with a mutually exclusive set of bits within each word value assigned to the word prediction experts to reflect a priority order among the word prediction experts; and

each word value is computed by summing the word prediction scores associated with a particular one of the word predictions with a word identification value for the particular word prediction.

23. The word prediction system of claim 22, wherein the step of submitting the list of feasible words to the word prediction experts comprises the steps of submitting the list of feasible words to a first one of the word prediction experts, and within the first word prediction expert:

comparing the list of feasible words to a list of recently received words to determine whether a particular one of the feasible words appears in the list of recently received words;

if the particular feasible word appears in the list of recently received words, determining whether the complete data entry immediately preceding the partial data entry in the stream of characters corresponds to the data entry immediately preceding the particular feasible word in the list of recently received words; and

if the complete data entry immediately preceding the partial data entry in the stream of characters corresponds to the data entry immediately preceding the particular feasible word in the list of recently received words, determining whether the two complete data entries immediately preceding the partial data entry in the stream of characters corresponds to the two data entries immediately preceding the particular feasible word in the list of recently received words.

24. The word prediction system of claim 21, wherein the step of submitting the list of feasible words to the word prediction experts comprises the steps of submitting the list of feasible words to a second one of the word prediction experts, and within the second word prediction expert:

comparing the list of feasible words to a list of entries in the dictionary including a word count for each dictionary entry, the word count for a particular dictionary entry indicating the historical frequency of the occurrence of the particular dictionary entry in the word prediction system.

25. The word prediction system of claim 21, wherein the step of submitting the list of feasible words to the word prediction experts comprises the steps of submitting the list of feasible words to a third one of the word prediction experts, and within the third word prediction expert:

comparing the list of feasible words to a list of entries in the dictionary including a probability score for each dictionary entry, the probability score for a particular dictionary entry indicating the frequency of the occurrence of the particular dictionary entry in a training corpus.

26. The word prediction system of claim 21, wherein the step of submitting the list of feasible words to the word prediction experts comprises the steps of submitting the list of feasible words to a fourth one of the word prediction experts, and within the fourth word prediction expert:

identifying a context parameter associated with the partial data entry; and

determining whether an entry in the list of feasible words has previously occurred in the word prediction system in association with the context parameter.

27. The word prediction system of claim 26, wherein the context parameter is indicative of a particular user interface associated with a particular program module.

28. The word prediction system of claim 27, wherein the context parameter is indicative of a particular structured field within a particular user interface associated with a particular program module.

29. The word prediction system of claim 27, wherein the step of determining whether the entry in the list of feasible words has previously occurred in the word prediction system in association with the context parameter further comprises the steps of:

computing a hash value based on the context parameter and a word identification value associated with the entry in the list of feasible words;

identifying a memory address based on the hash value;

retrieving a stored value from the memory address; and

determining whether the stored value corresponds to a signature value based on the hash value.

30. The word prediction system of claim 21, further comprising the steps of:

receiving a complete data entry; and

in response to the complete data entry, updating the word prediction system for the complete data entry.

31. The word prediction system of claim 30, wherein the step of updating the word prediction system further comprises the steps of:

determining whether the complete data entry corresponds to a first entry in the dictionary; and

if the complete data entry corresponds to the first entry in the dictionary,

incrementing a first word count value associated with the first entry in the dictionary,

randomly selecting a second entry in the dictionary, and

decrementing a second word count value associated with the second entry in the dictionary.

32. The word prediction system of claim 31, wherein the step of updating the word prediction system further comprises the steps of:

determining whether the complete data entry corresponds to an entry in the dictionary; and

if the complete data entry does not correspond to an entry in the dictionary,

adding the complete data entry to the dictionary, and

deleting another data entry from the dictionary.

33. The word prediction system of claim 31, wherein the step of updating the word prediction system further comprises the step of adding the complete data entry to a list of recently received words.

34. The word prediction system of claim 31, wherein the step of updating the word prediction system further comprises the steps of:

identifying a context parameter associated with the partial data entry;

computing a hash value based on the context parameter and a word identification value associated with the entry in the list of feasible words;

identifying a memory address based on the hash value; and

storing a signature value based on the hash value at the memory address.

35. In a computer system, a word prediction system for producing a prioritized list of word predictions for a partial data entry, comprising:

a dictionary comprising a plurality of static dictionary entries and a plurality of dynamic dictionary values, each static dictionary entry having a word associated with a unique word identification value;

a word count value associated with each dictionary entry indicating the historical frequency of the occurrence of the particular dictionary entry in the word prediction system;

a probability score associated with each static dictionary entry indicating the frequency of the occurrence of the particular dictionary entry in a training corpus;

an array of word identification values corresponding to a list of recently received words in the order in which the words were received by the word prediction system; and

an array of signature values based on hash values, each hash value stored at a memory address based on the corresponding hash value, each hash value computed based on a word identification value and a context parameter associated with the partial data entry.