Redisでオートコンプリート (2)ZRANGEで範囲指定

Redisを使ったいろいろな autocomplete のアルゴリズムをメモ。

1. 前方一致
2. zrange 範囲指定
3. @antirez
4. trie
5. inverted index

zrangeで範囲指定

アルゴリズムをシンプルにするために、サジェスト対象の文字列は小文字のアルファベットのみで構成された1語とする。

a で検索した場合、オートコンプリート対象は a, aa, …, az, az… といった a で始まる語。
ASCII 文字表で小文字のアルファベットを眺めると

`abcdefghijklmnopqrstuvwxyz{

と並んでいることに着目すると、ASCII でソートすれば

a の1文字前 = ` < 候補の語 < a{

となる。
b で検索した場合は

b の1文字前 = a < 候補の語 < b{

となる。

このアイデアを使い、候補となる語は辞書順で登録し、検索時には、不等号の両端の語を追加し、間に挟まれた語をサジェスト候補にすると autocomplete ができあがる。

キーの追加

データ型は Sorted Set を利用。

候補となるキーを ZADD で追加する。

> zadd key 0 bar
(integer) 1
> zadd key 0 foo
(integer) 1
> zadd key 0 baz
(integer) 1
> zrange key 0 -1
1) "bar"
2) "baz"
3) "foo"

Redis の Sorted Set はスコアが同じ場合、辞書順にソートされる。

サジェスト

ba で検索されたとして、不等号の両端の語を追加する。

> zadd key 0 b`
(integer) 1
> zadd key 0 ba}
(integer) 1
> zrange key 0 -1
1) "b`"
2) "bar"
3) "baz"
4) "ba}"
5) "foo"

範囲取得用に追加した語の位置を ZRANK で取得

> zrank key  b`
(integer) 0
> zrank key  ba}
(integer) 3

あとは ZRANGE で不等号に挟まれたサジェスト候補を取得

> zrange key 1 2
1) "bar"
2) "baz"

※ 開始インデックス1 = “b`” の位置 + 1, 終了インデックス2 = “ba}” の位置 -1

検索が終わったら、追加した語を削除

> zrem key b`
(integer) 1
> zrem key ba}
(integer) 1
> zrange key 0 -1
1) "bar"
2) "baz"
3) "foo"

References

• Josiah L. Carlson :”Redis In Action”, Manning Publications Co., 2013.
  § 6.1 Autocomplete