Error model formation

• US 8,321,471 B2
• Filed: 03/30/2005
• Issued: 11/27/2012
• Est. Priority Date: 03/16/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Cucerzan, Silviu P.
• Primary Examiner(s): Kerzhner, Aleksandr
• Assistant Examiner(s): Bullock, Joshua
• Application Number:
  US11/094,078
• Publication Number:
  US 20050210017A1
• Time in Patent Office: 2,799 Days
• Field of Search: None
• US Class Current: 707/803
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/9532 Query formulation
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation

Abstract

In a method of forming a target error model to facilitate correcting or suggesting corrections to misspelled input text related to a target data collection, a source query log containing user queries to at least one source data collection is provided. Next, target relational data is generated based on the source query log including corrective substring suggestions that relate to the target data collection and corresponding misspelled substrings extracted from the source query log. A target error model is then built using the target relational data. The target error model includes target statistical occurrence data for the substrings of the target relational data derived from the source query log. Finally, the target error model is stored on a computer readable medium. Additional embodiments of the invention are directed to a system configured to implement the method.

Claims

1. A method of forming a target error model to facilitate spell checking input text related to a target data collection comprising steps of:

a) providing a source query log containing user queries to at least one source data collection;

b) generating target relational data based on the source query log including corrective substring suggestions that relate to the target data collection and corresponding misspelled substrings for the corrective substring suggestions extracted from the source query log, by applying a source error model to the source query log to thereby generate source relational data including corrective substring suggestions for misspelled substrings of the source query log, and selecting a subset of the source relational data that relate to the target data collection as the target relational data;

c) building a target error model using the target relational data including target statistical occurrence data for the substrings of the target relational data derived from the source query log; and

d) storing the target error model on a computer readable medium.

2. The method of claim 1, wherein the target relational data includes corrective substring suggestions from the source relational data that match substrings of the target data collection.

3. The method of claim 1, wherein the generating step b) includes filtering the source relational data using named entities of the target data collection.

4. The method of claim 3, wherein the target relational data includes the corrective substring suggestions of the source relational data that match the named entities of the target data collection and their corresponding misspelled substrings.

5. The method of claim 4, wherein the named entities are selected from the group consisting of names of people, names of locations, company names, product names, book titles, names of diseases, drug names, names of software processes, names of music bands, song titles, and album titles.

6. The method of claim 1, wherein the source error model contains statistical occurrence data and is generated based on input queries to the at least one source data collection.

7. The method of claim 1, wherein the target statistical occurrence data includes at least one of occurrence statistics and co-occurrence statistics for the substrings of the target relational data.

8. The method of claim 1, wherein the building step c) includes providing a searchable lexicon data structure.

9. A method of forming a target error model to facilitate spell checking input text related to a target data collection comprising steps of:

a) providing first and second source query logs comprising query data corresponding to user queries to at least one source data collection by dividing a primary source query log corresponding to user queries to the source data collection into the first and second source query logs;

b) generating source statistical occurrence data for substrings of the first source query log;

c) generating source relational data including corrective substring suggestions for misspelled substrings of the second source query log based on an application of the statistical occurrence data to the second source query log;

d) selecting a subset of the corrective substring suggestions and their corresponding misspelled substrings of the source relational data that relate to substrings of the target data collection as target relational data;

e) building a target error model using the target relational data including target statistical occurrence data for the substrings of the target relational data; and

f) storing the target error model on a computer readable medium.

10. The method of claim 9, wherein the building step e) includes counting at least one of occurrences and co-occurrences of substrings in the target relational data to build the target statistical occurrence data.

11. The method of claim 9, wherein the target statistical occurrence data includes at least one of unigram statistics and bigram statistics for the substrings of the target relational data.

12. The method of claim 9, wherein the generating step d) includes filtering the source relational data using named entities of the target data collection.

13. The method of claim 12, wherein the target relational data includes the corrective substring suggestions that match the named entities of the target data collection and their corresponding misspelled substrings.

14. The method of claim 9, wherein the building step e) includes providing a searchable lexicon data structure.

15. A system for forming a target error model to facilitate spell checking input text related to a target data collection comprising:

a source query log comprising query data to at least one source data collection;

a target relational data generator having an output of target relational data including corrective substring suggestions that relate to the target data collection and corresponding misspelled substrings for the corrective substring suggestions extracted from the source query log;

a target error model generator including an output of target statistical occurrence data including at least one of unigram statistics and bigram statistics for the substrings of the target relational data;

a computer storage medium containing a target error model comprising the target statistical occurrence data; and

a computer processor being a functional component of the system and facilitating generating the output of the target relational data generator and the target error model generator.

16. The system of claim 15 including a substring analyzer configured to generate source statistical occurrence data including at least one of unigram statistics and bigram statistics of queries to the at least one source data collection, wherein the target relational data is generated based on an application of the source statistical occurrence data to the source query log.

17. The system of claim 16, wherein the target relational data generator includes a source relational data generator configured to apply the source statistical occurrence data to the source query log to thereby generate source relational data including corrective substring suggestions for corresponding misspelled substrings of the source query log, wherein the target relational data comprises a subset of the source relational data.

18. The system of claim 17, wherein the target relational data generator includes a comparator including an output of the target relational data that includes the corrective substring suggestions that match named entities of the target data collection and their corresponding misspelled substrings.