×

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

Tiny Double-Array Library

Double-Array

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

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

Introduction

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

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

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

Source

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 で動作確認をしています.

Update

November 18, 2007 - Version 1.23
コメントを英語に修正しました.
March 14, 2007 - Version 1.22
エラーメッセージを返す関数 DAErr_String を修正しました.
January 30, 2007 - Version 1.21
エラーコードをマイナスの値に変更しました.
ハッシュ関数を変更しました.
動作には変更ありません.
January 5, 2007 - Version 1.20
未使用要素の CHECK が 正しく設定されないバグを修正しました.
辞書に登録されているキーを列挙するための関数 DADic_Enum を用意しました.
January 2, 2007 - Version 1.10
DADic_Prefix において, 一致しないキーを検出するバグを修正しました.
入力文字列に出現するキーを辞書から検索する関数 DADic_Infix を用意しました.
DAStat に 最大キー長 maxlen を追加しました.
maxlen の追加にともない, 辞書ファイルの構造が変化しています.
December 26, 2006 - Version 1.00
とりあえず,動くものができたので公開することにしました.

Structures

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 で算出されます. 基本的に,BASE3 bytes で,CHECK1 byte になっています. これは,辞書を小さくするためなのですが, BCのサイズの上限が 2^23 = 8,388,608 に制限されます. おそらく,日本語や英語の単語を約 500 万件 くらいまで登録できると思います.

Functions

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_PrefixDADic_Infix を呼び出した後, s はキーの検出位置もしくは 遷移の失敗位置を指しているので,s - start により 一致したキーの長さを容易に求めることができます.

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

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

Sample

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

Comparison

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

辞書ソース サイズ ( bytes )
辞書ソース Darts-0.31 TinyDA-1.21
レコードありレコードなし
ipadic-2.6.3 見出し語 1,662,9777,023,8002,372,2001,460,158
ipadic-2.6.3 読み 1,981,1546,689,4561,915,0641,258,205

To Do

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

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

References

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

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

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

Back
Last-Modified: November 19, 2007