Top-k文書列挙問題

いろいろとありまして去年読んだ論文で面白かったものランキングとか書けなかったのが残念ですが、もしあげるとしたら次の論文は入れると思います（知ったのは年明けだったけど）。

"Space-Efficient Framework for Top-k String Retrieval Problems", FOCS 2009, Wing Kai Hon, Rahul Shah and Jeffrey Scott Vitter (pdf)

扱っているのは次のような問題です（説明のため本来のと言い換えています）

n個の葉からなる木が入力として与えられ，各葉には色（1以上d以下の整数とします）が与えられています．
この時、木中の任意の節点と正整数kがクエリとして与えられたときに、その節点の子孫の中で出現回数が大きい色を順にk個答えよという問題です。

簡単に思いつくのは，各節点に適当な個数(d)の答えをあらかじめ前計算したものを持っておくというアプローチですが、この場合保存に必要なスペースは
節点数がO(n)のため、O(nd)bitsとなる上、d < kの場合は途端に計算量が爆発します．

この問題は全文検索と非常に強い関係があります．検索対象D個の文書に対し接尾辞木や接尾辞配列で索引を作る場合、それらをつなげた長さnの入力文を作成します。
次に、それに対する接尾辞木（一般接尾辞木）を構築します。検索のときは普通の接尾辞木のよう検索を行い、ヒット位置集合を求めた後に、それらの位置が元々どの文書に所属していたかを求めます．
ヒット件数を求めるのはO(|q|)と高速に行うことができるのに対し、ヒット文書集合、ヒット文書数を求めるのはヒット位置数がoccの時、O(occ log D)時間かかってしまいます。
各位置に対してそれがもともとどの文書に対応していたかを調べるにはO(log D)時間かかるため。
ヒット位置数が数億などで、それらの中からクエリに特に関係する数十程度の文書を求めるのに非常に大きな時間がかかってしまいます。

これに対する解法はいくつか提案されていますが補助データ構造のサイズが非常に大きいなどの問題がありました

論文では、この問題をO(k log k + dep)時間で正確な結果を求めることができ、O(n log n)bitsで保存可能なデータ構造を提案しています。depは節点の深さです。
これはかなりまじめにやった場合で、ヒット位置数が大きい場合節点に対して保存することにより、データ構造のサイズはいくらでも小さくなりえて、結構現実的です。

まず、木中の節点（葉も子の数が０の節点とする）に対し行きがけ順（preorder）で番号をつけておきます。これは深さ優先探索をして、辿った順です。
この番号のつけ方だと、ある節点以下の部分木は全て連番になっているという特徴があります。

次に、各節点において(親へのポインタ:p 色:c）エントリの配列からなるN-structureというデータ構造を考えます。
まず、各葉では、自分の色からなるエントリのみをN-structureに保存します。
次に各内部節点では、二つ以上の子が色cの葉を子孫として持つ場合、色cのエントリを持つとします。そして色cのエントリ中のpは、同じ色cのエントリを保持する最も近い祖先の節点番号とします。
もし、そのような親が無い場合は-1をpとして記録しておきます。

先ほどの定義より、ある節点において、同じ親へのポインタを含むエントリを複数持つ場合はあります、が同じ文書番号を含むエントリは高々一つしか存在しません。

図では葉に色（a,b,cの文字ですが）がacbaaccbcとつけられている場合の例を示します
図中の青色の箱がN-structureの例です。例えば番号2の節点(-1, a), (1, c), (-1, b)の三つのエントリからなるN-structureが保存されています。番号3の節点のように一つもエントリが無い節点も存在します。

このとき全エントリの総数は高々2n個です。なぜなら、それぞれ葉の数がn個で子二つが持っている場合のみ内部節点にはエントリが存在するからです。

次に、N-structureの逆向きのI-structureというのを考えます。これは（子へのポインタ：p 色:c 頻度:f）を保存した配列です。例えば節点tにおいて(p, c)というエントリがN-structureに存在する場合、
節点pに(t, c, f)というエントリが存在します。fは節点tの子孫中の色cの個数です。
I-structure中では、エントリは子へのポインタの番号順にソートしておくことにします。頻度：fは対応する子でその色が何回出現しているかを記録したものです。
図のオレンジ色の箱がI-structureの例です。

このI-structureのエントリの総数もN-structureと一対一対応があるので高々2n個です。
検索時に保存するのはI-structureのみです。

では、これを利用して先ほどの問題を解いてみましょう。

クエリとして節点tと正整数kが与えられ、t以下の色で頻度が高い順にk個報告するのが目標です。

まず、t以下の節点、葉は行きがけ順で番号をつけたことから連続する番号がつけられています。これを[t, t']としましょう（t'はt中の最右の葉）

次にtの親から根方向に向かう各節点のI-structureにおいて、[t, t']内の値を子へのポインタとして持っている範囲を見つけます(*)。I-structureはポインタの番号順にソートされているので、この範囲は連続した区間に存在し
二分探索でその範囲を求めることができます。例えば、図の例でクエリで節点3が与えられた時 [t, t']=(3, 6)なので、節点2においては(4:a 1) (5:c 1) (6:b 1)が該当する範囲であり、節点1, -1ではこの範囲に該当するエントリは
ありません。

この範囲の集合に対し次の事実があります。

事実：tを根とする部分木中に出現している各色に関するエントリはこれらの範囲の集合内ではちょうど１回出現し、それの頻度fはt中の色cの出現頻度と一致する。

これは、ある部分木内に色cが出現している場合、この部分木から外に飛び出すポインタで色cに関するものはちょうど1個しかないこと、またそのポインタの子孫にのみ色cの葉が含まれていることからいえます。

さて、この事実を使えば、これらの範囲集合内で頻度が大きいものをk個とってくればいいだけになります。同じ文書番号を重複して数えてしまうとか、足さないといけないとか考える必要はありません。

それぞれの範囲内でRange Max Query (RMQ)を走らせ、各範囲内で最大値のものをk個ヒープに登録します。
そして、ヒープから一個ずつ一番高い値を取り出し、取り出した値に関する範囲を二個の部分範囲に分割し、それぞれの中からRMQを適用してまた最大値二個登録し、ヒープから最小の値を一個除きます。これを繰り返せば上位k個を取り出すことができます。
この時間はRMQはO(1)時間、O(n)bitsで実行でき、ヒープの操作時間合計はO(k log k)です。

(*)を求める時間は二分探索であることからO(log n)時間、predecessor用のデータ構造を使うとO(log logn)時間でとけますが、もうちょっと補助データ構造を使うと一つの節点あたりO(1)時間でとくことができます。

計算時間はクエリ節点から根への範囲の個数は高々dep個なので、まとめるとO(dep + k log k)時間でとけます。

さて、この話は頻度情報以外も扱えます。例えば文書にページランクのような固有のスコアが与えられている場合、fの代わりにそのスコアをいれておけば、同じように動きます。

アイディアは単純ですがとてもきれいな話だと思います。
この著者の人と昨年夏にあったとき、すごいのを思いついているのだが言えないといってたのが分かります。