ビット列に対するランク簡潔索引の詳細説明

簡潔データ構造の一つであるランク簡潔索引について詳細を説明する．簡潔データ構造やランク簡潔索引についての説明は前回の記事を参照のこと．今回も説明を簡単にするために0,1のビット列を考える．また，ビット列の値についての事前知識はないとする（0,1の生成確率が偏っていることが分かっている場合には元データを圧縮できるが，今回はその場合は考えない）．

ランク簡潔索引を用いることで，元データと十分に小さいサイズのテーブルのみを用いて，定数時間でランクを求めることができる．
使用するテーブルは3つであり，各テーブルへのアクセス回数は1回である．

以下，その詳細について説明するが，以下に留意して読んでいただければと思う．

本当に3回のテーブルアクセスで正しい答えが求まるのか？
テーブルサイズは本当に小さくなるのか？

詳細説明

処理の流れ

n要素からなるビット列B[0..n-1]に対するランク簡潔索引を考える．まず，下図を用いてランクをどのように求めるかについて説明する．下図は処理の流れを説明するものであり，サイズについては正しくない．

f:id:koikezlemma:20131125113812p:plain

上図のBにおいて，Rank₁(B,25)を求める場合を説明する．まず，補助データを用いない場合について考え，その後，いくつかの補助データを導入する．

まず，補助データを用いない場合は，配列Bについてindex 0から25までをスキャンし1の数を数えることで，ランク値（11）を算出できる．

次にこれをデータサイズの小さいテーブルR₁をあらかじめ作成しておくことで少し高速化する．作成手順は以下の通りである．配列Bを長さlog²n の大ブロックに分割し，各大ブロックの最終要素のランク値をテーブルR₁に格納する．このテーブルを用いることで，Rank₁(B,25)を求める際に右側の大ブロック以外の大ブロックをスキャンする必要がなくなる．左側と中央の大ブロックにおける1の合計数はR₁を参照することで7と分かるので，Rank₁(B,25)を求めるためには，この値にindex 18 から 25 までの1の数を加えればよい（右側の大ブロックをスキャンする）．このように，テーブルR₁を用いることで，スキャンの範囲を右側の大ブロックの中だけに限定できる．

次に大ブロックのスキャンを高速化する．そのために上記と同様のことを行う．大ブロックを長さ(1/2) log n の小ブロックに分割し，各小ブロックの最終要素のランク値（大ブロックの中でのランク値）をテーブルR₂に格納する．このテーブルを用いることで自身の属する小ブロック以外の小ブロックをスキャンする必要がなくなる．左側と中央の小ブロックにおける1の数はR₂を参照することで3と分かるので，大ブロック内でのランク値を求めるためには，これまで求めた2つの値(7+3)にindex 24 から 25 までの1の数を加えればよい（小ブロック内でランク値計算を行うことで算出できる）．

最後に小ブロック内のランク値計算を高速化する．小ブロックにおいて取りうるすべてのビット列パターンに対するランクの値をテーブルR₃に格納する．小ブロックが3ビットの時はR₃は以下のようになる．

f:id:koikezlemma:20131125113828p:plain:w200

まず，自身の属する小ブロックのビット列を元データから取得する．小ブロックのサイズはとても小さいため，1回のメモリアクセスで小ブロックの全ビット列を取得できる．（今回は詳しく説明しないが，使用する計算機は1回のメモリアクセスで log n ビットのデータを取得できると仮定している．このような計算機モデルはword RAMと呼ばれている．このサイズは小ブロックサイズよりも大きいので1回のメモリアクセスで全ビット列を取得することが可能である．）自身の属する小ブロックのビットパターンは101なので，下記テーブルの6行目にアクセスすればよい．また，index 25の小ブロック内でのindexは1なので，小ブロック内でのランク値はテーブル参照により1と求まる．以上から，Rank₁(B,25) = 7 + 3 + 1 = 11 と求まる．

Rank₁(B,25)を求める手順をまとめると以下のようになる．

テーブルR₁に1回アクセスし，上図①を取得する．
テーブルR₂に1回アクセスし，上図②を取得する．
元データとテーブルR₃に1回ずつアクセスし，上図③を取得する．
上記3つの値の和をとったものが所望のランク値となる

テーブルのデータサイズについて

上記のデータ構造のデータサイズが十分に小さく，簡潔データ構造になっていることを説明する．まず，元データに対し最適な圧縮をかけた場合のデータサイズZを求める．ビット列の値についての事前知識がない場合，n要素のビット列を保持するためには，nビットが必要である．よって，元データはこれ以上サイズを圧縮することはできず，Z = n (ビット) となる．

次に使用するデータ構造ごとのデータサイズを計算する．

まず，①の計算では，テーブルR₁を使用している．テーブルR₁については，1要素あたりのサイズが log n (ビット)で要素数がn/log²nなので，合計では，n/log n (ビット)である．

②の計算では，テーブルR₂を使用している．テーブルR₂に格納される値の最大値は log²n である．よって，1要素あたりのサイズは log (log²n) ビットあれば十分である．また，テーブルR₂の要素数は n / (1/2) log n なので，R₂合計では，
$\frac{n}{\frac{1}{2}\log n}\log \left(\log^2 n\right) = \frac{4n\log\log n}{\log n}$
となる．

③の計算では，元データとテーブルR₃を使用している．元データのデータサイズはnビットである．テーブルR₃については以下の通りである．格納される値の最大値は(1/2) log n なので，1要素あたりのサイズは log ((1/2)log n) ビットあれば十分である．要素数はテーブルの行数 $2^{\frac{1}{2}\log n}$ と列数 $\frac{1}{2}\log n$ の掛け算となる．
よって合計では，
$2^{\frac{1}{2}\log n}\cdot \frac{1}{2}\log n \cdot \log \left(\frac{1}{2}\log n\right) = \mathcal{O}\left(\sqrt{n}\log n \log\log n\right)$
となる．この値は，
$\mathcal{o}\left(\frac{n\log\log n}{\log n}\right)$
となることが示せる．