Skip to content

Instantly share code, notes, and snippets.

@quiver
Created March 28, 2013 16:18
Show Gist options
  • Save quiver/5264557 to your computer and use it in GitHub Desktop.
Save quiver/5264557 to your computer and use it in GitHub Desktop.
Redis+trie auto complete Ruby program is a copy from http://stackoverflow.com/questions/1958005/redis-autocomplete, authored by Alex. http://en.wikipedia.org/wiki/Trie
require 'rubygems'
require 'redis'
class RedisTrie
TERMINAL = '+'
def initialize(prefix)
@prefix = prefix
@r = Redis.new
end
def add_word(word)
w = word.gsub(/[^a-zA-Z0-9_-]/, '')
key = "#{@prefix}:"
w.each_char do |c|
@r.zadd key, c.bytes.first, c
key += c
end
@r.zadd key, 0, TERMINAL
end
def add_words(*words)
words.flatten.compact.each {|word| add_word word}
end
def suggest(text)
@r.zrange("#{@prefix}:#{text}", 0, -1).map do |c|
(c == TERMINAL) ? text : suggest(text + c)
end.flatten
end
end
rt = RedisTrie.new('trie')
rt.add_words %w( apple automobile carwash oil-change cranky five ruthie axe auto )
p rt.suggest(ARGV.shift.to_s)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment