Redisでオートコンプリート (3)@antirezアルゴリズム

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

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

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

Advertisements
Tagged with: , ,
Posted in algorithm, database
2 comments on “Redisでオートコンプリート (3)@antirezアルゴリズム

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Archives
  • RT @__apf__: How to write a research paper: a guide for software engineers & practitioners. docs.google.com/presentation/d… /cc @inwyrd 4 months ago
  • RT @HayatoChiba: 昔、自然と対話しながら数学に打ち込んだら何かを悟れるのではと思いたち、専門書1つだけ持ってパワースポットで名高い奈良の山奥に1週間籠ったことがある。しかし泊まった民宿にドカベンが全巻揃っていたため、水島新司と対話しただけで1週間過ぎた。 それ… 4 months ago
  • RT @googlecloud: Ever wonder what underwater fiber optic internet cables look like? Look no further than this deep dive w/ @NatAndLo: https… 4 months ago
  • @ijin UTC+01:00 な時間帯で生活しています、、、 10 months ago
  • RT @mattcutts: Google's world-class Site Reliability Engineering team wrote a new book: amazon.com/Site-Reliabili… It's about managing produc… 1 year ago
%d bloggers like this: