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

redisRedisを使ったいろいろな 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

Advertisements
Tagged with:
Posted in algorithm, database
4 comments on “Redisでオートコンプリート (2)ZRANGEで範囲指定

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週間過ぎた。 それ… 5 months ago
  • RT @googlecloud: Ever wonder what underwater fiber optic internet cables look like? Look no further than this deep dive w/ @NatAndLo: https… 5 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: