System and method for correcting spelling errors in search queries

• US 6,144,958 A
• Filed: 07/15/1998
• Issued: 11/07/2000
• Est. Priority Date: 07/15/1998
• Status: Expired due to Term

• Current Assignee: A9.com Incorporated (Amazon.com, Inc.), Micron Technology, Inc.
• Original Assignee: Amazon.com, Inc.
• Inventors: Hamrick, Michael L., Kohn, Timothy R., Spiegel, Joel R., Ortega, Ruben Ernesto, Bowman, Dwayne Edward
• Primary Examiner(s): Alam, Hosain T.
• Application Number:
  US09/115,662
• Time in Patent Office: 846 Days
• Field of Search: 707/5, 707/1-4, 707/6, 707/10, 707/510, 707/513, 709/217-219
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: G06F 16/90 Details of database functions independent of the retrieved data types
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9532 Query formulation
• CPC Class Codes: G06F 40/226 Validation
• 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
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A search engine is disclosed that uses correlations between search terms to correct misspelled terms within search queries. The correlations are based at least in-part on historical query submissions to the search engine. Preferably, the correlations reflect the frequencies with which the search terms have historically appeared together within the same query, and are stored within a correlation table using related terms lists. In one embodiment, the correlation table is generated periodically from the M (e.g. 10) most recent days of entries in a query log, and thus reflects the current preferences of users. In operation, when a query that includes both matching and non-matching search terms is submitted to the search engine, a spelling correction process accesses the correlation table to generate a list of terms that are deemed to be related to the matching term(s). The spellings of these related terms are then compared to the spelling of each non-matching term using a spelling comparison function that compares two character strings and generates a similarity score. If a suitable replacement is found for a given non-matching term, the non-matching term is replaced with the similar related term. The modified query is then used to perform the search, and the user is notified of the modification(s) made to the query. In the disclosed embodiment, the search engine is used on the Web site of an online merchant to assist users in locating book titles, music titles, and other types of products.

Claims

1. In a computer system that implements a search engine that is accessible to users over a computer network, a method of handling misspelled search terms in search queries, the method comprising the computer-implemented steps of:

(a) processing search queries submitted to the search engine by a plurality of users over a period of time to generate correlation data, the correlation data indicating correlations between search terms based at least upon frequencies of prior occurrences of the search terms within the same search query;

(b) receiving a search query from a user over the computer network, the search query comprising a plurality of search terms and being directed to an informational database to be searched;

(c) identifying within the search query a non-matching search term which does not produce a match within the informational database, and at least one matching search term which produces a match within the informational database;

(d) using at least the correlation data to identify a plurality of additional terms that are deemed to be related to the at least one matching search term; and

(e) comparing the additional terms identified in step (d) to the non-matching term to identify an additional term that is a candidate correctly-spelled replacement term for the non-matching term.

2. The method of claim 1, further comprising the computer-implemented steps of:

(f) without requiring user input, replacing the non-matching term with the candidate replacement term within the search query to generate a modified search query;

(g) applying the modified search query to the informational database to perform a search; and

(h) notifying the user of the query result of step (g) and of the replacement made in step (f).

3. The method of claim 1, wherein step (a) comprises updating the correlation data substantially in real time as search queries are received from users.

4. The method of claim 1, wherein step (a) comprises parsing a log that includes queries submitted to the search engine.

5. The method of claim 4, wherein step (a) further comprises applying a time-based biasing function to the log to favor recent search query submissions over aged search query submissions.

6. The method of claim 5, wherein the step of applying a time-based biasing function comprises applying a window function to the log.

7. The method of claim 1, wherein step (a) comprises ignoring search queries that produce a null query result.

8. The method of claim 1, wherein step (a) further comprises evaluating post-query-submission actions of users to identify search queries that are deemed to have produced a successful result, and weighing the search queries that produced a successful result more heavily in generating the correlation data.

9. The method of claim 1, wherein step (c) comprises identifying a plurality of non-matching search terms within the search query, and the method comprises repeating step (e) for each of the non-matching search terms to identify a candidate replacement term for each non-matching search term.

10. The method of claim 1, wherein step (d) comprises:

(d1) for each of a plurality of matching search terms, identifying a respective list of related terms; and

(d2) combining the lists of related terms of identified in step (d1).

11. The method of claim 1, wherein step (e) comprises using a spelling comparison function to compare the non-matching term to the additional terms, the spelling comparison function adapted to compare first and second character strings by sorting the first and second strings and comparing the sorted first and second strings on a character-by-character basis.

