Grammar-based automatic data completion and suggestion for user input

• US 20050043942A1
• 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,171,353 B2
• Time in Patent Office: Days
• US Class Current: 704/10
• 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.

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) format.

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 accepted 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 user input to an edit control of a user interface;

comparing the user input to a plurality of rules that correspond to valid inputs;

determining which of the plurality of rules is expected to have the highest likelihood of correctly completing the user input; and

presenting the selected rule as an automatic completion option for the user input to the edit control.

11. A method as recited in claim 10, wherein the presenting comprises displaying at least a portion of the grammar rule in the edit control.

12. A method as recited in claim 10, wherein the receiving comprises receiving user input to an edit control of a graphical user interface.

13. A method as recited in claim 10, further comprising receiving a user acceptance of the selected rule as the user'"'"'s desired input.

14. A method as recited in claim 10, further comprising receiving a user acceptance of only a portion of the selected rule as part of the user'"'"'s desired input.

15. One or more computer-readable memories containing a computer program that is executable by a processor to perform the method recited in claim 10.

16. A method comprising:

receiving user input to a user interface;

comparing the user input to a plurality of rules that correspond to valid inputs;

selecting a set of one or more rules from the plurality of rules, wherein the selecting comprises;

generating a score for each of the plurality of rules that match the user input, and

selecting rules with a score that exceeds a threshold value; and

presenting the set of one or more rules as suggested completion options for the user input.

17. A method as recited in claim 16, wherein the presenting comprises presenting the set of one or more rules in alphabetical order.

18. A method as recited in claim 16, further comprising receiving a user selection of one of the suggested completion options as a completion of the user'"'"'s input.

19. One or more computer-readable memories containing a computer program that is executable by a processor to perform the method recited in claim 16.

20. A system comprising:

an analysis module to,

receive a partial data input,

generate, using a plurality of grammar rules, a set of options to complete the partial data input,

associate a ranking with each option in the set of options; and

a display module, coupled to the analysis module, to display at least a subset of the set of options.

21. A system as recited in claim 20, wherein the display module is to display a first option of the set of options in a same edit control as the partial data input is being presented, and to display a plurality of the subset of options in a suggestion list associated with the edit control.

22. A system as recited in claim 20, wherein the system further comprises a scoring module, coupled to the analysis module, to generate the ranking for each option in the set of options.

23. A system as recited in claim 20, wherein the display module is further to display at least a subset of the set of options by displaying the highest ranking options.

24. A user interface for accepting data input from a user, the user interface comprising:

an edit control including a first portion in which data input received from a user is displayed, and a second portion in which auto completion data is displayed; and

a suggestion list including at least one completion data option that is selected based on at least one rule corresponding to a valid input.

25. A user interface as recited in claim 24, wherein the second portion of the edit control abuts the first portion, so that the data input received from the user combined with the auto completion data results in a complete data entry.

26. A user interface as recited in claim 24, wherein the completion data in the second portion are displayed in an alphabetical ordering.

27. A user interface as recited in claim 24, wherein the suggestion list is displayed in response to a user request for the suggestion list.

28. A user interface as recited in claim 27, wherein the user request for the suggestion list comprises user selection of a pull-down menu button.

29. A user interface as recited in claim 24, wherein the auto completion data in the second portion is displayed in a manner to differentiate it from the data input in the first portion.

30. A user interface as recited in claim 29, wherein the auto completion data is highlighted and the data input is not highlighted.

31. A user interface as recited in claim 24, wherein the user interface comprises a graphical user interface.

32. 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;

waiting until the data input has paused for a first amount of time in the event data is being added to the edit control, and waiting until the data input has paused for a second amount of time in the event data is being deleted from the edit control; and

analyzing, after completing the waiting, the partial data input to identify one of the plurality of grammar rules to automatically complete the data input and a set of the plurality of grammar rules to suggest as completion options.