完備辞書（簡潔ビットベクトル）の解説
以前、「簡潔データ構造 LOUDS の解説」というシリーズの記事を書いたことがあります。
LOUDS というのは木構造やtrieを簡潔に表すことができるデータ構造なのですが、この中で「簡潔ビットベクトル」というものについてはブラックボックスとして扱っていました。
また、中学生にもわかるウェーブレット行列を書いたときも、その中で出てきた「完備辞書」の実装には触れませんでした。
この「簡潔ビットベクトル」「完備辞書」は、同じものを指しています*1。
今回は、このデータ構造*2について書いてみます。
完備辞書でできること
ビット列に対する定数時間の rank と selectです*3。
rank()は、「ビット列の先頭から位置 k までに、1 のビットがいくつあるか」*4。
select()は、「ビット列の先頭から見て、n 個目の 1 のビットの次の位置はどこか」*5。
それぞれ例を挙げます。
"0100100111011110" というビット列（B とします）の中で、先頭から位置 12 までの間に、いくつ 1 があるか。
下の図で、先頭から矢印までの範囲の 1 を数えることになります。
数えてみると、6つあります。
つまり、rank(B, 12) = 6 ということになります*6。
また、このビット列の中で、4 個目のビット 1 の次の位置はどこか。
下の図は、先頭から 4 個の 1 に色をつけたものです。
4番目の 1 は位置 8 にあるので、その次である位置 9 が求めるものです。
つまり、select(B, 4) = 9 ということになります*7。
先頭から順に数えるというやり方では、サイズが大きくなるとこれらの操作には長さに比例した時間がかかりますが、完備辞書を使うと、これらの操作が定数時間で可能になります。
実装
ここでは、完備辞書の代表的な実装例を挙げます。
元のビット配列 B に加え、3 つの補助データを持つというものです。
それによって、定数時間での rank() が可能になります。
まず、一つ目の補助データです。
B の長さを n とすると、B を長さ lg(n) ^ 2 ごとの大ブロックに分割して、それぞれの大ブロックの先頭の rank() の結果を保存しておきます。
ここで、仮に B の長さ n が 2 ^ 16, つまり 65536 ビットだとします。
すると、lg(n) = 16 なので、lg(n) ^ 2 = 256 になります。
つまり、一つ目の補助データは 256 ビットごとに持っておくことになります。
記録するべきものは、0, 256, 512, ... の位置の rank() の結果です。
まず、位置 0 の rank()、つまり「位置 0 の左にいくつ 1 があるか」を考えます。
位置 0 は左端なので、答えは当然 0 になります。
これが、補助データの最初のものになります。
次に、位置 256 の rank() です。
位置 256 まで（下の図の A の範囲）に、いくつ 1 があるかということです。
この画像では途中が省略されているのですが、実際にはビット列があるので、数えればわかります。
たとえば 131個あったとすると、rank(B, 256) = 131 を補助データの次の要素として記録します。
その次は位置 512 の rank() です。
たとえば、256〜511 （図の A' の範囲）に 1 が 137 個あったとします。
この場合、記録する rank() は先頭からのものなので、B の範囲にある 1 のビットの数ということになります。
A の範囲には 131 個あったので、それに 137 を加えた 268 を書き込むことになります。
同じように、位置 768, 1024...についても先頭からの rank() を求めて、最後まで埋めます。
そして、次は二つ目の補助データです。
今度は、一つ目の補助データで分割した大ブロックを、さらに小ブロックに分割します。
小ブロックのサイズは、B の長さが n のとき、lg(n) / 2 のように決めます。
すると、n = 65536 のとき、小ブロックのサイズは lg(n) / 2 = 16 / 2 = 8 となります。
二つ目の補助データでは、この小ブロックごとに rank() を保存するのですが、保存するのは大ブロックの先頭との差分です。
たとえば、ビット列 B の 512 ビット目からの部分が次のようになっているとします。
すると、小ブロックは次のように、8 ビットごとの単位になります。
小ブロックについてもそれぞれ rank() を記録するのですが、小ブロックについては、それが属する大ブロックの先頭からの差分として記録します。
上の図で、512 からの小ブロックは大ブロックの先頭なので、記録する rank()（512からの差分）は 0 です。
次の 520 からの小ブロックは、512〜520 の間に 5 個の 1 があるので、5 を書き込みます。
528 からのものは、520〜528 の間に 3 個の 1 があるので、520 までのものと合わせて 520からの差分は 5 + 3 = 8 です。
同じように、位置 536 以降についても、位置 512 からの 1 のビットの数の累計を書いていきます。
すると、小ブロックについて書き込む数字は次のようになります。
さて、このように大ブロックと小ブロックについて、それぞれ rank()（またはその差分）を記録すると、何がうれしいか。
それは、小ブロックの先頭までの rank() を定数時間で求められる ということです。
たとえば、このデータを使って、位置 533 までの rank()、つまり rank(B, 533) を求めたいとします。
図の中では、次の場所です。
この位置の rank()、つまり先頭からの 1 のビットの数は、位置 533 が属する大ブロック・小ブロックを調べれば*8次のように分解できます。
- 位置 0 から 位置 512 までの 1 のビットの数
- 位置 512 から 位置 528 までの 1 のビットの数
- 位置 528 から 位置 533 までの 1 のビットの数
最初の 2 つについては、上で作った表を参照することで求めることができます。
まず、位置 0 から位置 512 までの 1 のビットの数です。
位置 512 から始まる大ブロックの rank() ということになるのですが、それは最初に作った表に書いてあります。
表によると、位置 512 までには 268 個の 1 のビットがあることがわかります。
次に、位置 512 から位置 528 までの 1 のビットの数です。
小ブロックについては、大ブロックの先頭（この場合、位置 512）からの差分の rank() が記録してあるので、それを見ます。
位置 512 から位置 528 までには、8 個の 1 のビットがあるということがわかります。
ここまでで、位置 528 までに 268 + 8 = 276 個の 1 のビットがあることがわかりました。
残りは、位置 528 から 位置 533 までのビット数ということになります。
位置 528 から 位置 533 の範囲は、次の灰色の部分です。
パッと見で、1 のビットは 2 個だということがわかります。
この例では、小ブロックのビット数は 8 なので、一瞬で数えることができます。
しかし、コンピュータは目で見て数えるということはできないので、3つ目の補助データを用意します。
ここで作るのは、ビット列にあたる数字の位置に、そのビット列が持つ 1 のビットの数を書いたテーブルです。
たとえば 8 ビットの場合、8 ビットで表せる数字は全部で 256 個なので、そのひとつひとつに対して 1 のビットの数を書いていきます*9。
次のような表です。
添字を 2 進数で表すと、数字が添字の 1 のビットの数に対応するというのがわかりやすいかと思います。
さて、今回の例で知りたいのは、位置 528 から位置 533 の間にいくつ 1 のビットがあるかです。
知りたい範囲を含む小ブロックのビットは次のようになっています。
この範囲から外れる部分を、ビットマスクで 0 にします。
そして、先ほどの表で、10010000（144）にあたる場所を見ます。
これで、10010000 の中の 1 のビットが 2 個であるということがわかります。
これで、位置 533 までに 268 + 8 + 2 = 278 個の 1 のビットがあることがわかりました。
作る補助データをまとめると、次のようになります。
- 大ブロック(長さ lg(n) ^ 2)ごとに、先頭からの rank() を記録したもの
- 小ブロック(長さ lg(n) / 2)ごとに、所属する大ブロックの先頭からの rank() を記録したもの
- 小ブロック(長さ lg(n) / 2)のすべてのビットパターンに対して、それの持つ 1 のビット数を記録したもの
ここまでの内容を知っていれば、完備辞書を作り、検索するプログラムを作ることはできます。
ですが、完備辞書にはある都合のよい性質があり、それがこのデータ構造の特徴となっています。
それは、元データの大きさが増えても、補助データの大きさはそんなに増えないということです。
どういうことか、具体的に見てみます。
まず、元データ B のビット数を、上での例のように n とおきます。
このとき、大ブロックの数は、n / (lg(n) ^ 2) となります。
ここで、それぞれの大ブロックに対して先頭からの rank() を記録するのですが、そのデータひとつあたり何ビット必要かわかるでしょうか。
それは lg(n) です。
元データ B の中での先頭からの rank() は、n 以上になることはありません。
0 以上 n 未満の数を表すのには、n が 2 ^ m で表せる形であれば*10、m ビットが必要です。
つまり、lg(n) ビットが必要ということになります。
今回の例で言うと、rank() は 0 以上 65536 未満で、65536 = 2 ^ 16 なので、rank() ひとつを表すのに 16 ビットが必要ということになります。
大ブロックの数は n / (lg(n) ^ 2) 個なので、それに lg(n) ビットをかけると、合計 n / lg(n) ビットになります。
これが、大ブロックのデータ格納に必要な容量ですが、 n / lg(n) なので、n が増えるに従って元データに対する割合は小さくなります。
次に、小ブロックについて考えます。
それぞれの小ブロックに対しては、大ブロック先頭からの rank() を記録するということになっています。
つまり、この差分の rank() は、大ブロックの大きさである lg(n) ^ 2 以上にはなりません。
数字ひとつを記録するのには、lg(lg(n) ^ 2)、つまり 2 * lg(lg(n)) だけのビットが必要ということになります。
小ブロックの個数は n / (lg(n) / 2) 個なので、小ブロック全体として必要なビット数は (n / (lg(n) / 2)) * (2 * lg(lg(n))) = n * 4 * lg(lg(n)) / lg(n) です。
lg(lg(n)) より lg(n) のほうがオーダーが大きいので、これもやはり n が増えるに従って元データに対する割合が小さくなります。
最後に、小ブロックのビットパターンそれぞれに対するビット数の表を考えます。
小ブロックの大きさは (lg(n) / 2) なので、要素ひとつあたりに必要なビット数は lg(lg(n) / 2)、つまり lg(lg(n)) - 1 です。
そして、表の要素数は (lg(n) / 2) 個のビットで表せる数だけ必要なので、2 ^ (lg(n) / 2) = n ^ (1 / 2)、つまり √n です。
また、ビットマスクをしない場合（上で脚注として書いた部分）を考えると、検索位置ごとに表を作ることになるので、小ブロックの大きさである lg(n) / 2 個となります。
表の要素数と、要素ひとつあたりに必要なビット数、それに表の個数をかけると、√n * (lg(lg(n)) - 1) * lg(n) / 2 なので、やはり n よりも小さいオーダーということになります。
そういうわけで、元データよりも小さなオーダーの補助データを使って、任意の位置の rank() が定数時間で求められるという話でした。
いい話ですね。
さて、記事の最初のほうで、rank() に対応する select() というものに触れたのを覚えているでしょうか。
select()は、「ビット列の先頭から見て、n 個目の 1 のビットの次の位置はどこか」。
この select() というのは、rank() に比べると、使いどころはだいぶ少ないのですが、たとえば LOUDS などでは使いまくるので、これも定数時間でできてほしいところです。
で、これも一応、元データよりも小さいオーダーの補助データを使って、定数時間で調べることができるようですが、こっちのほうは実装がかなり大変なうえ、補助データや検索時間の定数項も大きかったりするので、日和って rank() 用のブロックを二分探索したりしたり線形探索したりするのが普通です。
あんまりいい話じゃないですね。
rank() のほうも、n によって大きさを変えたりしないで、大ブロックと小ブロックの大きさを適当に決めて実装するのが普通です。
小ブロック中の 1 のビットを数えるのも、脚注で書いたように「検索位置ごとの表を作る」ということは普通やりません。
結局、定数時間とかはあんまり関係なくて、rank() と select() があんまり容量を取らないでけっこう速くできるというのが重要なポイントなので、実装をする際には時間を計ったりしながら適当に試行錯誤するのがいいのかもしれません。
ところで、実装時に注意することとして、小ブロックの rank() を記録するのに、サボって 32bit 型などを使わない ということがあります。
わざわざ大ブロックと小ブロックを分けた意味は、小ブロックに対して記録する rank() を小さくしてオーダーを抑えるということなので、小ブロックの rank() と大ブロックの rank() に同じサイズの型を使うなら、大ブロックを作る意味がありません。
もっとも、大ブロックを作らないで小ブロックだけで実装するというのもひとつのやり方だと思いますが、その場合「簡潔データ構造」ではなくなります（元データと同じオーダーの補助データが必要になるため）。
ここに書いたような内容は、「高速文字列解析の世界」や「日本語入力を支える技術」にも書いてあります。
この記事を書きながら、「ここまで詳しく書く必要があるのか」と思って「幼稚園児にもわかる完備辞書」というタイトルにしようかと思いましたが、さすがに思いとどまりました。
でも、まあ普通の大学生が真面目に読めばわかるんじゃないのかなぁぐらいには考えています。
*1:Wikipedia では、簡潔データ構造の項で簡潔辞書という名前で扱われているようです。
*2:今回の記事では「完備辞書」で統一します。
*3:実は、selectは後述するように定数時間でない実装が一般的です。
*4:rank1とすることが多いのですが、ここでは略しました。
*5:rank との対称性のために、直感的に少しわかりにくくなっています。
*6:引数は前からビット列、位置です。
*7:引数は前からビット列、1 の個数です。
*8:ビットシフトなどで求められます。
*9:これは実用寄りの話です。理論的にはビットマスクも lg(n) なので、それを避けるためか、小ブロック中の検索位置ごとに表を作るということをするようです。この例では、このような表を 8 個作ることになります。しかし、それを言うなら表のインデクシングとかも定数ではないような気がするのですが。
*10:そうでない場合は切り上げます。
