はじめに
大規模なデータを扱うアプリケーションでは、速度とともに作業領域量も大きな問題となります。作業領域がメインメモリに収まらない場合、スワッピングが発生し、大幅な速度低下につながります。そのため近年、データ構造は高速なだけでなく、作業領域量が小さいことも求められています。今回紹介するデータ構造は「操作付きbit vector（SUCcinct Bit Vector:sucBV）」です。sucBVは、圧縮索引やSuccinct Data Structureなど、データをコンパクトに表現する際に重要なデータ構造です。STLのvector<bool>と同様に、bit列情報B[0....n-1]を保存します。このbit列情報は前もって与えられ、変更が無いことを前提とします。sucBVは、次の二つの操作を定数時間でサポートします。
rank(p,bit)――B[0...p]中のbit（bitは1または0）の数を返すselect(i,bit)――(i+1)番目のbit（bitは1または0）の位置を返す
sucBVの作業領域量はbit vectorの長さがNのとき約0.4N Byteであり、長さ1G超のbit vectorなども通常のPC上で扱うことができます。
対象読者
C++の利用者を対象としています。
必要な環境
C++、32bit環境を想定しています。Windows XP上のVisual Studio C++ 2003、gcc 3.2.2で動作確認済みです。
sucBVの概要
sucBVは操作付きbit vectorであり、rank、selectの二つの操作をサポートします。bit vector B[0...n]が与えられた時、rank(p,bit)はB[0...p]中の1の数を返し、select(i,bit)は（i+1）番目のbit(1 or 0)の位置を返します。このbit vectorを利用することで、近年提案されている圧縮全文索引（Compressed Suffix Arrays、FM-index、wavelet treeなど）やsuccinct data structure（括弧木など）を実現することができます（sucBVを利用した、これらのデータ構造についても今後記事にする予定です）。
sucBVはbit arrayに対するsuccinctな（簡潔な）データ構造です。 いくつか例を挙げてrank、select操作を説明します。今、bit vectorとしてB[0...9] = 0101000111が与えられたとします。この時、rank(5,1) = 2です。なぜなら、B[0...5]中には2つの1があるからです。同様にしてrank(5,0)=4となります。一般にrank(p,1)+rank(p,0)=p+1が成り立ちます（添え字が0始まりなのでpではなくp+1）。またselectの場合は、select(2,1)=7となります。なぜなら、(2+1)番目の1の位置は7だからです。同様にして(2+1)番目の0の位置は4なので、select(2,0)=4となります。その他の結果は次の通りとなります。
B[0...9] = 0101000111
| rank(p,1) | rank(p,0) | |
| 0 | 0 | 1 |
| 1 | 1 | 1 |
| 2 | 1 | 2 |
| 3 | 2 | 2 |
| 4 | 2 | 3 |
| 5 | 2 | 4 |
| 6 | 2 | 5 |
| 7 | 3 | 5 |
| 8 | 4 | 5 |
| 9 | 5 | 5 |
| select(i,1) | select(i,0) | |
| 0 | 1 | 0 |
| 1 | 3 | 2 |
| 2 | 7 | 4 |
| 3 | 8 | 5 |
| 4 | 9 | 6 |
このrank、select操作は定義自体は非常に単純ですが、操作の時に毎回求めるとO(n)時間必要です。前もって全ての答えを求めておく場合も、rank、selectの結果を全て明示的に保持するには約8N byte必要になります（rankはrank(p,1)だけ保持して4N byte、select1とselect0を合わせて4N byte）。これはbit vector本体の作業領域量（0.125N byte）の約64倍にもなります。今回紹介するsucBVは定数時間でrank、select操作を実現しながら、作業領域量は約0.4N byteという省メモリを実現しています。
