読者です 読者をやめる 読者になる 読者になる

Wavelet TreeのTop-Kの改善

NLP

Wavelet Treeは強力なデータ構造ですが、ひとつどうしても気になる点があります。それは、Top-Kの列挙です。文字列本で紹介されているGreedyな方法は、結果がK件しか必要ないにもかかわらず、計算時間がけっこうかかります。他の操作は、最悪値の計算量が小さく、安心して使えるのに対して、Top-Kだけは、少し注意する必要があります。そのことは、文字列本にも書いてあって、最悪計算量も明示してあります。

その最悪計算量ですが、要素間の頻度に大きな偏りがある場合は、無断な節点を調べずに済み、計算量はO(klogσ)に近づくとあります。つまり、ある区間内の数値に偏りがあると、問題ないということです。

1 2 3 4 2 3 4 3 4 4

上記のような場合だと、Top-1のクエリを発行すると、O(logσ)です。頻度に偏りがあると、Wavelet Treeの上段での見積もりがうまく機能するので、無駄な節点を調べる必要がなくなるからです。

ただし、それぞれの数値がまんべんなく出現する場合は、上段での見積もりがうまく機能しません。

1 2 3 4 1 2 3 4

上記の場合は、上段での見積もりは、どの節点も同じなので、結局、一番下の段まで調べないとTop-1を決定できません。

こんなケースはレアだということで済ますこともできるんですが、実運用を考えると少し不安です。例えば、英語の文書で、ある程度の文書数で、ある程度同じ長さの場合、「The」の出現頻度が高い順にTop-K文書を表示するとやっかいなわけです。
(もちろん、すべての文書で、「The」の出現頻度が同じということはないですが、ある程度の文書数があると、上段の見積もりはほとんど意味がなく、無駄な節点の計算が必要になります。)

その点を考慮に入れて、Wavelet TreeのTop-Kの性能を改善したNavarro神の論文が以下です。

Space-Efficient Top-k Document Retrieval
Gonzalo Navarro, SEA'12, 2012.

http://www.dcc.uchile.cl/~gnavarro/ps/sea12.2.pdf

この論文を理解するためには、Suffix Treeを利用してTop-Kを取得する方法を理解しなければならない。それについては、以下の岡野原さんのブログに詳しく書いてある。

http://hillbig.cocolog-nifty.com/do/2010/02/top-k-f0d9.html

基本的な概念は、非常に丁寧に説明されているので、上記を読めば理解できると思います。
(もちろん、私も何回も読んでようやく理解しました。)

読んでから気づいたんですが、私は、Suffix Arrayから興味を持ったので、Suffix Treeについては、あまり理解していなかったなということです。なので、今は、「Algorithms on Strings」を読んで、Suffix Treeに対する理解を深めています。

さて、Suffix TreeをTop-K用の補助的データ構造に使うんですが、岡野原さんのブログで紹介されている方法は、厳密な方法なので、サイズが大きいです。なので、情報を減らして、サイズを削減します。やり方は簡単で、Suffix Treeの葉を一定間隔でサンプリングし、それぞれのLCAを求めます。そのLCAに、サンプリングした区間のTop-Kを事前計算して付与しておきます。そして、Suffix Treeの木構造は、LOUDSで表現しておきます(いわゆるパトリシアトライに近いものです)。実際は、各区間のLCAのノードがわかれば良いので、すべての木構造を再現する必要はないと思います。

このTop-K用に特化しつつサイズを抑えたSuffix TreeをSSGST(Succinct Sparsied Generalized Suffix Tree)と呼びます。さて、理解しやすい図が欲しいところだと思いますので、以下のスライドを紹介しておきます。

http://www.cikm2012.org/keynote/Keynote_Jeffrey_S_Vitter.pdf

p.27~40まで見ればイメージできると思います。ちなみに、一般化接尾辞木というのは、複数の文書を対象に作ったSuffix Treeをそう呼んでいるようです。

ようやく本題ですが、このSSGSTを使って、なぜ、Wavelet TreeのTop-K操作が改善されるかということですが、それは、「無駄な節点の計算をしないようにする」ということです。つまり、計算が不要な節点がWavelet Treeの上段でわかれば、早めに打ち切れるので、性能がアップするわけです。

さて、どうやってTop-Kに活かすかということですが、例えば、FM-Indexで検索した結果として、[sp, ep]が得られたとします。そして、あるLCAで事前計算された範囲が、[lsp, lep]とします。そのとき、以下のような関係になっているとします。

sp --- lsp --- lep --- ep 

このlspとlepの区間のTop-K件は事前計算によりわかっています。なので、問題は、[sp, lsp]と[lep, ep]の区間です。[lsp, lep]の区間にあるTop-K件は、[sp, ep]を考慮すると内容が入れ替わる可能性があります。つまり、重要なのは、[sp, lsp]と[lep, ep]を考慮すると[lsp, lep]のTop-K件の内容が入れ替わるかということです。

上記のことを考慮して、Wavelet Treeに対して、[sp, ep]の区間のTop-K操作を行います。ただし、[sp, lsp]か[lep, ep]の範囲の数値が含まれている節点だけを計算対象とします。これにより、[sp, lsp]か[lep, ep]の数値が含まれていない節点を展開しなくてよくなりますし、事前計算されたTop-Kの中で最も頻度が低いものよりも数が少ない節点に到達した時点で探索を打ち切ることもできます。

多くの場合、高速化されるようです。

ただ、最近は、さらに良いデータ構造が提案されていて、以下は、SSGSTを使ったものより数十倍も高速になるようです。

Faster Compact Top-k Document Retrieval
Gonzalo Navarro, DCC'13, 2013.

http://www.dcc.uchile.cl/~gnavarro/ps/dcc13.1.pdf

Table1がわかりやすいと思います。こちらは、まだ読んでいないので、読んでみようと思います。