GIANT ROBOTS SMASHING INTO OTHER GIANT ROBOTS

Written by thoughtbot

Redis Partial Word Match -- You (Auto)complete Me

Redis autocomplete

We can use partial word matching to rapidly search strings of text such as Names, Cities, States, etc.

We can do this by indexing strings into Redis sets based on partial matches of the string. The indexing process takes a string and breaks it into left-bound substrings which are placed into the appropriate Redis sets.

Partial word matching movie titles

In this example we’ll enable partial word matching queries of movie titles.

The movie titles will be stored in plain text. The keys are simple key-value pairs that are stored with the key structure movies:id, where id is incremented:

$ redis-cli get movies:1
"Bad Santa"
$ redis-cli get movies:2
"Batman"
$ redis-cli get movies:3
"Bad Company"

The movie Batman would be decomposed into the following sets (assuming that the indexing started at two characters):

ba
bat
batm
batma
batman

We’ll index the movie titles into sets based on partial match of their titles. To prevent any key collisions in Redis we’ll create keys with the following structue index:abc:movies.

View the indexed ids using Redis smembers command:

$ redis-cli smembers index:ba:movies
1) "1"
2) "2"
3) "3"

$ redis-cli smembers index:bat:movies
1) "2"

Note: The keys for the movie titles have been parameterized (lowercase and spaces replaced with dashes).

We’ll use a Ruby class Autocomplete to wrap the Redis calls:

# autocomplete.rb
require 'redis'

class Autocomplete
  def initialize(partial_word)
    @partial_word = partial_word
  end

  def movies
    redis.sort "index:#{partial_word}:movies", by: :nosort, get: 'movies:*'
  end

  private

  def redis
    Redis.current
  end

  attr_reader :partial_word
end

movies = Autocomplete.new('bat').movies

We’ll use the sort command with the by: :nosort parameter to query the partial word match index and return the matched movie names.

Related Reading

Redis Set Intersection - Using sets to filter data

Redis Pub/Sub…how does it work?