12. The method of claim 11, wherein the spelling comparison function generates a score which indicates a degree of similarity between the first and second character strings, and wherein step (e) further comprises comparing a score generated by the scoring function to a threshold value to determine whether a corresponding additional term is a candidate replacement, the threshold value dependent upon a number of characters in the non-matching term.

13. The method of claim 1, wherein step (e) comprises identifying a plurality of candidate correctly-spelled replacement terms for the non-matching term, and the method further comprises presenting the user with a list of the candidate replacement terms for selection.

14. The method of claim 13, wherein the step of presenting the user with a list comprises presenting each candidate replacement term within a respective hyperlink which can be selected by the user to initiate a modified search.

15. The method of claim 1, wherein the computer system is part of a Web site, and the informational database includes information about products that are available for purchase via the Web site.

29. The method as in claim 1, further comprising the steps of:

(f) receiving a second search query from a second user;

(g) using at least the second search query and the correlation data to identify a set of related search terms; and

(h) presenting the set of related search terms to the second user, in conjunction with search results, as suggested refinements to the second search query.

30. The method as in claim 29, wherein the second search query comprises multiple search terms, and step (g) comprises using the correlation data to identify terms that are related to each of the miltiple search terms.

31. The method as in claim 29, wherein step (h) comprises presenting each related search term using a respective textual link that is selectable to initiate a refined search.

16. In a computer system that implements a search engine that is accessible to users over a computer network, a method of processing a search query that includes at least one misspelled search term, the method comprising the computer-implemented steps of:

(a) receiving the search query from a user over the computer network, the search query comprising a plurality of search terms and being directed to an informational database to be searched;

(b) identifying within the search query a non-matching search term which does not produce a match within the informational database, and at least one matching search term which produces a match within the informational database;

(c) using search term correlation data to identify a plurality of additional terms that are deemed to be related to the at least one matching search term, the search term correlation data based at least on historical query submissions; and

(d) comparing the additional terms identified in step (c) to the non-matching term to identify an additional term that is a candidate correctly-spelled replacement for the non-matching term.

17. The method of claim 16, wherein the search term correlation data is based at least on frequencies with which search terms have previously occurred within the same query.

18. The method of claim 16, further comprising the step of processing historical query submissions within a log to generate the search term correlation data.

19. The method of claim 18, wherein the step of processing historical query submissions comprises applying a window function to the log.

20. The method of claim 18, wherein the step of processing historical query submissions comprises ignoring queries that produced null query results.

21. The method of claim 16, further comprising the computer-implemented steps of:

(e) without requiring user input, replacing the non-matching term with the candidate replacement term within the search query to generate a modified search query;

(f) applying the modified search query to the informational database to perform a search; and

(g) notifying the user of the query result of step (f) and of the replacement made in step (e).

22. The method of claim 16, wherein step (d) comprises using a spelling comparison function to compare the non-matching term to the additional terms, the spelling comparison function adapted to compare first and second character strings by sorting the first and second strings and comparing the sorted first and second strings on a character-by-character basis.

23. The method of claim 22, wherein the spelling comparison function generates a score which indicates a degree of similarity between the first and second character strings, and wherein step (d) further comprises comparing a score generated by the scoring function to a threshold value to determine whether a corresponding additional term is a candidate replacement, the threshold value dependent upon a length of the non-matching term.

24. A search engine for allowing users of a computer network to conduct searches of a database of items, the search engine comprising:

a computer system which has search term correlation data stored in a memory thereof, the search term correlation data indicating correlations between search terms based at least upon prior query submissions of users; and

a query server which runs on the computer system, the query server adapted to search the database of items using search queries received from users, the query server configured to process a multi-term search query that includes both matching and non-matching terms by at least;

accessing the search term correlation data to identify a plurality of additional terms that are deemed to be related to the matching terms(s) of the search query; and

comparing the spellings of the additional terms to the spelling of at least one non-matching term of the query to determine whether any of the additional terms is a candidate replacement for the non-matching term.

25. The search engine of claim 24, wherein the search term correlation data is based at least on frequencies with which search terms have previously occurred within the same query.

26. The search engine of claim 24, wherein the query server is configured to, without requiring user input:

replace a non-matching term with an additional term to generate a modified query; and

search the database of items with the modified query.

27. The search engine of claim 24, wherein the query server compares the additional terms to the non-matching term using a spelling comparison function, the spelling comparison function adapted to compare first and second character strings by sorting the first and second strings and comparing the sorted first and second strings on a character-by-character basis.

28. The search engine of claim 27, wherein the spelling comparison function generates a score which indicates a degree of similarity between the first and second character strings, and wherein the query server compares a score generated by the scoring function to a threshold value to determine whether a corresponding additional term is a candidate replacement.