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” を含んだテキストは

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

Redisを使ったいろいろな autocomplete のアルゴリズムをメモ。 前方一致 zrange 範囲指定 @antirez trie inverted index trie(トライ木) 3つ目の @antirez アルゴリズムでは、登録後 bar に対して b, ba, bar というように各部分文字列だけをキーとして保存した。 これを拡張して、 b の次は a, ba の次は r というように接頭する文字列とその次に来る文字の対応関係を木構造で持つと、トライ木(trie)というデータ構造になる。 登録語が inn の場合 root -> i i -> n in -> n inn -> + # 終端文字 というようになる。 検索の場合も同じようにルートから辿り、検索文字列を接頭語としてもつノードより下のノードを、終端文字にたどり着くまで辿る。 キーの追加 wikipedia の例を題材にする。 データ型は再び Sorted Set を利用。 候補となるキー(下の例では

Redisでオートコンプリート (3)@antirezアルゴリズム

Redisを使ったいろいろな autocomplete のアルゴリズムをメモ。 前方一致 zrange 範囲指定 @antirez trie inverted index 3つ目は Redis 作者の @antirez が 2010年のブログに書いていたアルゴリズム。 http://oldblog.antirez.com/post/autocomplete-with-redis.html ↑の URL に詳しく書かれているので、飛んで実際に読んだほうが理解ははやいと思われる。 キーの追加 キーの登録時に foo であれば というように先頭から1文字ずつ登録する。また、語の切れ目がわかるように、終端文字 * をつけた “foo*” も登録する。 データ型は Sorted Set を利用。 候補となるキーを ZADD で追加する。 #2 の時と同じく Redis の Sorted Set はスコアが同じ場合、辞書順にソートされる。 サジェスト fo で検索されれば fo の Sorted Set での位置を探し fo 以降の文字列を順に走査し、”*”で終わる語を探す。 fo で前方一致しなくなれば、処理を終える。

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

Redisを使ったいろいろな autocomplete のアルゴリズムをメモ。 前方一致 zrange 範囲指定 @antirez trie inverted index zrangeで範囲指定 アルゴリズムをシンプルにするために、サジェスト対象の文字列は小文字のアルファベットのみで構成された1語とする。 a で検索した場合、オートコンプリート対象は a, aa, …, az, az… といった a で始まる語。 ASCII 文字表で小文字のアルファベットを眺めると `abcdefghijklmnopqrstuvwxyz{ と並んでいることに着目すると、ASCII でソートすれば a の1文字前 = ` < 候補の語 < a{ となる。 b で検索した場合は b の1文字前 = a < 候補の語 < b{ となる。 このアイデアを使い、候補となる語は辞書順で登録し、検索時には、不等号の両端の語を追加し、間に挟まれた語をサジェスト候補にすると autocomplete ができあがる。 キーの追加 データ型は Sorted Set を利用。

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

Redisを使ったいろいろな autocomplete のアルゴリズムをメモ。 前方一致 zrange 範囲指定 @antirez trie inverted index 前方一致 まずは一番シンプルな実装。 SQL の % 部分一致の KVS 版。 サジェスト時には、全キーを取得し(LRANGE)、検索文字列と前方一致するキーを候補として返す。 LRANGE の計算量は O(StartOffset+NumberOfElement) のため、キーが増えるとスケールしない。 キーの追加 候補となるキーを LPUSH で追加する。 サジェスト LRANGE key 0 -1 で全キーを取得する。 あとは、各キーが検索文字列と前方一致するかチェックし、一致すればサジェスト候補で返す。 References Josiah L. Carlson : “Redis In Action”, Manning Publications Co., 2013. § 6.1 Autocomplete