2011年11月25日

succinct data structure というものを初めて知った．使用する空間量が情報理論的下限（つまりはエントロピー？）に近く且つ幾つかのクエリ処理が高速に行えるデータ構造であると．分類としては，適当なデータを表現するビット量の情報理論的下限をZとしてやると，Z + O(1) ビットで表現できる構造は implicit data structure で，Z + o(Z) ビットで表現できる（つまり係数も一致して漸近的に下限に至る）なら succinct で，O(Z) ビットで表現できる（つまり下限の定数倍程度）なら compact というと．

例としては，{0, 1, ..., n-1} の部分集合の表現（つまりは長さ n のビットベクタ）に対して rank と select というクエリをO(1)で行うギミックを付けた構造があると．rank(x) は x ビット目までの 1（ないし 0）の数を返すクエリで，select (y) は rank(x) = y なる最小の x を返すクエリ．rank を O(1) で計算するために o(n) なサイズのテーブル３つをうまく用意してやると．大きな１つのテーブルですべての答えを用意しようとすると n lg n になってしまう（引数の数がn通りでそれぞれの答えが lg n だから）ので，とりあえず (lg n)^2 毎に区切ったブロックの先頭だけの rank テーブルを作って（これで n / ((lg n)^2) * lg n = n / lg n ビットのテーブル），次に残りのブロック内の先頭からの rank の差分をどうにかしましょうとか考えるのね．残りの部分をどうするかだけど，とりあえず愚直に全部のインデックスに対してブロック先頭からの差分を保持すると O(n) 以上かかるのでダメで，一方，存在しうるブロックの全パタンを網羅しておこうとしてもブロックサイズが大きすぎてこちらも O(n) 以上かかる．しょうが無いのでもう一段ブロック化を導入してあげて，この小ブロックのサイズを lg n / 2 にしてあげると，この小ブロックに関して全パタン網羅しても o(n) で済むし小ブロックの先頭の rank （の大ブロックの先頭からの rank の差分）を全部保持しても o(n) で済みますよと．これにて一件落着．クエリ時には３つのテーブルを引いて足しあわせりゃいい．select はめんどいらしい．

まあ，再帰の段数を固定して適度なサイズ以下の問題は定数で答えが返るという状態を作っておけということなのか？　計算の一部を適当なサイズのデータに変えて取っておこうよというかよく使う部分計算はテーブルに取っておこうよというか．

それはさておき，rank/select で具体的に何が出来るのかがよく分からん．あとは一般にどんなクエリなら効率をデータ構造に押し付けられるんだ？　どの程度自動化できるんだ？　よく分からん（論文読め）．