autocomplete.rb

require 'redis'

# Search query autocompletion based on http://oldblog.antirez.com/post/autocomplete-with-redis.html
class Autocomplete
  # Expire the completion database for a scope after 30 days with no new data.
  TTL = 60 * 60 * 24 * 30

  def initialize(redis = Redis.new)
    @redis = redis
  end

  def index(term, scope: [])
    key = key_for(scope)
    term = clean(term)

    1.upto(term.length) do |l|
      prefix = term[0...l]
      @redis.zadd(key, 0, prefix)
    end

    @redis.zadd(key, 0, term + "*")

    # Automatically expire keys that are no longer updated.
    @redis.expire(key, TTL)
  end

  def complete(prefix, scope: [], max_results: 50)
    key = key_for(scope)
    prefix = clean(prefix)
    results = []
    rangelen = 50 # This is not random, try to get replies < MTU size
    start = @redis.zrank(key, prefix)
    count = max_results

    return [] if !start

    while results.length != count
      range = @redis.zrange(key, start, start + rangelen - 1)
      start += rangelen

      break if !range || range.empty?

      range.each do |entry|
        minlen = [entry.length, prefix.length].min

        if entry[0...minlen] != prefix[0...minlen]
          count = results.count
          break
        end

        if entry[-1..-1] == "*" && results.length != count
          results << entry[0...-1]
        end
      end
    end

    results
  end

  private

  def key_for(scope)
    (scope + ["compl"]).join(":")
  end

  def clean(term)
    term
      .downcase
      .gsub(/\W+/, " ")
      .strip
  end
end