Grammar-based automatic data completion and suggestion for user input

• US 7,698,127 B2
• Filed: 10/01/2004
• Issued: 04/13/2010
• Est. Priority Date: 03/07/2000
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Weinberg, Mark J., Trower, Tandy Woodson II
• Primary Examiner(s): Hudspeth; David R
• Assistant Examiner(s): Spooner; Lamont M
• Application Number:
  US10/956,270
• Publication Number:
  US 20050043939A1
• Time in Patent Office: 2,020 Days
• Field of Search: 704/9, 715/261, 715254-259, 707 2- 6
• US Class Current: 704/9
• CPC Class Codes: G06F 3/0237 using prediction or retrieval techniques
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs

Abstract

In a computer, a user interface allows users to input requests to various applications or software modules executing on the computer. During the input process, the invention presents to the user a grammar-based automatic completion of the user input so far, and/or a grammar-based suggestion list of one or more possible options for completing the user input.

Claims

1. A method comprising:

receiving a series of user input selections by a computer configured to auto complete and suggest data entries;

for a most recently received input selection;

checking, by the computer, whether the most recently received input selection is for addition of an input character or deletion of an input character;

if the most recently received input selection is for addition of an input character, then;

waiting by the computer, in response to the most recently received input selection, until a first amount of time since the most recently received input selection was received has passed, and

presenting by the computer, in response to the first amount of time having passed, an option to automatically enter an additional input selection; and

if the most recently received input selection is for deletion of an input character, then;

waiting by the computer, in response to the most recently received input selection, until a second amount of time since the most recently received input selection was received has passed, and

presenting by the computer, in response to the second amount of time having passed, the option to automatically enter an additional input selection, the second amount of time being longer than the first amount of time.

2. A method as recited in claim 1, wherein the series of user input selections comprises a partial data input, and wherein the additional input selection is determined by:

comparing, by the computer, the partial data input to a plurality of grammar rules that identify valid inputs;

identifying by the computer, based on the comparing, a set of grammar rules that match the partial data input;

assigning a score to each of the grammar rules by the computer, the score indicating how closely the grammar rule matches the partial data input; and

selecting by the computer, as the additional input selection, the grammar rule with a highest score.

3. A method as recited in claim 2, wherein assigning a score to each of the grammar rules further comprises accessing a user context of the partial data input by the computer and modifying the score of at least one of the grammar rules in accordance with the user context by the computer.

4. A method as recited in claim 2, wherein the plurality of grammar rules are included in a plurality of grammar modules, and wherein each of the plurality of grammar modules includes grammar rules corresponding to a different software module.

5. A method as recited in claim 2, wherein at least one of the plurality of grammar rules includes a variable.

6. A method as recited in claim 2, wherein at least one of the plurality of grammar rules includes a wildcard.

7. A method as recited in claim 2, wherein the plurality of grammar rules includes a set of grammar rules that were previously accepted by the user to complete a previous partial data input.

8. A method as recited in claim 7, further comprising modifying one of the set of grammar rules by the computer by replacing any variables or wildcards in the grammar rule with matching portions of the previous partial data input.

9. A method as recited in claim 1, further comprising receiving by the computer, after presenting the option, a user acceptance of only a portion of the option as part of the user'"'"'s desired input.

10. One or more computer-readable media having stored thereon instructions that, when executed by one or more processors, cause the one or more processors to perform acts comprising:

receiving a partial data input for an edit control; and

for a most recently received input selection of the partial data input;

determining whether the most recently received input selection is for addition of an input character or deletion of an input character;

waiting for an input time delay before analyzing the partial data input when the input selection is for the addition of an input character;

waiting for a deletion time delay before analyzing the partial data input when the input selection is for the deletion of an input character, wherein the deletion time delay is longer than the input time delay;

comparing the partial data input to a plurality of grammar rules that identify valid inputs;

identifying, based on the comparing, a set of grammar rules that match the partial data input;

assigning a score to each of the grammar rules by determining a user context of the partial data input based on one or more active applications and modifying the score of at least one of the grammar rules in accordance with the user context, the score indicating how closely the grammar rule matches the partial data input;

selecting, as an additional input selection, the grammar rule with a highest score; and

presenting an option to automatically enter the additional input selection after the input time delay or the deletion time delay has passed, wherein the option is based on the analysis of the partial data input.

11. One or more computer-readable media as recited in claim 10, wherein the plurality of grammar rules are included in a plurality of grammar modules, and wherein each of the plurality of grammar modules includes grammar rules corresponding to a different software module that can be executed by the one or more processors.

12. One or more computer-readable media as recited in claim 10, wherein at least one of the plurality of grammar rules includes a variable.

13. One or more computer-readable media as recited in claim 10, wherein at least one of the plurality of grammar rules includes awildcard.

14. One or more computer-readable media as recited in claim 10, wherein the plurality of grammar rules includes a set of grammar rules that were previously accepted by the user to complete a previous partial data input.

15. One or more computer-readable media as recited in claim 14, wherein the acts further comprise modifying one of the set of grammar rules by replacing any variables or wildcards in the grammar rule with matching portions of the previous partial data input.

16. One or more computer-readable media as recited in claim 10, wherein the acts further comprise receiving, after presentation of the option, a user acceptance of only a portion of the option as part of the user'"'"'s desired input.

17. A system comprising:

a processor; and

a memory, coupled to the processor, including one or more instructions that, when executed by the processor, cause the processor to;

receive a series of user input selections;

for a most recently received input selection;

if the most recently received input selection is for addition of an input character, then;

wait, in response to the most recently received input selection, until a first predetermined amount of time since the most recently received input selection was received has passed, and

present, in response to the first predetermined amount of time having passed, an option to automatically enter an additional input selection; and

if the most recently received input selection is for deletion of an input character, then;

wait, in response to the most recently received input selection, until a second predetermined amount of time since the most recently received input selection was received has passed;

compare the partial data input to a plurality of grammar rules that identify valid inputs;

identify, based on the comparing, a set of grammar rules that match the partial data input;

assign a score to each of the grammar rules by determining a user context of the partial data input based on user preferences, the score indicating how closely the grammar rule matches the partial data input; and

select, as an additional input selection, the grammar rule with a highest score;

and present, in response to the predetermined second amount of time having passed, the option to automatically enter the additional input selection, the second predetermined amount of time being longer than the first predetermined amount of time.

18. A system as recited in claim 17, wherein the plurality of grammar rules includes a set of grammar rules that were previously accepted by the user to complete a previous partial data input.

19. A system as recited in claim 18, wherein the one or more instructions when executed by the processor further cause the processor to receive, after presentation of the option, a user acceptance of only a portion of the option as part of the user'"'"'s desired input.

20. A system comprising:

a processor;

means for receiving a partial data input for an edit control; and

means for, for a most recently received input selection of the partial data input;

waiting for an input time delay before analyzing the partial data input when the input selection is for addition of an input character;

waiting for a deletion time delay before analyzing the partial data input when the input selection is for deletion of an input character, wherein the deletion time delay is longer than the input time delay; and

presenting an option to automatically enter an additional input selection in response to the input time delay passing or in response to the deletion time delay passing, wherein the option is based on the analysis of the partial data input.

21. A system as recited in claim 20, further comprising means for determining the additional input selection by:

comparing the partial data input to a plurality of grammar rules that identify valid inputs; and

identifying, based on the comparing, a set of grammar rules that match the partial data input;

assigning a score to each of the grammar rules, the score indicating how closely the grammar rule matches the partial data input;

selecting, as the additional input selection, the grammar rule with a highest score.