Skip to content

Instantly share code, notes, and snippets.

@cwholt
Created February 17, 2012 16:39
Show Gist options
  • Star 13 You must be signed in to star a gist
  • Fork 5 You must be signed in to fork a gist
  • Save cwholt/1854283 to your computer and use it in GitHub Desktop.
Save cwholt/1854283 to your computer and use it in GitHub Desktop.
node.js + redis prefix trie (autocomplete)
module.exports = function(redisClient,prefix) {
var Autocomplete = {};
Autocomplete.prefix = prefix;
Autocomplete.terminal = "+";
Autocomplete.add = function(word, next) {
function add(letters, key, last, x) {
var letter = last ? Autocomplete.terminal : letters[x];
var score = last ? 0 : letter.charCodeAt(0);
redisClient.zadd(key, score, letter, function(reply) {
x++;
if (x < letters.length) {
add(letters, key+letter, false, x);
} else {
if (x == letters.length) {
add(letters, key+letter, true, x);
} else {
if (typeof(next) == "function") next();
}
}
})
}
var letters = word.split("");
var key = Autocomplete.prefix+letters[0];
add(letters, key, false, 1);
}
Autocomplete.suggest = function(query, limit, next) {
var more = 1;
var suggestions = [];
function suggest(query) {
var key = Autocomplete.prefix+query;
redisClient.zrange(key, 0, -1, function(err, reply) {
more--;
reply.forEach(function(c) {
if (c == Autocomplete.terminal) {
suggestions.push(query);
} else {
if (suggestions.length < limit) {
more++;
suggest(query + c);
}
}
})
if (more <= 0) next(suggestions);
})
}
suggest(query);
}
return Autocomplete;
}
// create redis client
var redisClient = require('redis').createClient();
// tries will be stored under the "trie:" prefix.
var prefix = "trie:";
// load Autocomplete, pass along redisClient and prefix.
var Autocomplete = require('./Autocomplete')(redisClient,prefix);
// add a word.
Autocomplete.add("word", function() {
// suggest words that start with "wo", limit to 2 responses.
Autocomplete.suggest("wo", 2, function(words) {
// log
console.log(words)
// exits.
process.exit(0)
})
})
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment