Redisを使ったいろいろな autocomplete のアルゴリズムをメモ。
3つ目は Redis 作者の @antirez が 2010年のブログに書いていたアルゴリズム。
http://oldblog.antirez.com/post/autocomplete-with-redis.html
↑の URL に詳しく書かれているので、飛んで実際に読んだほうが理解ははやいと思われる。
キーの追加
キーの登録時に foo
であれば
f fo foo foo*
というように先頭から1文字ずつ登録する。また、語の切れ目がわかるように、終端文字 *
をつけた "foo*"
も登録する。
データ型は Sorted Set を利用。
候補となるキーを ZADD
で追加する。
> zadd key 0 b (integer) 1 > zadd key 0 ba (integer) 1 > zadd key 0 bar (integer) 1 > zadd key 0 bar* (integer) 1 > zadd key 0 b (integer) 0 > zadd key 0 ba (integer) 0 > zadd key 0 baz (integer) 1 > zadd key 0 baz* (integer) 1 ... > zrange key 0 -1 1) "b" 2) "ba" 3) "bar" 4) "bar*" 5) "baz" 6) "baz*" 7) "f" 8) "fo" 9) "foo" 10) "foo*"
#2 の時と同じく Redis の Sorted Set はスコアが同じ場合、辞書順にソートされる。
サジェスト
- fo で検索されれば
- fo の Sorted Set での位置を探し
- fo 以降の文字列を順に走査し、”*”で終わる語を探す。
- fo で前方一致しなくなれば、処理を終える。
アイデアとしては、1つ目の前方一致と2つ目の ZRANGE
を組み合わせている。(発表の時系列的には#2 より #3 のほうが先)
ba
で検索されたとして、まずは ba
の位置を ZRANK
で探す
> zrank key ba (integer) 1
あとは、ZRANGE
で ba
以降にあるサジェスト候補を取得
> zrange key 1 4 1) "ba" 2) "bar" 3) "bar*" 4) "baz" > zrange key 5 8 1) "baz*" 2) "f" 3) "fo" 4) "foo" >
*
で終わる語があれば、候補として返す。
ZRANGE
の終わりの index を -1 とすると、開始インデックス以降のすべてのキーを返してしまうので、検索語の ba と先頭一致しなくなるまで開始・終了のインデックスを増やしながら、キーを走査する。
References
- Salvatore Sanfilippo : Auto Complete with Redis
http://oldblog.antirez.com/post/autocomplete-with-redis.html
2 thoughts on “Redisでオートコンプリート (3)@antirezアルゴリズム”