Algorithm for autocomplete?

I am referring to the algorithm that is used to give query suggestions when a user types a search term in Google.

I am mainly interested in: 1. Most important results (most likely queries rather than anything that matches) 2. Match substrings 3. Fuzzy matches

I know you could use Trie or generalized trie to find matches, but it wouldn't meet the above requirements...

Similar questions asked earlier here

Answers


For (heh) awesome fuzzy/partial string matching algorithms, check out Damn Cool Algorithms:

These don't replace tries, but rather prevent brute-force lookups in tries - which is still a huge win. Next, you probably want a way to bound the size of the trie:

  • keep a trie of recent/top N words used globally;
  • for each user, keep a trie of recent/top N words for that user.

Finally, you want to prevent lookups whenever possible...

  • cache lookup results: if the user clicks through on any search results, you can serve those very quickly and then asynchronously fetch the full partial/fuzzy lookup.
  • precompute lookup results: if the user has typed "appl", they are likely to continue with "apple", "apply".
  • prefetch data: for instance, a web app can send a smaller set of results to the browser, small enough to make brute-force searching in JS viable.

I'd just like to say... A good solution to this problem is going to incorporate more than a Ternary Search Tree. Ngrams, and Shingles (Phrases) are needed. Word-boundary errors also need to be detected. "hell o" should be "hello" ... and "whitesocks" should be "white socks" - these are pre-processing steps. If you don't preprocess the data properly you aren't going to get valuable search results. Ternary search trees are a useful component in figuring out what is a word, and also for implementing related-word guessing when a word typed isn't a valid word in the index.

The google algorithm performs phrase suggestion and correction. The google algorithm also has some concept of context... if the first word you search for is weather related and you combine them "weatherforcst" vs "monsoonfrcst" vs "deskfrcst" - my guess is behind the scenes rankings are being changed in the suggestion based on the first word encountered - forecast and weather are related words therefore forecast get's a high rank in the Did-You-Mean guess.

word-partials (ngrams), phrase-terms (shingles), word-proximity (word-clustering-index), ternary-search-tree (word lookup).


Google's exact algorithm is unknown, but it is said to work by statistical analysis of users input. An approach not suitable for most cases. More commonly auto completion is implemented using one of the following:

  • Trees. By indexing the searchable text in a tree structure (prefix tree, suffix tree, dawg, etc..) one can execute very fast searches at the expense of memory storage. The tree traversal can be adapted for approximate matching.
  • Pattern Partitioning. By partitioning the text into tokens (ngrams) one can execute searches for pattern occurrences using a simple hashing scheme.
  • Filtering. Find a set of potential matches and then apply a sequential algorithm to check each candidate.

Take a look at completely, a Java autocomplete library that implements some of the latter concepts.


There are tools like soundex and levenshtein distance that can be used to find fuzzy matches that are within a certain range.

Soundex finds words that sound similar and levenshtein distance finds words that are within a certain edit distance from another word.


Take a look at Firefox's Awesome bar algorithm

Google suggest is useful, because it take the millions of popular queries + your past related queries into account.

It doesn't have a good completion algorithm / UI though:

  1. Doesn't do substrings
  2. Seems like a relatively simple word-boundary prefix algorithm. For example: Try tomcat tut --> correctly suggest "tomcat tutorial". Now try tomcat rial --> no suggestions )-:
  3. Doesn't support "did you mean?" - as in google search results.

For substrings and fuzzy matches, the Levenshtein distance algorithm has worked fairly well for me. Though I will admit it does not seem to be as perfect as industry implementations of autocomplete/suggest. Both Google and Microsoft's Intellisense do a better job, I think because they've refined this basic algorithm to weigh the kind of edit operations it takes to match the dissimilar strings. E.g. transposing two characters should probably only count as 1 operation, not 2 (an insert & delete).

But even so I find this is close enough. Here is it's implementation in C#...

