Redisでオートコンプリート (1)前方一致

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

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

前方一致

まずは一番シンプルな実装。
SQL の % 部分一致の KVS 版。

サジェスト時には、全キーを取得し(LRANGE)、検索文字列と前方一致するキーを候補として返す。

LRANGE の計算量は O(StartOffset+NumberOfElement) のため、キーが増えるとスケールしない。

キーの追加

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

> lpush key foo
(integer) 1
> lpush key bar
(integer) 2
> lpush key baz
(integer) 3

サジェスト

LRANGE key 0 -1 で全キーを取得する。

> lrange key 0 -1
1) "baz"
2) "bar"
3) "foo"

あとは、各キーが検索文字列と前方一致するかチェックし、一致すればサジェスト候補で返す。

References

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