Succinct Integer Array というのは造語です． ビット列に対する Succinct なデータ構造を利用して， ゼロの多い配列を圧縮したものと考えてください．
Succinct なデータ構造については，
岡野原大輔氏による解説とソースコードを参考にさせていただきました．
Tsujii Laboratory: Daisuke Okanohara
高速かつ省メモリで文字列を扱うデータ構造「wavelet tree」
Tx: Succinct Trie Data structure
Succinct なデータ構造の勉強という名目で 作成したライブラリです． Rank の実装は Tx とほぼ同じになっていますが，Select については異なる実装がなされています．
IntArray は GNU Lesser General Public License に従います．
intarray-000.tgz - 4,953 bytes
MinGW gcc 3.4.2 で動作確認をしています．
intarray.h からの抜粋になりますが， 以下のような構造体を提供します．
// 圧縮配列のハンドル typedef struct IAry *hIAry;
// 線形探索の位置情報
typedef struct IAryScan
{
hIAry h; // 探索している圧縮配列のハンドル
IAryIdx idx; // 次の整数の番号
IAryIdx pos; // 次の整数の格納位置
int jump; // 格納位置の有効（0）と無効（1）
} IAryScan, *hIAryScan;
圧縮配列に対してランダムアクセスすることは可能ですが， 高速にシーケンシャルアクセスするための構造体を用意しています． 探索速度が最大で 10 倍くらいになるので， IAryScan を有効利用できるかどうかが 探索速度の鍵になると思います．
intarray.h からの抜粋になりますが， 以下のような関数を提供します．
// 圧縮配列の作成 int IAry_Open( hIAry *h );
// 圧縮配列の破棄 void IAry_Close( hIAry h );
空の圧縮配列を作成する関数と， 作成した圧縮配列に割り当てた領域を解放する関数です．
// 圧縮配列をファイルから入力 int IAry_Load( hIAry *h, const char *path );
// 圧縮配列をファイルに出力 int IAry_Save( hIAry h, const char *path );
作成した圧縮配列を IAry_Save でファイルに保存することができます． また，保存した圧縮配列は，IAry_Load により読み込むことができます．
// 符号あり整数の追加 int IAry_AddInt( hIAry h, IAryInt x );
// 符号なし整数の追加 int IAry_AddUInt( hIAry h, IAryUInt x );
整数を圧縮配列に追加するための関数です． ただし，索引を構築するまでは取得できません．
// 索引の構築と再構築 int IAry_BuildIndex( hIAry h );
整数を取得するための索引を構築する関数です． 圧縮配列を更新した場合，整数を取得する前に呼び出す必要があります．
// 符号あり整数の取得 IAryInt IAry_GetInt( hIAry h, IAryIdx idx );
// 符号なし整数の取得 IAryUInt IAry_GetUInt( hIAry h, IAryIdx idx );
指定したインデックスの整数を取得する関数です．
// 線形探索の初期化 void IAry_Start( hIAry h, hIAryScan scan );
// 線形探索の位置変更 void IAry_Jump( hIAryScan scan, IAryIdx idx );
// 線形探索による符号あり整数の取得 IAryInt IAry_NextInt( hIAryScan scan );
// 線形探索による符号なし整数の取得 IAryUInt IAry_NextUInt( hIAryScan scan );
圧縮配列に登録されている整数を先頭から順に取得していくための関数群です． IAry_Start を呼び出すことで探索が開始し， IAry_NextInt, IAry_NextUInt により 整数を一つずつ取得することができます． また，IAry_Jump を呼び出すことにより， 探索位置を変更することが可能です．
// 圧縮配列のサイズを算出 IAryIdx IAry_Size( hIAry h );
圧縮配列に対して割り当てられた領域の大きさを取得するための関数です．
sample.c を参考にしてください．
ページ自体が作成中です．
ページの先頭に一覧があります．