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

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

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


SQL の % 部分一致の KVS 版。


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"



Tagged with: ,
Posted in algorithm, database
3 comments on “Redisでオートコンプリート (1)前方一致

Leave a Reply

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

You are commenting using your 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

  • RT @__apf__: How to write a research paper: a guide for software engineers & practitioners.… /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:… It's about managing produc… 1 year ago
%d bloggers like this: