簡潔データ構造の入門の入門

最近、簡潔データ構造(Succinct Data Structure)がじわじわ人気が出てきているように感じるので入門の入門、くらいの記事を書いておく。
この記事では簡潔データ構造において最も基本的なデータ構造である完備辞書(Fully Indexable Dictionary)について説明する。
新しい概念が出てきた時に気になるのは「どうやって実現するのか」「それができると何が嬉しいのか」という2点だと思う。
前者についてはこの記事(http://d.hatena.ne.jp/takeda25/20140201/1391250137)がわかりやすいのでここでは述べない。この記事では「完備辞書があると何が嬉しいのか」について説明する。

完備辞書とは
完備辞書はrankおよびselectという操作が定数時間で実行できるビット列のこと。rank(i)はi番目のビットより前にいくつ1があるかを返し、select(i)はi番目の1は何ビット目かを返す。rankとselectは互いに逆の操作になっている。具体的には以下のような感じ。

ビット列: b = 10101011

b.rank(0) = 0
b.rank(1) = 1
b.rank(2) = 1
b.rank(3) = 2
b.rank(4) = 2
b.rank(5) = 3
b.rank(6) = 3
b.rank(7) = 4
b.rank(8) = 5

b.select(0) = 0
b.select(1) = 2
b.select(2) = 4
b.select(3) = 6
b.select(4) = 7

ここまでは当ブログでも何度か書いてきた。この記事では、これらの操作が何故基本的なのか、どういう意味を持っているのかについて書いてみたい。

値が単調増加する配列は集合とみなせる
データ構造のうち、配列(array)はだれでも知っている一般的なものだといえる。0から(m-1)までの値を取り、n個の要素を持つ配列はn lg(m)ビットで表現できる(lgは底が2のlog)。
なぜならデータの種類は高々m種類なのでひとつのデータはlg(m)ビットで表現でき、これがn個あるのでn lg(m)ビット必要となる。この計算量は決して小さくはないのでもっと小さいサイズで表現したい。
任意の値を取る配列の場合、ビット数はn lg(m)より小さくできない。しかし取りうる値に何らかの制約がある場合にはビット数を小さく出来る。
ここでは制約として"値が狭義の単調増加をする"というものを考える。この制約があると配列は集合(set)とみなすことが出来る。集合は配列からデータの順番という情報を消し去ったものでmビットで表現できる(具体的にどうするかは後述)。
集合にはデータの順番がないので、例えばs1 = { 0, 2, 4, 6, 7 }もs2 = { 6, 7, 4, 0, 2 }も同じデータを表す。これを昇順に並べることでa = [ 0, 2, 4, 6, 7 ]という単調増加な配列を作れる。

集合を表すデータ構造
前節で集合がmビットで表現できると書いた。これはどうやって実現するかというと

集合: s = { 0, 2, 4, 6, 7 }
ビット列: b = 10101011

というように集合が持っている要素を1に、それ以外の要素を0にしたビット列を用意すれば良い。このビット列は最も大きい要素(上の例では7)より後ろのビットは全部0なので持っておく必要がない。従って取りうる要素が0から(m-1)のときは高々mビットあれば表現できる。
このビット列表現によって単調増加する配列を実現するのに必要なビット数はn lg(m)ビットからmビットに変化した。例えばm=2nのとき、配列そのままだとn lg(2n) = n lg(n) + nビット必要だが、集合として表現すれば2nビットですむ。

集合を配列のように扱う
データサイズを小さくするために単調増加する配列を集合で表現した。しかしこれはデータサイズを小さくすることが目的なのであって、利用する側としてはあたかもただの配列であるように扱いたい。
つまり配列a = [ 0, 2, 4, 6, 7 ]に対してa[0] = 0, a[1] = 2のようにi番目の要素を定数時間で取り出したい。この操作に対応するのが本記事の冒頭で述べた、完備辞書の2つの操作のうちのひとつ、selectにほかならない。再掲すると

配列: a = [ 0, 2, 4, 6, 7 ]
集合: s = { 0, 2, 4, 6, 7 }
ビット列: b = 10101011

a[0] = 0
a[1] = 2
a[2] = 4
a[3] = 6
a[4] = 7

b.select(0) = 0
b.select(1) = 2
b.select(2) = 4
b.select(3) = 6
b.select(4) = 7

となる。完備辞書は(実装方法は本記事の範囲を越えるので述べないが)select(とrank)が定数時間で実行できるビット列のことなので、完備辞書(という名のビット列)を使って単調増加する配列を表現すれば、selectという操作を通してあたかも通常の配列のように要素アクセスができる。
また、冒頭で述べたようにrankはselectと逆の操作になっている。これは配列で言うと"データの値がxである位置を教えてね"という逆引きの操作になる。通常、配列ではこの逆引きの操作は定数時間ではできないので、この操作ができるという点で完備辞書は配列よりも優れている。

完備辞書の応用例
ここまでで述べたように、単調増加する配列が必要な部分を完備辞書で置き換えることができる。例えば、複数のテキストを連結して1つのテキストにした場合に、テキストの切れ目の位置を管理する配列が単調増加する配列になっている。
この記事では狭義の単調増加列を扱ったが、実は少しの拡張で広義の単調増加列の簡潔データ構造も実現できる。広義の単調増加列は木構造とみなせる(参考：http://d.hatena.ne.jp/echizen_tm/20140130/1391100781)ので、広義の単調増加列の簡潔データ構造は木構造の簡潔データ構造とも言える。これはLOUDSと呼ばれている。
またこの記事では集合を配列のように扱うためにビット列にrankとselectを定義したが、配列に対してもrankとselectを定義できる。このrank、selectの定義された配列をウェーブレット木(もしくは実装の違いでウェーブレット行列)と言う。ウェーブレット木(行列)はFM-Indexという高性能な全文検索アルゴリズムに利用される。

参考資料
このへんを参考に。
http://d.hatena.ne.jp/echizen_tm/20111208/1323360317

簡潔データ構造の書いてある和書