Tiny Double-Array Library

ダブル配列 （ Double-Array ） とは， トライ （ Trie ） のデータ構造の一つで， 「小さい辞書で高速な検索」が特長になります． トライを表現したデータ構造ですから， 「入力文字列の前方部分列と一致するキーの検索」が可能です． 使い方としては，フィルタリングや構文解析，形態素解析などがあります．

ライブラリとしては，おそらく Darts が有名です．
Darts: Double-ARay Trie System

TinyDA は， Darts に影響されて作成したライブラリです． キーを整列して辞書に一括登録するようになっていて， レコードについては，型を特定せず，領域だけを確保するようになっています． そのため，辞書を作成した後でキーを追加することはできませんが， レコードを変更することは可能です． ただし，レコードを変更する場合は， 書き込む領域を誤ると辞書が破損しますので，十分に注意してください．

このプログラムは，int のサイズが 32-bit であると仮定しています． また，構造体に 0 長配列メンバ （ C99 ）を使用しているので， コンパイラによってはエラーになります．

辞書を構築するとき，キー数を nkey， キーの平均長を ave， 最大長を max， 辞書のサイズを dic とすると， （ ( ave + 28 ) * nkey + 2,048 * max + dic ） 程度のメモリを必要とします．

TinyDA は GNU Lesser General Public License に従います．

tinyda-123.tgz - 13,906 bytes
tinyda-122.tgz - 13,498 bytes
tinyda-121.tgz - 13,428 bytes
tinyda-120.tgz - 13,355 bytes
tinyda-110.tgz - 12,429 bytes
tinyda-100.tgz - 11,940 bytes

文字コードは UTF-8 になっています． MinGW gcc 3.4.2 で動作確認をしています．

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

// キー集合のハンドル
typedef  struct DASet  *hDASet;

// 辞書のハンドル
typedef  struct DADic  *hDADic;

// 辞書の状態
typedef  struct DAStat
{
  int  nbc;       // 配列 BC（ BASE, CHECK ）の長さ
  int  ntail;     // 配列 TAIL の長さ
  int  size;      // 配列 BC と配列 TAIL に割り当てたバイト数
  int  nkey;      // キー数
  int  maxlen;    // 最大キー長（ NULL 文字を除く ）
  int  boundary;  // バイト境界
}  DAStat, *hDAStat;

// 列挙用の関数
// 引数は，キー，レコード，オリジナルの順
// 返り値を DA_OK 以外にすると列挙を終了する
typedef  int ( *fDACall )( const char *, void *, void * );

辞書のサイズは DAStat のメンバ size で分かりますが， 4 * nbc + ntail で算出されます． 基本的に，BASE が 3 bytes で，CHECK が 1 byte になっています． これは，辞書を小さくするためなのですが， BCのサイズの上限が 2^23 = 8,388,608 に制限されます． おそらく，日本語や英語の単語を約 500 万件 くらいまで登録できると思います．

tinyda.h からの抜粋になりますが， 以下のような関数を提供します．

// キー集合の作成
int  DASet_Open( hDASet *h );

// キー集合の読み込み
// タブや改行による区切りを delim で指定する
// レコードのサイズを rec で指定する
int  DASet_Load( hDASet h, const char *path, const char *delim, int rec );

// キーの追加
// レコードのサイズを rec で指定する
int  DASet_Insert( hDASet h, const char *key, int rec );

// キー集合の破棄
int  DASet_Close( hDASet h );

以上がキー集合を操作するための関数です． 同じキーを重複して追加しようとした場合， レコードのサイズが上書きされるのようになっています． 重複の検出のために，内部でハッシュ表を作成します．

// 辞書の作成
// レコードは boundary で指定したバイト境界に配置される
int  DADic_Build( hDADic *h, hDASet set, int boundary );

// 辞書の読み込み
int  DADic_Open( hDADic *h, const char *path );

// 辞書の破棄
int  DADic_Close( hDADic h );

// 辞書の保存
int  DADic_Save( hDADic h, const char *path );

辞書の構築や解放，入出力のための関数です． 構築時に指定したバイト境界にレコードが配置される以外， 特に説明するようなことはありません． ただし，realloc が返したアドレスを 起点とするバイト境界に配置されます．

レコードのサイズが一種類しかない場合， もしくはレコードのサイズの最大値がバイト境界以下の場合， 共通するサフィックスを併合することで辞書を圧縮します．

// 辞書情報の取得
int  DADic_Status( hDADic h, hDAStat st );

// 登録キーを昇順に列挙
int  DADic_Enum( hDADic h, void *arg, fDACall call );

辞書の情報を取得したり，登録されているキーを列挙したりするための関数です．

// 入力文字列と一致するキーを辞書から検索
// レコードへのポインタを返す
void  *DADic_Search( hDADic h, const char *key );

// 入力文字列の前方部分列と一致するキーを辞書から検索
// レコードへのポインタを返す
// 最初はインデックスを 0 にしておき，NULL を返すまで繰り返し呼び出す
void  *DADic_Prefix( hDADic h, const char **s, int *idx );

// 入力文字列に出現するキーを辞書から検索
// レコードへのポインタを返す
// 最初の呼び出しでは，start = s，インデックスを 0 にしておく
// NULL を返すまで繰り返し呼び出す
void  *DADic_Infix( hDADic h, const char **start, const char **s, int *idx );

辞書を用いて検索するための関数です． キーが見つかった場合はレコードへのポインタを返し， 見つからなかった場合は NULL を返します．

DADic_Prefix や DADic_Infix を呼び出した後， s はキーの検出位置もしくは 遷移の失敗位置を指しているので，s - start により 一致したキーの長さを容易に求めることができます．

// エラーメッセージ
const char  *DAErr_String( int err );

エラーコードに対応する文字列を返します．

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

Darts と TinyDA を使って ipadic-2.6.3 の見出し語と読みに対する 辞書を作成してみたところ，サイズは以下のようになりました． TinyDA のレコードありは， 4 bytes 境界上に 4 bytes のレコードを確保するように設定した場合の結果になっています．

再帰呼び出しによるクイックソートを使っているので， 故意にスタックオーバーフローを引き起こすことが可能ですが， あんまり直す気がありません．

移植性のことを考えると，いろいろと直すべき点があると分かっていますが， どのように修正すべきなのかについて，作者があまり詳しくありません． というわけで，力不足により，適切に修正することができません．

青江順一． トライとその応用． 情報処理．pp. 244-251．1993．

森田和宏，泓田正雄，大野将樹，青江順一． ダブル配列における動的更新の効率化アルゴリズム． 情報処理学会論文誌．Vol. 42．No. 9．pp. 2229-2238．2001．

矢田晋，森田和宏，泓田正雄，平石亘，青江順一． ダブル配列におけるキャッシュの効率化． FIT2006．pp. 71-72．2006．