Wild Card Auto Completion

• US 20120143897A1
• Filed: 12/03/2010
• Published: 06/07/2012
• Est. Priority Date: 12/03/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wei, Hao, Scott, Matthew Robert, Chen, Gang
• Granted Patent: US 8,712,989 B2
• Time in Patent Office: Days
• US Class Current: 707/769
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs

Abstract

Described herein is a technology that facilitates efficient wild card auto completion of an input term. The technology supports the input term including multiple, predefined, distinct wild card characters, escape characters, special characters with language specific functionality, delimiters, and context designation. Wild card auto completion is based on a regular expression engine that supports the multiple, predefined, wild card characters. In addition, the technology supports a single input that may include multiple parts including context, domain, parts of speech, and a number of words in a result phrase. In various embodiments the technology facilitates pattern optimization to merge a subset of consecutive homogenous wild card characters and provides a selection of matching tools based on criteria including the type of wild card character included in the input term and where the wild card character appears in the input term as well as context.

Claims

1. A method comprising:

accepting a request to a wild card auto completion service including an input term at least partly in a target language, the service employing a syntax to accept the input term including zero to multiple wild card characters in a first part and a delimiter indicating a second part;

identifying an initial-target language pair for the request;

parsing the input term to identify a pattern of the input term;

selecting a matcher corresponding to the pattern of the input term;

matching the input term to an entry using the matcher selected; and

returning the entry.

2. A method as recited in claim 1, wherein the input term includes more than one word.

3. A method as recited in claim 1, wherein the input term includes multiple words and one of the multiple words is input in the initial language.

4. A method as recited in claim 1, wherein the input term includes multiple, predefined, discrete wild card characters.

5. A method as recited in claim 1, wherein matching the input term to the dictionary entry includes:

performing a prefix match to identify a sorted list of dictionary entries matching a prefix made up of characters in the input term that precede a first wild card character in the input term; and

performing a binary search on the dictionary entries matching the prefix, the dictionary entries corresponding to a number of characters that the at least one wild card character represents.

6. A method as recited in claim 1, wherein the returning the entry includes refining the entry to enhance presentation.

7. A method as recited in claim 1, further comprising, in an event the input term comprises at least two consecutive homogeneous wild card characters, optimizing the consecutive homogeneous wild card characters to obtain an optimized input term.

8. A method as recited in claim 1, wherein the input term includes multiple, predefined, discrete wild card characters including a single character wild card character and a zero to multi-character wild card character.

9. A computer-readable medium having computer executable instructions encoded thereon, the computer executable instructions for execution by a processor to perform wild card auto completion operations, the operations comprising:

supporting multiple predefined discrete wild card characters in a single input term;

representing a matched result corresponding to a pattern of the single input term.

10. A computer-readable medium as recited in claim 9, wherein the single input term includes one or more words.

11. A computer-readable medium as recited in claim 9, wherein the representing includes refining the matched results to emphasize non wild card characters from the single input term in the matched result in contrast to characters matched to one or more of the multiple predefined discrete wild card characters from the single input term.

12. A computer-readable medium as recited in claim 9, the operations further comprising based at least on the single input term, selecting one or more of a plurality of match technologies including a prefix matching technology and a wild card matching technology to obtain the matched result.

13. A computer-readable medium as recited in claim 12, wherein the prefix matching technology employs extended binary search of a sorted list.

14. A computer-readable medium as recited in claim 9, the operations further comprising facilitating pattern optimization in an event that the multiple, predefined, discrete wild card characters comprise a set of consecutive, predefined, discrete wild card characters.

15. A computer-readable medium as recited in claim 9, the operations further comprising facilitating pattern optimization in an event that the multiple predefined discrete wild card characters comprise a set of consecutive homogeneous wild card characters.

16. A computer-readable medium as recited in claim 15, wherein the pattern optimization includes merging two or more consecutive homogeneous wild card characters.

17. A computer-readable medium as recited in claim 9, the operations further comprising performing near miss resolution to reconcile unmatched results

18. A computer-readable medium as recited in claim 9, the operations further comprising defining a wild card auto completion syntax including one or more of a user configurable escape character, special characters with language specific functionality, delimiters, or context.

19. A computing device comprising:

a processor;

a memory communicatively coupled to the processor, the memory storing modules comprising;

a wild card auto completion module to perform wild card auto completion operations including pattern optimization and matching to generate a list of results matching an input term including at least one of multiple predefined discrete wild card characters to an entry; and

a presentation module to refine the list of results.

20. A computing device as recited in claim 19, wherein to refine the list of results includes performing marking operations on the list of results including emphasizing characters in the entry that correspond to characters from the input term in contrast to characters in the entry matched to the at least one multiple predefined discrete wild card characters included in the input term.