Redisでオートコンプリート(4)Trie

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

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

trie(トライ木)

3つ目の @antirez アルゴリズムでは、登録後 bar に対して b, ba, bar というように各部分文字列だけをキーとして保存した。
これを拡張して、 b の次は a, ba の次は r というように接頭する文字列とその次に来る文字の対応関係を木構造で持つと、トライ木(trie)というデータ構造になる。

Trie_example

登録語が inn の場合

  • root -> i
  • i -> n
  • in -> n
  • inn -> + # 終端文字

というようになる。

検索の場合も同じようにルートから辿り、検索文字列を接頭語としてもつノードより下のノードを、終端文字にたどり着くまで辿る。

キーの追加

wikipedia の例を題材にする。

データ型は再び Sorted Set を利用。

候補となるキー(下の例では “tea” と “ten”)を ZADD で追加する。

> zadd trie: 0 t
(integer) 0
> zadd trie:t 0 o
(integer) 0
> zadd trie:to 0 +
(integer) 0
> zadd trie:t 0 e
(integer) 0
> zadd trie:te 0 a
(integer) 0
> zadd trie:tea 0 +
(integer) 0
> zadd trie:te 0 n
(integer) 0
> zadd trie:ten 0 +
...

サジェスト

te で検索された場合、root -> t -> te とノードを辿り、このノードを起点に終端文字「+」が見つかるまでノードを辿る。

> zrange trie: 0 -1
1) "t"
2) "a"
3) "i"
> zrange trie:t 0 -1
1) "e"
2) "o"
> zrange trie:te 0 -1
1) "a"
2) "n"
3) "d"
> zrange trie:tea 0 -1
1) "+"
> zrange trie:ted 0 -1
1) "+"
> zrange trie:ten 0 -1
1) "+"

以上から tea と ted と ten の3つが候補になる。

trie を使うと、サジェストする語をエレガントに retrieve できる。

References

Tagged with: , ,
Posted in algorithm, database
4 comments on “Redisでオートコンプリート(4)Trie

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 1 week ago
  • RT @HayatoChiba: 昔、自然と対話しながら数学に打ち込んだら何かを悟れるのではと思いたち、専門書1つだけ持ってパワースポットで名高い奈良の山奥に1週間籠ったことがある。しかし泊まった民宿にドカベンが全巻揃っていたため、水島新司と対話しただけで1週間過ぎた。 それ… 3 weeks ago
  • RT @googlecloud: Ever wonder what underwater fiber optic internet cables look like? Look no further than this deep dive w/ @NatAndLo: https… 3 weeks ago
  • @ijin UTC+01:00 な時間帯で生活しています、、、 6 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… 9 months ago
%d bloggers like this: