×

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

Dynamic Double-Array Library

Double-Array

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

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

Introduction

DynDA は,動的なダブル配列なので, キーを一つずつ追加,削除できるようになっています. また,更新によって発生した無駄な領域を除去する機能があります. 試験的に公開しているだけなので,レコードの格納には対応していません.

Source

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

dynda-001.tgz - 5,895 bytes
dynda-000.tgz - 5,874 bytes

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

Update

March 17, 2007 - Version 0.01
無駄な領域を削除するときにエラーが発生するバグを修正しました.
March 15, 2007 - Version 0.00
試験的に公開することにしました.

Structures

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

// ダブル配列のハンドル
typedef  struct Dary  *hDary;
// ダブル配列の状態
typedef  struct Dstat
{
  unsigned  max;    // 末尾の要素
  unsigned  mblk;   // 使用中のブロック数
  unsigned  nblk;   // ブロック数
  unsigned  mtail;  // 配列 TAIL の使用中の長さ
  unsigned  ntail;  // 配列 TAIL の長さ
  unsigned  size;   // ダブル配列に割り当てられたバイト数
  unsigned  nemp;   // 未使用要素の数
  unsigned  nkey;   // 登録されているキーの数
}  Dstat, *hDstat;

各ブロックは,256 個の要素で構成されます. また,BASE, CHECK には, それぞれ 4 bytes が割り当てられます.

Functions

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

// 辞書の作成,もしくは読み込み
int  Dary_Open( hDary *h, const char *path );
// 辞書の破棄
int  Dary_Close( hDary h );
// 辞書の保存
int  Dary_Save( hDary h, const char *path );

辞書の作成と破棄,入出力のための関数です.

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

辞書の情報を取得するための関数です.

// 検索
int  Dary_Search( hDary h, const char *s );
// 追加
int  Dary_Insert( hDary h, const char *s );
// 削除
int  Dary_Delete( hDary h, const char *s );

キーを検索,追加,削除するための関数です.

// 配列 BC の整理
int  Dary_AdjustBC( hDary h );
// 配列 TAIL の整理
int  Dary_AdjustTail( hDary h );

配列 BC, TAIL から無駄な領域を除去するための関数です.

// エラーメッセージ
void  Dary_Error( int code );

エラーコードに対応する文字列を stderr に出力する関数です.

Sample

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

To Do

余裕があれば,レコードの格納や Prefix Search などを実装しようと思っています.

References

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

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

森田和宏,泓田正雄,大野将樹,青江順一. ダブル配列におけるキー削除の効率化手法. 情報処理学会論文誌.Vol. 44.No. 5.pp. 1311-1320.2003.

大野将樹,森田和宏,泓田正雄,青江順一. ダブル配列による自然言語辞書の高速更新法. 言語処理学会第 11 回年次大会.P5-5.2005.

矢田晋,森田和宏,大野将樹,泓田正雄,吉成友子,青江順一. 接頭辞ダブル配列における空間効率を低下させないキー削除法. 情報処理学会論文誌.Vol. 47.No. 6.pp. 1894-1902.2006.

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

Back
Last-Modified: March 17, 2007