Grammar-based automatic data completion and suggestion for user input

• US 20050043939A1
• Filed: 10/01/2004
• Published: 02/24/2005
• Est. Priority Date: 03/07/2000
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Weinberg, Mark J., Trower, Tandy Woodson II
• Granted Patent: US 7,698,127 B2
• Time in Patent Office: Days
• US Class Current: 704/8
• 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;

for a most recently received input selection;

checking 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, 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, 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, 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, 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 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, the score indicating how closely the grammar rule matches the partial data input; and

selecting, 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 and modifying the score of at least one of the grammar rules in accordance with the user context.

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 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, 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:

receive a partial data input for an edit control; and

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

wait, in response to the most recently received input selection, until an amount of time since the most recently received input selection was received has passed, the amount of time being longer if the most recently received input selection is for deletion of an input character than if the most recently recieved input selection is for addition of an input character; and

present, in response to the amount of time having passed, an option to automatically enter an additional input selection.

11. One or more computer-readable media as recited in claim 10, wherein the instructions further cause the one or more processors to determine the additional input selection by:

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, the score indicating how closely the grammar rule matches the partial data input; and

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

12. One or more computer-readable media as recited in claim 11, wherein assigning a score to each of the grammar rules further comprises accessing a user context of the partial data input and modifying the score of at least one of the grammar rules in accordance with the user context.

13. One or more computer-readable media as recited in claim 11, 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.

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

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

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

17. One or more computer-readable media as recited in claim 16, further comprising 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.

18. One or more computer-readable media as recited in claim 10, wherein the instructions further cause the one or more processors 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.

19. 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 amount of time since the most recently received input selection was received has passed, and

present, 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;

wait, 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

present, 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.

20. A system as recited in claim 19, wherein the series of user input selections comprises a partial data input, and wherein the instructions further cause the one or more processors to determine the additional input selection by:

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, the score indicating how closely the grammar rule matches the partial data input; and

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

21. A system as recited in claim 20, 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.

22. A system as recited in claim 21, wherein the instructions further cause the one or more processors 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.

23. A system comprising:

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, in response to the most recently received input selection, until an amount of time since the most recently received input selection was received has passed, the amount of time being longer if the most recently received input selection is for deletion of an input character than if the most recently received input selection is for addition of an input character; and

presenting, in response to the amount of time having passed, an option to automatically enter an additional input selection.

24. A system as recited in claim 23, 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.