How do autocomplete suggestions work?

Question

For example, if you type something in upper-right google/yahoo search box in firefox there will be some kind 'suggested auto complete' sort of thing.

Another example is in youtube search box and Stackoverflow tags edit box just below this question preview. How do they work? What technology behind 'em?

Answer 1

What technology behind 'em?

In case you are wondering which data structure is being used underneath then its called "trie" and for using less space compared to tries you can use "DAFSA"

How do they work?

both are implemented as a tree, where each node of tree corresponds to one character in a string and the character which appears before is parent of character which appears later e.g. The strings "tap", "taps", "top", and "tops" stored in a Trie (left) and a DAFSA (right),so as you begin to type tap..the tree is traversed based on the characters typed and shows the suggestions based on some weight assigned to each word, weight may be assigned based on usage frequency of the word.

Looking up string in worst case is O(m) time where m is the length of string.

Image is being referenced from the wikipedia articel : DAFSA,trie

Answer 2

It's quite simple.

Client side:

1. Grab keystrokes in form field
2. On keystroke make an AJAX request to server
   1. If another keystroke is entered immediately, cancel current AJAX request as it is obsolete now
   2. Make a new AJAX requested with updated characters in form field
3. Show server response to client

Server side:

1. All words are already bucketed alphabetically
2. If client request comes in for "ove" find all words starting with ove, ordered by popularity
3. Return top matches to client