If you are implementing autocomplete feature, consider using a trie. In this post, I'll describe how to implement a trie in Redis. To be precise, a string trie. Redis is ideal for this purpose because it's fast, lightweight and is ideal for cache.

Now let's store some phrases in the trie:

Airline Baby Ban
Vitamin D Sources
Vitamin D Study
Blood Sugar

They are stored in a trie as shown below. Let's use trie as our root element.

To store this in Redis, we'll tokenize the search phrases and store each increasing sequence of tokens as a key. The next token in the sequence is stored as value. Let's use sorted sets to store values.

redis>ZADD trie 97 airline
redis>ZADD trie->airline 98 baby
redis>ZADD trie->airline->baby 98 ban
redis>ZADD trie 98 blood
redis>ZADD trie->blood 98 sugar
redis>ZADD trie 97 vitamin
redis>ZADD trie->vitamin 97 d
redis>ZADD trie->vitamin->d 97 sources
redis>ZADD trie->vitamin->d 97 study

Given a partial phrase, you can retrieve a subtree using one of the following commands

redis>ZRANGE "trie->vitamin->d" 0 -1
1) "study"
2) "sources"
redis>ZRANGEBYSCORE "trie->vitamin->d" -INF +INF
1) "sources"
2) "study"

Let's modify the trie a little bit. Let's use the frequency of a token as it's score. So instead of ZADD, we'll use ZINCRBY with a score of 1. ZINCRBY adds a token with score 1 if it's not found. Otherwise, the score is incremented by 1.

Here's a Node.js implementation of trie described above using Redis as data store. You can tweak it to make a more sophisticated trie.

/**
 * trie.js
 * A simple trie to suggest frequent phrases
 */
var redis = require('redis').createClient();

// Default constructor
var Trie = function(trieName) {
    this.root = 'trie';
    this.separator = '->';
};
exports.Trie = Trie;

// Stores a search phrase
Trie.prototype.addPhrase = function(phrase) {
    var key = this.root;
    var words = phrase.split(' ');
    for(var index in words) {
        var word = words[index].toLowerCase();
        this.addWord(word, key);
        key = (key + this.separator + word);
    }
};

// Stores a word as a child of given key
Trie.prototype.addWord = function(word, key) {
    var parent = key || this.root;
    // var score = word.charCodeAt(0);
    // redis.zadd(parent, score, word);
    redis.zincrby(parent, 1, word);
};

// Suggests a next word based on the input
Trie.prototype.suggest = function(phrase, callback) {
    var prefix = this.root + this.separator;
    var path = phrase.toLowerCase().split(' ').join(this.separator);
    var key = prefix + path;
    redis.zrevrangebyscore(key, '+inf', '-inf', callback);
};

// Disconnect from redis
Trie.prototype.end = function() {
    redis.quit();
};

It's used as follows.

/**
 * test.js
 * A simple trie to suggest frequent phrases
 */
var t = require("./trie");

var trie = new t.Trie();

trie.addPhrase('Emma Watson');
trie.addPhrase('Airline Baby Ban');
trie.addPhrase('Vitamin D Study');
trie.addPhrase('Vitamin D Sources');
trie.addPhrase('Vitamin D Sources');
trie.addPhrase('Vitamin D Sources');
trie.addPhrase('Blood Sugar');
trie.addPhrase('Bathroom Cleaning Tips');


trie.suggest('vitamin d', function(err, reply) {
    if(err) console.log(err);
    if(reply)  console.log(reply);
    trie.end();
});
$ node test.js
[ 'study', 'sources' ]