16

I'm implementing search suggestion functionality in my web-app, and have been looking at existing implementations for techniques in use.

It seems as though most of the major sites (Amazon, Bing, etc.) implement fuzzy search in the following way:

Tokenize search string in to terms
processingSearchStringSet = {}
For each term
    if exact term is NOT in index
        Get possible terms (fuzzyTerms) from levenshtein(term, 1 (or 2))
        For each term in fuzzyTerms
            if term is in index
                processingSearchStringSet.intersect(stringsIndexedByTermsSet)
    else
        processingSearchStringSet.intersect(stringsIndexedByTermsSet)

The result set members are then presumably ranked by metrics (ex: term order preserval, absolute term location, search popularity) and preserved or eliminated based on this ranking and a pre-determined result set size before being delivered back to the user.

Google's implementation on the other hand, differs quite a bit from this.

Specifically, it allows more than 1 error in the search string's constituent terms. The error threshhold seems to be dependant on where the term of interest is in the string, though it never exceeds 7.

What's interesting is that:

  1. Conducting a Levenstein search with a threshold of 5 on the entire term space, for each term in the user's string would be insanely expensive
  2. Even if #1 is what is done, it still wouldn't explain the absence of erroneous suggestions

N-grams also don't see to be in use: modifying a term so that it doesn't contain an bigram present in the original term does not seem to affect the result(s).

Here's an example to illustrate my findings:

Example term: "Fiftyyyy shades of grey"

Amazon suggestions: none 
(if the error count exceeds 1 on any term, the search fails)

Bing suggestions: none
(if the error count exceeds 2 on any term, the search fails)

Google suggestions: 10 (max) 
(breaking the search would require 5 or more errors on any single term, 
or multiple errors on multiple terms)

My question is: what type of sorcery is at work here? Are they just using a Levenshtein search with a huge error allowance, or do they use another technique I am unaware of?

5
  • 3
    Peter Norvig (Director of Research at google) in this talk (starting at 28:30 or so) discusses the use of probabilistic models (corpus based) for spelling corrections.
    – lccarrasco
    Commented Sep 2, 2012 at 21:24
  • @lccarasco: Thanks! I suppose the corpus-based approach (specifcally the part measuring the probability of certain errors) accounts for what I observed.
    – Kevin
    Commented Sep 2, 2012 at 22:28
  • 4
    I have no idea what the actual algorithm used by google is, so this is pure speculation: I always figured they monitor cases where the same user searches for query_1, does not click any link, then searches for similar terms (query_2). Average this over a large enough sample set. If 100 people searched for query1, followed by query2, then when another user searches for query_1, present query_2 as suggestion. You can refine that further by first breaking the queries up in individual words or phrases
    – HugoRune
    Commented Sep 2, 2012 at 23:06
  • @HugoRune I believe this is correct, google's algorithms solve this problem by with a ton of data comparing your search to similar searches by others, not by comparing your search to the actual data. I remember reading somewhere that even their "did you mean X" for spelling mistakes isn't based off of a list of words in some canonical dictionary, it is based purely off of the search behaviour of users after making similar errors. Commented Sep 3, 2012 at 7:16
  • 1
    @HugoRune That could be why sometimes "Did you mean.." comes up instead of "Searching for x instead of y," to verify this is a typo.
    – Pieter Bos
    Commented Sep 5, 2012 at 16:19

1 Answer 1

1

Maybe you should try this approach: http://norvig.com/spell-correct.html

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.