Wild card auto completion

• US 8,712,989 B2
• Filed: 12/03/2010
• Issued: 04/29/2014
• 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
• Primary Examiner(s): Pham, Hung Q
• Application Number:
  US12/960,258
• Publication Number:
  US 20120143897A1
• Time in Patent Office: 1,243 Days
• Field of Search: None
• US Class Current: 707/706
• 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 and at least partly in an initial language, wherein the initial language and the target language are two different languages, the service employing a syntax to accept the input term including zero to multiple wild card characters in the target language or in the initial language in a first part and a delimiter indicating a second part, the second part comprising the target language or the initial language such that;

if the language of the first part includes the initial language, the second part includes the target language and if the language of the first part includes the target language, the second part includes the initial language, and the second part identifying at least one of a context or a domain for the wild card auto completion service;

identifying an initial-target language pair for the request;

aggregating two or more consecutive homogenous wild card characters, wherein the aggregating comprises replacing the two or more consecutive homogenous wild card characters with a single wild card character of a same type as the homogenous wild card character;

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, heterogeneous 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, wherein the input term includes multiple, predefined, heterogeneous wild card characters including a single character wild card character and a zero to multi-character wild card character.

8. A method as recited in claim 1, wherein the input term comprises a request for a part of speech and the entry matches the part of speech.

9. A method as recited in claim 1, wherein the pattern of the input term includes one or more of a pattern string parameter that represents the input term, a patternStartIndex parameter that represents a location to start matching the input term to dictionary entries, or a patternLength parameter that represents a length of the input term in terms of a number of characters entered.

10. A method as recited in claim 1, wherein the first part of the input term is in the target language and the second part of the input term is in the initial language, the second part identifying at least one of a context or a domain for the wild card auto completion service in the initial language.

11. 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:

accepting a request to a wild card auto completion service including an input term at least partly in a target language and partly in an initial language, wherein the initial language and the target language are two different languages, the service employing a syntax to accept the input term including zero to multiple wild card characters in the target language or in the initial language in a first part and a delimiter indicating a second part, the second part comprising the target language or the initial language such that;

if the language of the first part includes the initial language, the second part includes the target language and if the language of the first part includes the target language, the second part includes the initial language, and the second part identifying at least one of a context or a domain for the wild card auto completion service;

identifying an initial-target language pair for the request;

aggregating two or more consecutive homogenous wild card characters, wherein the aggregating comprises replacing the two or more consecutive homogenous wild card characters with a single wild card character of a same type as the homogenous wild card character;

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

matching the pattern of the input term to an entry; and

returning the entry.

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

13. The computer-readable medium of claim 11, wherein at least one of:

the input term includes multiple words and one of the multiple words is input in the initial language;

or

the input term includes multiple, predefined, heterogeneous wild card characters.

14. The computer-readable medium of claim 11, 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.

15. The computer-readable medium of claim 11, wherein at least one of:

the input term includes multiple, predefined, heterogeneous wild card characters including a single character wild card character and a zero to multi-character wild card character;

or

the input term comprises a request for a part of speech and the entry matches the part of speech.

16. The computer-readable medium of claim 11, wherein the first part of the input term is in the target language and the second part of the input term is in the initial language, the second part identifying at least one of a context or a domain for the wild card auto completion service in the initial language.

17. The computer-readable medium of claim 11, wherein the wild card auto completion operations further comprise selecting a matcher corresponding to the pattern of the input term, wherein matching the pattern of the input term to the entry includes using the matcher selected.

18. A computing device comprising:

a processor;

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

a wild card auto completion module configured to;

accept a request to a wild card auto completion service including an input term at least partly in a target language and partly in an initial language, wherein the initial language and the target language are two different languages, the service employing a syntax to accept the input term including zero to multiple wild card characters in the target language or in the initial language in a first part and a delimiter indicating a second part, the second part comprising the target language or the initial language such that;

if the language of the first part includes the initial language, the second part includes the target language and if the language of the first part includes the target language, the second part includes the initial language, and the second part identifying at least one of a context or a domain for the wild card auto completion service;

identify an initial-target language pair for the request;

aggregate two or more consecutive homogenous wild card characters, wherein the aggregating comprises replacing the two or more consecutive homogenous wild card characters with a single wild card character of a same type as the homogenous wild card character;

parse the input term to identify a pattern of the input term; and

return the list of results.

19. The computing device of claim 18, wherein the wild card auto completion module is further configured to:

select a matcher corresponding to the pattern of the input term; and

match the input term to an entry using the matcher selected.

20. The computing device of claim 18, wherein the first part of the input term is in the target language and the second part of the input term is in the initial language, the second part identifying at least one of a context or a domain for the wild card auto completion service in the initial language.