Dynamic spelling correction of search queries

• US 8,700,654 B2
• Filed: 09/13/2011
• Issued: 04/15/2014
• Est. Priority Date: 09/13/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Mehanna, Hussein Mohamed, Govani, Tabreez, Proskurin, Andrey
• Primary Examiner(s): Saeed, Usmaan
• Assistant Examiner(s): Uddin, Md. I
• Application Number:
  US13/231,049
• Publication Number:
  US 20130066896A1
• Time in Patent Office: 945 Days
• Field of Search: 707/765, 707/766, 707/767, 707/719, 707/722, 707/723, 707/999.003
• US Class Current: 707/767
• CPC Class Codes: G06F 16/2425 Iterative querying; Query formulation based on the results of a preceding query
• CPC Class Codes: G06F 16/243 Natural language query formulation

Abstract

Methods, computer systems, and computer-readable storage media for dynamically correcting misspelled search queries are provided. A portion of a search query is received, and a data store is accessed. It is determined that the portion of the search query is absent from the data store and, thus, comprises a misspelled portion of a search query. Correctly spelled portions of search queries are dynamically determined for the misspelled portion of the search query using a trie data structure, and the misspelled portion of the search query is associated with the correctly spelled portions of search queries. Search suggestions are determined for the correctly spelled portions of search queries and are ranked based on a frequency of use and on a transformation cost of associating the misspelled portion of the search query with the correctly spelled portion of search queries. The ranked search suggestions are provided to a user.

Claims

1. One or more computer-readable storage media having computer-executable instructions embodied thereon that, when executed, facilitate a method of providing relevant search suggestions, the method comprising:

receiving a portion of a search query from a user;

accessing a data store, the data store comprising a plurality of correctly spelled complete search queries, a plurality of correctly spelled portions of search queries, and a plurality of search suggestions;

using the data store, determining that the portion of the search query is associated with a first set of search suggestions;

determining that the portion of the search query is a misspelled portion of a search query when the first set of search suggestions is less than a predetermined number;

dynamically determining a first set of correctly spelled portions of search queries that are similar to the misspelled portion of the search query;

creating an association between the misspelled portion of the search query and the set of correctly spelled portions of search queries;

using the data store, determining a second set of search suggestions associated with the set of correctly spelled portions of search queries, wherein the set of correctly spelled portions of search queries have been associated with the misspelled portion of the search query;

aggregating the first set of search suggestions and the second set of search suggestions to create a third set of search suggestions, wherein the first set of search suggestions is associated with the misspelled portion of the search query and the second set of search suggestions is associated with the set of correctly spelled portions of search queries that have been associated with the misspelled portion of the search query;

ranking the third set of search suggestions based on a frequency of use of each of the search suggestions within the third set of search suggestions and on a transformation cost of associating the misspelled portion of the search query with the set of correctly spelled portions of search queries;

wherein the transformation cost is a numerical value that is inversely proportional to a probability that the user intended to input a character other than the character in the misspelled portion of the search query; and

providing the third set of search suggestions to a search engine page.

2. The media of claim 1, wherein the portion of the search query received from the user is received via the user inputting the portion of the search query using a keyboard.

3. The media of claim 2, wherein the misspelled portion of the search query is misspelled due to a typographical error.

4. The media of claim 1, wherein the transformation cost is greater if the typographical error involves characters that are spaced far apart on the keyboard.

5. The media of claim 1, wherein the ranking of a search suggestion within the third set of search suggestions is inversely proportional to the transformation cost.

6. The media of claim 1, wherein the ranking of a search suggestion within the third set of search suggestions is directly proportional to a frequency of use of the search suggestion.

7. One or more computer-readable storage media having computer-executable instructions embodied thereon that, when executed, facilitate a method of associating one or more correctly spelled portions of search queries with a misspelled portion of a search query, the method comprising:

receiving a portion of a search query from a user, the portion of the search query comprising a first character and a second character, wherein the second character follows the first character;

accessing a data store, the data store comprising a plurality of correctly spelled complete search queries, misspelled complete search queries, correctly spelled portions of search queries, and misspelled portions of search queries;

determining that the portion of the search query is absent from the data store;

determining that the portion of the search query is a misspelled portion of a search query when the portion of the search query is absent from the data store;

dynamically determining that the second character is capable of being modified to create a first correctly spelled portion of a search query, wherein the first correctly spelled portion of a search query is in the data store;

