Grammar-based automatic data completion and suggestion for user input

• US 6,922,810 B1
• Filed: 03/07/2000
• Issued: 07/26/2005
• 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): Edouard, Patrick N.
• Assistant Examiner(s): Spooner, Lamont
• Application Number:
  US09/519,942
• Time in Patent Office: 1,967 Days
• Field of Search: 715/534, 715/531, 715/533, 704/1, 704 2- 9, 704/7, 704/257, 707/508, 707/530, 345/327
• US Class Current: 715/256
• 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. One or more computer-readable media having stored thereon a computer program that, when executed by one or more processors, causes the one or more processors to perform acts including:

receiving a partial data input for an edit control;

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;

displaying, as an automatic completion option, a grammar rule with a highest score; and

displaying, as a list of suggested completion options, one or more grammar rules of the set of grammar rules with scores that exceed a threshold value;

wherein the assigning a score to each of the grammar rules comprises, for each of the grammar rules, performing the following calculation to generate the score;

((match points)÷

(rule words))×

((match points)+(input words)),

wherein the match points variable is the number of words in the partial data input that match either words or variables in the grammar rule, wherein the rule words variable is the combined number of both words and variables in the grammar rule, and wherein the input word variable is the number of words in the partial data input.

2. One or more computer-readable media as recited in claim 1, wherein the 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.

3. One or more computer-readable media as recited in claim 1, wherein the plurality of grammar rules conform to a Backus-Naur Form (BNF) formal.

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

5. One or more computer-readable media as recited in claim 4, wherein the comparing comprises comparing the partial data input to only the grammar rules in grammar modules corresponding to software modules that are currently executing.

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

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

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

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

10. A method comprising:

receiving a partial data input for an edit control;

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;

displaying, as an automatic completion option, a grammar rule with a highest score; and

displaying, as a list of suggested completion options, one or more grammar rules of the set of grammar rules with scores that exceed a threshold value;

wherein the assigning a score to each of the grammar rules comprises, for each of the grammar rules, performing the following calculation to generate the score;

((match points)÷

(rule words))×

((match points)÷

(input words)),

wherein the match points variable is the number of words in the partial data input that match either words or variables in the grammar rule, wherein the rule words variable is the combined number of both words and variables in the grammar rule, and wherein the input words variable is the number of words in the partial data input.

11. A method as recited in claim 10, wherein the assigning a score to each of the grammar rule 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.

12. A method as recited in claim 10, wherein the plurality of grammar rules conform to a Backus-Naur Form (BNF) format.

13. A method 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.

14. A method as recited in claim 13, wherein the comparing comprises comparing the partial data input to only the grammar rules in grammar modules corresponding to software modules that are currently executing.

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

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

17. A method 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.

18. A method as recited in claim 17, 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.

19. A computer comprising:

a processor;

a memory coupled to the processor; and

wherein the memory is to store a plurality of instructions to;

receive a partial data input for an edit control;

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

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

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

display, as an automatic completion option, a grammar rule with a highest score; and

display, as a list of suggested completion options, one or more grammar rules of the set of grammar rules with scores that exceed a threshold value;

wherein to assign a score to each of the grammar rules is further to, for each of the grammar rules, perform the following calculation to generate the score;

((match points)÷

(rule words))×

((match points)÷

(input words)),

wherein the match points variable is the number of words in the partial data input that match either words or variables in the grammar rule, wherein the rule words variable is the combined number of both words and variables in the grammar rule, and wherein the input words variable is the number of words in the partial data input.

20. A computer as recited in claim 19, wherein to assign a score to each of the grammar rules is further to access a user context of the partial data input and modify the score of at least one of the grammar rules in accordance with the user context.

21. A computer as recited in claim 19, wherein the plurality of grammar rules conform to a Backus-Naur Form (BNF) format.

22. A computer as recited in claim 19, 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.

23. A computer as recited in claim 22, wherein to compare the partial data input to a plurality of grammar rules that identify valid inputs is to compare the partial data input to only the grammar rules in grammar modules corresponding to software modules that are currently executing.

24. A computer as recited in claim 19, wherein at least one of the plurality of grammar rules includes a variable.

25. A computer as recited in claim 19, wherein at least one of the plurality of grammar rules includes a wildcard.

26. A computer as recited in claim 19, 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.

27. A computer as recited in claim 26, wherein the plurality of instructions are further to modify 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.