Redisでオートコンプリート(5) 転置インデックス

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

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

これまでの実装例は、検索語が一語に限られている。
RubyGem の soulmate は転置インデックスを用いて、複数語の autocomplete に対応している。

今は実装が変わっているかもしれないけれども、転置インデックスを使った2011年11月当時の実装が次のブログにまとめられているので、これをベースにメモ

http://patshaughnessy.net/2011/11/29/two-ways-of-using-redis-to-build-a-nosql-autocomplete-search-index

転置インデックス

T[0] = “it is what it is”
T[1] = “what is it”
T[2] = “it is a banana”

というような3つのテキストがあり、上から順に 0, 1, 2 と ID が付けられているとする。

各テキストを単語で分割し、各語とテキストの対応関係を {単語 : テキストIDの集合} のペアで持つ。
上の例であれば、

"a":      {2}
"banana": {2}
"is":     {0, 1, 2}
"it":     {0, 1, 2}
"what":   {0, 1}

となる。

このマッピングがあると “is” を含んだテキストは {0, 1, 2} とわかる。
“is” と “banana” の両方を含んだテキストを探したければ、”is” に対応するテキストの集合と “banana” に対応する集合の積を取って {0, 1, 2] ∩ {2} = {2} とわかる。

※例は wikipedia から

部分文字列の前方一致と組み合わせる

上の例では、単語をまるっとキーにして転置インデックスを作った。
単語を @antirez アルゴリズムと同じく w, wh, wha, what というように先頭からの部分文字列に分割し、各部分文字列に対して 部分文字列 => {テキストIDの集合} の転置インデックスを作成する。

検索されたときは、各検索語を転置インデックスに問い合わせてテキストIDの集合を取得。
各検索語に対するテキストIDの集合の積をとると、検索語をすべて含むテキストIDの集合を取得できる。

キーの追加

“a hard day’s night” を登録したい場合、まずは INCR でテキストID を取得する。

> incr beatles:sequence
(integer) 1

取得したテキストIDを利用してテキストを登録。データ型は Hash を利用。

> hmset beatles:songs:1 id 1 text "a hard day's night"
OK

登録語を分割し、部分文字列とテキストIDのマッピングを登録する。データ型は Set を利用。

> sadd beatles:term:a 1
(integer) 1
> sadd beatles:term:h 1
(integer) 1
> sadd beatles:term:ha 1
(integer) 1
> sadd beatles:term:har 1
(integer) 1
> sadd beatles:term:hard 1
(integer) 1
...

サジェスト

“lik” と “too” の2語で検索したとする。

まずは、”lik” で転置インデックスに問い合わせる。

> smembers beatles:term:lik
1) "155"
2) "296"

“lik” を含むテキスト ID の集合がかえってくる。

次に “too” で転置インデックスに問い合わせる。

> smembers beatles:term:too
1) "140"
2) "270"
3) "296"

“lik” と “too” の両方にマッチするテキスト ID はこの2つの集合の INTERSECT。 SINTER コマンドで積を求める。

> sinter beatles:term:too beatles:term:lik
1) "296"

最後にテキスト ID からテキストを確認

> "HGET" "beatles:songs:296" "title"
"you like me too much"

確かにテキスト ID:296 は “too” と “lik” を含んでいる。

以上のようにして、複数の検索語でも autocomplete できるようになる。転置インデックをカジュアルにつかえて気分が良い。

References

• Two ways of using Redis to build a NoSQL autocomplete search index
• Josiah L. Carlson :”Redis In Action”, Manning Publications Co., 2013.
  § 7.1 Searching in Redis(Redis を使った Inverted Index 実装。データ型は Set ではなく Sorted Set を利用。)