dynamically determining a first transformation cost for modifying the second character to create the first correctly spelled portion of a search query, the first transformation cost being inversely proportional to a probability that the user intended to input the first correctly spelled portion of a search query;

dynamically determining that the first transformation cost is less than a predetermined threshold;

dynamically associating the misspelled portion of the search query with the first correctly spelled portion of a search query when the first transformation cost is less than the predetermined threshold

dynamically determining a first set of search suggestions corresponding to the first correctly spelled portion of the search query;

ranking the first set of search suggestions based on the first transformation cost and a frequency of use of each search suggestion in the first set of search suggestions; and

providing the first set of search suggestions to a search engine page.

8. The media of claim 7, wherein the misspelled portion of the search query further comprises a third character, wherein the third character follows the second character.

9. The media of claim 8, further comprising:

dynamically determining that the third character is capable of being modified to create a second correctly spelled portion of a search query, wherein the second correctly spelled portion of a search query is in the data store;

dynamically determining a second transformation cost for modifying the third character to create the second correctly spelled portion of a search query;

dynamically determining that the second transformation cost is less than a second predetermined threshold, the second predetermined threshold being greater than the first predetermined threshold; and

dynamically associating the misspelled portion of the search query with the second correctly spelled portion of a search query when the second transformation cost is less than the second predetermined threshold.

10. The media of claim 9, further comprising:

dynamically determining a second set of search suggestions corresponding to the second correctly spelled portion of a search query;

aggregating the first set of search suggestions and the second set of search suggestions to create an aggregated set of search suggestions;

ranking the aggregated set of search suggestions based on the first transformation cost, the second transformation cost, and a frequency of use of each search suggestion in the aggregated set of search suggestions; and

providing the ranked aggregated set of search suggestions to a search engine page.

11. The media of claim 10, wherein the ranked aggregated set of search suggestions is presented to a user.

12. One or more computer-readable storage media having computer-executable instructions embodied thereon that, when executed, facilitate a method of dynamically correcting a misspelled portion of a search query, the method comprising:

receiving a portion of a search query from a user, wherein the portion of the search query begins with a first character and comprises one or more additional characters;

accessing a data structure, the data structure comprising a plurality of stored relationships between misspelled portions of search queries and associated correctly spelled portions of search queries;

using the data structure, determining that the portion of the search query is not related to an associated correctly spelled portion of a search query;

determining that the portion of the search query is a misspelled portion of a search query when the portion of the search query is not related to an associated correctly spelled portion of a search query;

beginning with the one or more additional letters that comprise the misspelled portion of the search query, determining that each character of the one or more additional characters is capable of being modified to create one or more correctly spelled portions of search queries;

incident to determining that the each character of the one or more additional characters is capable of being modified to create the one or more correctly spelled portions of search queries, determining a transformation cost for modifying the each character of the one or more additional characters, wherein the transformation cost is a numerical value that is inversely proportional to a probability that the user intended to input a character other than the character in the misspelled portion of the search query;

determining that each of the transformation costs is below a predetermined threshold;

associating the misspelled portion of the search query with the one or more correctly spelled portions of search queries;

determining one or more search suggestions associated with the one or more correctly spelled portions of search queries;

ranking the one or more search suggestions based on a frequency of use of each search suggestion in the one or more search suggestions and on the transformation cost for modifying the each character of the one or more additional characters; and

providing the one or more search suggestions to a search engine page, wherein the one or more search suggestions are presented in ranked order.

13. The media of claim 12, wherein determining that the portion of the search query is misspelled further comprises determining that the portion of the search query received from the user is absent from the data structure.

14. The media of claim 12, wherein the data structure further comprises a plurality of search suggestions associated with the correctly spelled portions of search queries.

15. The media of claim 12, wherein determining that the each character of the one or more additional characters is capable of being modified to create the one or more correctly spelled portions of search queries comprises using a trie data structure.

16. The media of claim 15, wherein the trie data structure is generated using data within the data structure.

17. The media of claim 15, wherein the trie data structure comprises a plurality of nodes and a plurality of paths, wherein each node represents a character.

18. The media of claim 17, wherein traversal of one of the plurality of paths generates a correctly spelled portion of a search query.

19. The media of claim 12, wherein the each character can be modified by adding an additional character, removing the each character, or replacing the each character with a new character.