最近のSuffix Arrayによる全文検索について調べてみた

ちょっと興味があったので調べてみた。
全文検索には主に転置インデックス(Inverted Index)によるものと接尾辞配列(Suffix Array)/接尾辞木(Suffix Tree)によるものがある。
前者は効率的にデータを扱えるものの、キーワード単位でしかインデックスを付けられないので形態素解析するなどして検索対象のテキストからキーワードを取り出す必要がある。
後者は任意のクエリにマッチすることができるもののデータサイズが大きくなりがちであることと検索結果となる文書にスコア付けができないなどの問題がある。
最近ではSuffix Array/Treeによる全文検索に対して簡潔データ構造(Succinct Data Structure)を導入してデータサイズを小さくしたり、スコアをもたせる方法が提案されたりと何かと話題が多い。


Suffix Array/Treeが持つ文書検索の機能は、クエリにマッチした文書を列挙するというものでDocument Listingと呼ばれる。この操作はクエリ長をp、検索対象となる文書全体での出現回数をoccとするとO(p+occ)の時間がかかる。これはクエリが一般的な単語で文書中頻出する場合にはとても効率が悪い。


Muthukrishnanの方法
MuthukrishnanはDocument Listingにかかる時間をO(p+ndoc)に改善する方法を提案した。ndocはクエリにマッチした文書数。つまり一つの文書にクエリが100回出現する場合に、それまでは100回同じ文書にマッチしていたのが一回で済むようになった。
またMuthukrishnanはDocument Listingに加えてk-mine、k-repeatsという操作もO(p+ndoc)ができるようにした。k-mineはk回クエリとなる単語が含まれる文書のみを検索する。k-repeatsはクエリ同士の距離がk以内の文書のみを検索する。これによって自由なスコアではないもののある程度絞り込んだ文書検索が可能となった。

S. Muthukrishnan


Sadakaneの方法
Sadakaneは簡潔データ構造を用いることでデータサイズを小さくした。

K. Sadakane


Hon, Shah, Vitterの方法
Hon, Shah, Vitterはscore(P,d)という形式の任意のスコアを文書が持てるようにした。Pはパターン、dは文書。これによってk-mine,k-repeatsを統一的に扱えるようになった他、PageRankのような文書そのものがもつスコア、Tfidfのような情報検索で一般的に用いられるスコアが利用可能になった。
またtop-kクエリというスコアが上位の文書k件だけをO(p+klogk)で取得する方法を提案している。これはクエリが一般的な語でマッチする文書は非常に多いが実際はスコアの高い数件だけ結果を取れれば良い、という場合に非常に有効となる。
この論文は具体例が少なく理解が難しいが、ALSIP2011での岡野原氏の招待講演資料(http://research.preferred.jp/2011/12/sds_for_document_collection/)に具体例が図を用いて説明されているのであわせて読むと非常に理解しやすい。

Wing-Kai Hon, Rahul Shah & Jeffrey Scott Vitter


Navarro, Nekrichの方法
Navarro, Nekrichはtop-kクエリをO(p+k)で実行できるように改良した。この論文はsparseFFTで話題となったSODA2012のもので多分この手の話題では最新。FFTもいいけどこちらも注目したい。

Gonzalo Navarro & Yakov Nekrich