Redis autocomplete

Question

How can I implement an autocomplete using redis?

Say for example I have an array ["alfred","joel","jeff","addick"]. When I type a I get ["alfred", "addick"]

I hope you get the point. How can I implement this using redis commands efficiently(if possible but I think it is). It would be great if I could get some simple commands I can try out via telnet to mimic this behaviour.

Thanks

P.S: Merry x-mas to all of you :)

Answer 1

If you're dealing with a large data set, I would suggest considering implementing this as a trie. I have thrown together a small bit of Ruby that would do this:

    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.zset_add key, c.bytes.first, c
          key += c
        end
    
        @r.zset_add key, 0, TERMINAL
      end
    
      def add_words(*words)
        words.flatten.compact.each {|word| add_word word}
      end
    
      def suggest(text)
        @r.zset_range("#{@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)

For example:

    $ ruby RedisTrie.rb
    ["apple", "auto", "automobile", "axe", "carwash", "cranky", "five", "oil-change", "ruthie"]
    $ ruby RedisTrie.rb a
    ["apple", "auto", "automobile", "axe"]
    $ ruby RedisTrie.rb au
    ["auto", "automobile"]
    $ ruby RedisTrie.rb aux
    []

Read more on Tries at Wikipedia's entry on Tries.

You will definitely want to optimize your suggest method to not return ALL values, instead only returning the first X values it finds. It would defeat the purpose to iterate the entire data structure.

Answer 2

I also found this snippet when reading Simon Willison's impressive Redis tutorial.

Solution:

Hello Max,

KEYS is not the way to go, the best thing you can do is to use instead a sorted set. What you want is to turn the first 4 or 5 characters of the strings into an integer (you can imagine every char as a digit of a radix 256 number for instance, but there are better representation) and add all your usernames into a sorted set.

Then using ZRANGEBYSCORE you can get all the elements between a given range.

This method is much more scalable as it's an O(log(N)) thing.

I'm covering this stuff in my very slowly evolving Redis book...

Cheers, Salvatore