// This is the traditional Levenshtein Distance algorithem, though I've tweaked it to make
// it more like Google's autocomplete/suggest.  It returns the number of operations 
// (insert/delete/substitute) required to change one string into another, with the 
// expectation that userTyped is only a partial version of fullEntry.
// Gives us a measurement of how similar the two strings are.
public static int EditDistance(string userTyped, string fullEntry)
{
    if (userTyped.Length == 0) // all entries are assumed to be fully legit possibilities 
        return 0; // at this point, because the user hasn't typed anything.

    var inx = fullEntry.IndexOf(userTyped[0]);
    if (inx < 0) // If the 1st character doesn't exist anywhere in the entry, it's not
        return Int32.MaxValue; // a possible match.

    var lastInx = inx;
    var lastMatchCount = 0;
TryAgain:
    // Is there a better starting point?
    var len = fullEntry.Length - inx;
    var matchCount = 1;
    var k = 1;
    for (; k < len; k++)
    {
        if (k == userTyped.Length || userTyped[k] != fullEntry[k + inx])
        {
            if (matchCount > lastMatchCount)
            {
                lastMatchCount = matchCount;
                lastInx = inx;
            }
            inx = fullEntry.IndexOf(userTyped[0], inx + 1);
            matchCount = 0;
            if (inx > 0)
                goto TryAgain;
            else
                break;
        }
        else
            matchCount++;
    }
    if (k == len && matchCount > lastMatchCount)
        lastInx = inx;

    if (lastInx > 0)
        fullEntry = fullEntry.Substring(lastInx); // Jump to 1st character match, ignoring previous values 

    // The start of the Levenshtein Distance algorithem.
    var m = userTyped.Length;
    var n = Math.Min(m, fullEntry.Length);

    int[,] d = new int[m + 1, n + 1]; // "distance" - meaning number of operations.

    for (var i = 0; i <= m; i++)
        d[i, 0] = i; // the distance of any first string to an empty second string
    for (var j = 0; j <= n; j++)
        d[0, j] = j; // the distance of any second string to an empty first string

    for (var j = 1; j <= n; j++)
        for (var i = 1; i <= m; i++)
            if (userTyped[i - 1] == fullEntry[j - 1])
                d[i, j] = d[i - 1, j - 1];       // no operation required
            else
                d[i, j] = Math.Min
                           (
                             d[i - 1, j] + 1,  // a deletion
                             Math.Min(
                             d[i, j - 1] + 1,  // an insertion
                             d[i - 1, j - 1] + 1 // a substitution
                             )
                           );

    return d[m, n];
}

If you are looking for an overall design for the problem, try reading the content at https://www.interviewbit.com/problems/search-typeahead/.

They start by building autocomplete through a naive approach of using a trie and then build upon it. They also explain optimization techniques like sampling and offline updates to cater to specific use cases.

To keep the solution scalable, you would have to shard your trie data intelligently.


I think that one might be better off constructing a specialized trie, rather than pursuing a completely different data structure.

I could see that functionality manifested in a trie in which each leaf had a field that reflected the frequency of searches of its corresponding word.

The search query method would display the descendant leaf nodes with the largest values calculated from multiplying the distance to each descendant leaf node by the search frequency associated with each descendant leaf node.

The data structure (and consequently the algorithm) Google uses are probably vastly more complicated, potentially taking into a large number of other factors, such as search frequencies from your own specific account (and time of day... and weather... season... and lunar phase... and... ). However, I believe that the basic trie data structure can be expanded to any kind of specialized search preference by including additional fields to each of the nodes and using those fields in the search query method.


Need Your Help

WPF Datepicker to disable user input

wpf datepicker

I have a datepicker, but it is allowing me to enter any text. I want to disable user from entering text. User should be allowed to select date from the calendar.

ggplot2: Changing the layout of the legend

r ggplot2 legend

Right now, the legend by default looks something like this: