Grammar-based automatic data completion and suggestion for user input

• US 7,003,446 B2
• Filed: 12/17/2004
• Issued: 02/21/2006
• 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): Dorvil, Richemond
• Assistant Examiner(s): SPOONER, LAMONT M
• Application Number:
  US11/016,432
• Publication Number:
  US 20050102131A1
• Time in Patent Office: 431 Days
• Field of Search: 704/1, 704/9, 704/257, 715/534, 715/531, 715/533
• 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 system comprising:

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

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

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

means for assigning a score to each grammer rule in the set of grammer rules, the score indicating how closely the grammar rule matches the partial data input;

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

means for 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 means for assigning a score to each grammer rule in set of grammer rules comprises, for each grammer rule in the set of grammer rules, means for performing the following calculation to generate the score;

((match points variable)÷

(rule words variable))×

((match points variable)÷

(input words variable)),

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.

2. A system as recited in claim 1, wherein the means for assigning a score to each of the grammar rules further comprises means for 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. A system as recited in claim 1, wherein the plurality of grammar rules conform to a Backus-Naur Form (BNF) format.

4. A system 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.

5. A system as recited in claim 4, wherein the means for comparing comprises means for comparing the partial data input to only the grammar rules in grammar modules corresponding to software modules that are currently executing.

6. A system as recited in claim 1, wherein at least one of the plurality of grammar rules includes a variable.

7. A system as recited in claim 1, wherein at least one of the plurality of grammar rules includes a wildcard.

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

9. A system as recited in claim 8, further comprising means for modifying one of the set of grammar rules by replacing any variables or wildcards in the one of the set of grammer rules with matching portions of the previous partial data input.