高速かつ省メモリなbit vector「sucBV」を作る

大規模データを効率的に扱う操作付きbit vectorライブラリの実装

本記事では大規模なデータを扱うためのデータ構造である操作付きBit Array (SUCcinct Bit Vector: sucBV)を紹介します。sucBVは、vectorと同様に2値配列情報を保存する他にrank, selectと呼ばれる二つの操作を定数時間でサポートします。作業領域量はvectorの約3倍です。sucBVを用いることで、圧縮索引やsuccinct data structureなどを実装できます。

はじめに

　大規模なデータを扱うアプリケーションでは、速度とともに作業領域量も大きな問題となります。作業領域がメインメモリに収まらない場合、スワッピングが発生し、大幅な速度低下につながります。そのため近年、データ構造は高速なだけでなく、作業領域量が小さいことも求められています。今回紹介するデータ構造は「操作付き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を利用した、これらのデータ構造についても今後記事にする予定です）。

圧縮索引、succinct data structure

　「圧縮全文索引」は、任意のキーワードや部分列を漏れなく検索できる全文索引を、圧縮して保持したものです。従来の全文索引は作業領域量が大きい問題がありましたが、圧縮全文索引はわずかな速度低下で作業領域を大幅に減らすことができるデータ構造です。「succinct data structure」は、bit arrayや木構造情報をデータサイズに対し線形サイズ、もしくは情報理論的限界近くまで圧縮した状態で保持した上で、各操作を定数時間で実現するデータ構造です。本記事の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という省メモリを実現しています。