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

Redisを使ったいろいろな autocomplete のアルゴリズムをメモ。 前方一致 zrange 範囲指定 @antirez trie 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の集合} のペアで持つ。 上の例であれば、 となる。 このマッピングがあると “is” を含んだテキストは