×

[PR]この広告は3ヶ月以上更新がないため表示されています。
ホームページを更新後24時間以内に表示されなくなります。

Succinct Integer Array Library

Succinct Integer Array

Succinct Integer Array というのは造語です. ビット列に対する Succinct なデータ構造を利用して, ゼロの多い配列を圧縮したものと考えてください.

Succinct なデータ構造については, 岡野原大輔氏による解説とソースコードを参考にさせていただきました.
Tsujii Laboratory: Daisuke Okanohara
高速かつ省メモリで文字列を扱うデータ構造「wavelet tree」
Tx: Succinct Trie Data structure

Introduction

Succinct なデータ構造の勉強という名目で 作成したライブラリです. Rank の実装は Tx とほぼ同じになっていますが,Select については異なる実装がなされています.

Source

IntArray GNU Lesser General Public License に従います.

intarray-000.tgz - 4,953 bytes

MinGW gcc 3.4.2 で動作確認をしています.

Update

April 6, 2007 - Version 0.00
ライブラリとしては使いどころがないかもしれません.
ソースコードに価値を見出してくれる人がいるかもしれないので, 公開してみることにしました.

Structures

intarray.h からの抜粋になりますが, 以下のような構造体を提供します.

// 圧縮配列のハンドル
typedef  struct IAry  *hIAry;
// 線形探索の位置情報
typedef  struct IAryScan
{
  hIAry    h;     // 探索している圧縮配列のハンドル
  IAryIdx  idx;   // 次の整数の番号
  IAryIdx  pos;   // 次の整数の格納位置
  int      jump;  // 格納位置の有効(0)と無効(1)
}  IAryScan, *hIAryScan;

圧縮配列に対してランダムアクセスすることは可能ですが, 高速にシーケンシャルアクセスするための構造体を用意しています. 探索速度が最大で 10 倍くらいになるので, IAryScan を有効利用できるかどうかが 探索速度の鍵になると思います.

Functions

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

sample.c を参考にしてください.

To Do

ページ自体が作成中です.

References

ページの先頭に一覧があります.

Back
Last-Modified: April 16, 2007