Darts: Double-ARray Trie System

はじめに

Darts は, Double-Array [Aoe 1989]を構築するための シンプルな C++ Template Library です. Double-Array は Trie を表現するためのデータ構造です. ハッシュ木, デジタルトライ, パトリシア木, Suffix Array による擬似 Trieといった 他の Trie の実装に比べ高速に動作します. オリジナル の Double-Arrayは, 動的に key の追加削除を行えるような 枠組ですが, Darts は ソート済の辞書を一括してDouble-Array に変換することに機能を絞っています.

ハッシュのような単純な辞書として使うことも可能ですが, 形態素解析器の辞書に必須の Common Prefix Search を非常に高速に行うことができます.

2003年7月現在, Darts は, MeCab, ChaSen に採用されています. Darts は, MeCab で使 われている Double-Array のコードを 改めてパッケージングしたものです.

ダウンロード

• Darts はフリーソフトウェアです．LGPL(Lesser GNU General Public License) または BSD ライセンスに従って本ソフトウェアを使用,再配布することができます. 詳細は COPYING, LGPL, BSD各ファイルを参照して下さい．

Source

• darts-0.31.tar.gz: HTTP

インストール

% ./configure 
% make
% make check
% make install
あとは, /usr/local/include/darts.h を include して使う

新着情報

• 2007-01-27: darts 0.31
  
  • ライセンスをLGPLからBSD,LGPLのデュアルライセンスに変更
• 2005-12-25: darts 0.3
  
  • Double Array の作成時に不正特殊をアクセスする可能性があるバグを修正
  • メッソド名の一部変更 (setArray を set_array になど)
  • rpm パッケージ配布の停止
• 2003-8-3: darts 0.2
  
  • 特殊な検索文字列において, DoubleArray の未知領域をアクセスする可能性が あるバグを修正
  • DoubleArray のノードを traverse するメソッド traverse () を追加 (実験的)
  • setArray () にて DoubleArray のサイズを指定できるようになった
  • commonPrefixSearch のインタフェースが変更された. 検索結果のバッファサイズを指定できるようになり, 安全性が高まった.
• 2003-2-15: darts 0.1
  
  • rpm パッケージを用意した.
  • mkdarts darts を $(prefix)/libexec/darts 以下にインストールするようにした
• 2003-2-14: darts 0.09
  
  • open (FILE *), save (FILE *) インタフェイスの廃止 将来, C++ stream に変更する可能性があるため
  • make install した時に darts.h が $(prefix)/include にインストールさ れるようにした.
  • result_type, key_type という typedef を用意した.
• 2002-12-26: darts 0.08
  
  • zlib の関数を zlib namespace に入れる.
  • open, save の default mode を "rb", "wb" に変更
  • Darts::build の戻り値の変更
  • progress_func の 第一引数 (title の廃止)
• 2002-12-05: darts 0.07
  
  • progress func に NULL を指定を指定したときに core をはくbugを修正
• 2002-10-13: darts 0.06
  
  • gcc 3.2 への対応
    gcc 3.2 では, 正常なDoubleArray が作成できないバグを修正 (コンパイラのバグの可能性あり)
    宮田さんからの ご報告いただきました. ありがとうございます.
• 2002-04-23: darts 0.05
  
  • メソッド名の変更
• 2001-06-11: darts 0.04
  
  • mkdarts の辞書ファイルとして - が与えられた場合, 標準入力から辞書を読み込 むようにした.
  • configure option に --with-zlib or --without-zlib を追加
• 2001-05-24: darts 0.03
  
  • ライセンスが GPL になってた部分を修正. LGPL です.
• 2001-05-23: darts 0.02
  
  • 文字列終端と NULL文字の区別ができていなかったバグを修正. これにともない, index の互換性が無くなりました. 高岡さんら ご指摘をうけました. ありがとうございます.
  • zlib を使い Double-Array を圧縮する methodを追加 (experimental)
  • open,save の戻り値の変更, 標準的な UNIXに従い 0 を成功としました.
  • get_unit_size という Double-Array の各要素の size を取得する method を追加
• 2001-05-21: darts 0.01
  
  • Initial Release!

使い方

Darts は, darts.h を提供するのみの, C++ Template Library です. そのつど include して使用します.
inline 化による高速性を期待して, このような配布形態にしています.

クラスのインターフェイス

namespace Darts {

   template <class NodeType, class NodeUType class ArrayType, 
                class ArrayUType, class LengthFunc = Length<NodeType> >

   class DobuleArrayImpl
   {
    public:
     typedef ArrayType   result_type;
     typedef NodeType    key_type;

     DoubleArrayImpl();
     ~DoubleArrayImpl();

     int    set_array(void *ptr, size_t = 0);
     void   *array();
     void   clear();
     size_t size ();
     size_t unit_size ();
     size_t nonzero_size ();
     size_t total_size ();

     int build (size_t        key_size,
                key_type      **key,
                size_t        *len = 0,
                result_type   *val = 0,
                int (*pg)(size_t, size_t) = 0);

     int open (const char *file,
               const char *mode = "rb",
               size_t offset = 0,
               size_t _size = 0);

     int save (const char *file,
               const char *mode = "wb",
               size_t offset = 0);

     result_type exactMatchSearch (const key_type *key,
                                   size_t len = 0,
                                   size_t node_pos = 0)
      
     size_t commonPrefixSearch  (const key_type *key,
                                 result_type *result,
                                 size_t result_size,
                                 size_t len = 0,
                                 size_t node_pos = 0)

     result_type traverse (const key_type *key, 
                           size_t &node_pos, 
                           size_t &key_pos, 
                           size_t len = 0)
   };

   typedef Darts::DoubleArrayImpl<char, unsigned char,
              int, unsigned int> DoubleArray;
   // int, unsigned int は, プラットフォーム依存. 実際には, 32 bit 整数
   // になるように, configure が適切な型を選択する
};

テンプレート引数の説明

NodeType	Trie の各ノードの型です. 一般的な C 文字列の検索なら, char 以外に設定する必要はありません.
NodeUType	Trie の各ノードの型を符号無し整数に変換した型です. 一般的な C 文字列の検索なら, unsigned char 以外に設定する必要はありません.
ArrayType	Double-Array の Base の要素に使用される型です. 通常は signed の 32bit 整数に設定します
ArrayUType	Double-Array の Check の要素に使用される型です. 通常は unsigned の 32bit 整数に設定します
LengthFunc	NodeType の配列を引数にしたときに, その配列のサイズを返す関数オブジェクトを 指定します. 内部呼び出しに operator () を使っている ので, () を overload しておく必要があります. NodeType が, char の場合は, strlen を wrap した関数オブジェクトが, それ以外は 0 を終了条件とみなして配列のサイズを計算します.

32bit 整数の定義は OS, コンパイラ依存です.
実際には configure script が, 自動的に判別し,32bit になるように選択してくれます. もし64 bit 整数を用いる場合は, template 引数で個々に指定してください.

typedef の説明

テンプレート引数に与えられた型の別名定義です. 外部から型名を参照する 時に使います.

key_type	検索する key の 1つの要素の型です. NodeType と同一です.
result_type	1つの結果の型です. ArrayType と同一です.

メソッドの説明

int Darts::DoubleArrayImpl::build(size_t size, key_type **str, size_t *len = 0, result_type *val = 0, int (*progress_func)(size_t, size_t) = 0)

Double Array を構築します.

size には, 辞書のサイズ (いくつの単語を登録するか),
str には, 各単語へのポインタ (要素は size 個)
len は個々の単語のサイズの配列 (要素は size 個)
val には, 各単語に対応する値の配列 (要素は size 個)
progress_func には, 構築状況の表示に用いる関数へのポインタを指定します.
str の各要素は辞書順にソートされている必要があります.
また, val の各要素の中に, 負の要素はあってはいけません.
len, val, pg はそれぞれ省略可能です,
省略されると len には LengthFunc により計算された値が,
val には, 各要素が 0 から数えて何番目かをあらわす値が,
pg には, 何も表示を行なわないと解釈されます.


構築に成功すると, 0 が, 失敗すると 負の値が返ります.
表示関数 progress_func は, 2つの引数があります.
1つ目は size_t 型の整数で, 今まで構築した語彙の数,
2つ目も size_t 型の整数で全体の語彙の数です.
このような インタフェースを持つ関数へのポインタを渡すことで構築時の表示を 変更することができます.



result_type Darts::DoubleArrayImpl::exactMatchSearch(const key_type *key, size_t len = 0, size_t node_pos = 0)

exact match による検索を行います.

key には, 検索したい文字列を,
len には その文字列のサイズを,
node_pos には, Double-Array の検索開始位置を指定します.

len, と node_pos はそれぞれ省略可能で, 省略されると len には LengthFunc により計算された値が使用され,
node_pos は, root ノードとなります.

戻り値として, 検索に成功した場合はその key に対応する値が, 失敗したら -1 が返ってきます.



size_t Darts::DoubleArrayImpl::commonPrefixSearch (const key_type *key, result_type *result, size_t result_size, size_t len = 0, size_t node_pos = 0)

common prefix search による検索を行います.

key には, 検索したい文字列を,
result は, 検索後, マッチした複数の結果値を格納するための配列を,
result_size は, 配列 result のサイズを,
len には 検索文字列のサイズを,
node_pos には, Double-Array の検索開始位置を指定します.

len, と node_pos はそれぞれ省略可能で, 省略されると len には LengthFunc により計算された値が使用され,
node_pos は, root ノードとなります.

戻り値として, マッチした要素の個数が返ってきます. 各要素の実際の値は, result を参照することで得られます. マッチした要素の個数が, result_size を越えた場合は, result_size 個だけ 配列 result に結果を格納します. 戻り値は, 実際にマッチした個数なので, result_size を越えた場合は, result のサイズを増やし, 再検索してください.



result_t Darts::DoubleArrayImpl::traverse (const key_type *key, size_t &node_pos, size_t &key_pos, size_t len = 0)

Trie を traverse します

key には, 検索したい文字列を,
node_pos, には, DoubleArray の検索位置を,
key_pos には, 検索文字列の, 検索開始位置を,
len には, 検索文字列のサイズを指定します.

traverse のプロセスとは, key に従って TRIE を辿っていくことを差します.
ただし, 最後に辿った Trie 中の node の位置, 最後に辿った検索文字列の位置(何番目の文字)を得ることができます. これが, exactMatchSearch との違いになります.

node_pos は通常 root の位置 (0) を指定しておきます. node_pos は, 参照となっています. 関数呼び出し後, node_pos の値を 参照することで, traverse 後の, DoubleArray の位置が得られます.
key_pos は通常先頭の位置 (0) を指定しておきます. key_pos も, 参照となっています. 関数呼び出し後, key_pos の値を 参照することで, traverse 後の, 文字列の位置が得られます.

探索に失敗した場合は, 負の値 (-1) or (-2) を返します.
-1 は, leaf で失敗, -2 は, 途中の node で失敗を示します.
探索に成功した場合は, key に対応する value を返します.



int Darts::DoubleArrayImpl::save(const char *file, const char *mode = "wb", size_t offset = 0)

Double-Array をファイルに保存します.

file には, 保存先のファイル名を,
mode には, fopen(3) に用いられる modeを指定します.
offset は将来のために予約されていて, 現在は使用されていません.

戻り値には 成功すれば, 0 が, 失敗すれば -1 が返ってきます.



int Darts::DoubleArrayImpl::open (const char *file, const char *mode = "rb", size_t offset = 0, size_t size = 0)

Double-Array をファイルから読みこみます.

file には読みこむファイル名を,
mode には fopen(3) に用いられるmodeを,
offset には, ファイルの 何 byte 目から読むかの offset 情報を,
size には, 実際に 何 byte 読むのかを指定します.

size が 0 (デフォルト値) の場合は, size = ファイルサイズとなります.

戻り値には 成功すれば, 0 が, 失敗すれば -1 が返ってきます.



size_t Darts::DoubleArrayImpl::size()

Double-Array のサイズを返します.



size_t Darts::DoubleArrayImpl::unit_size()

Double-Array の1要素のサイズを返します.

size() * unit_size() が, Double-Array を保持するのに必要なメモリ のサイズになります.



size_t Darts::DoubleArrayImpl::nonzero_size()

Double-Array の各要素のうち, 使用領域のサイズを返します.
nonezero_size()/size() にて, 圧縮率が計算できます.



void Darts::DoubleArrayImpl::set_array(void *ptr, size_t array_size = 0)

ptr を Double-Array と解釈して Double-Array への pointer に代入します.
これは, mmap(2) を用い, 保存済みの Double-Array への pointer を取得し,
その値を外部からセットする目的で用意されています. 見てのとおり 非常に ad-hoc な methodです.

また, array_size にて, Double-Array のサイズ (size() の戻り値) を指定することができます.
このサイズは, Double-Array のサイズであって, メモリのサイズではありません. array_size * unit_size () が, 実際のメモリサイズです. ご注意下さい.

この method を用いて設定された メモリ領域への解放作業は行われません.



void* Darts::DoubleArrayImpl::array()

Double Array を 生の void ポインタとして取得します.
この領域は, DoubleArray のインスタンスが管理しており, 扱いには注意が必要です.



Darts::DoubleArrayImpl::clear()

保持している, Double-Array を解放します.

サンプルプログラミング

static な辞書から Double-Arrayを構築する.

#include <iostream>
#include <darts.h>

int main (int argc, char **argv)
{
  using namespace std;

  Darts::DoubleArray::key_type   *str[] = { "ALGOL", "ANSI", "ARCO",  "ARPA", "ARPANET", "ASCII" }; // same as char*
  Darts::DobuleArray::result_type val[] = { 1, 2, 3, 4, 5, 6 }; // same as int 

  Darts::DoubleArray da;
  da.build (6, str, 0, val); 

  cout << da.exactMatchSearch("ALGOL") << endl;
  cout << da.exactMatchSearch("ANSI") << endl;
  cout << da.exactMatchSearch("ARCO") << endl;;
  cout << da.exactMatchSearch("ARPA") << endl;;
  cout << da.exactMatchSearch("ARPANET") << endl;;
  cout << da.exactMatchSearch("ASCII") << endl;;
  cout << da.exactMatchSearch("APPARE") << endl;

  da.save("some_file");
}

実行結果
1
2
3
4
5
6
-1

標準入力から対話的に Double-Array に対し Common Prefix Search を行う

#include <iostream>
#include <string>
#include <algorithm>
#include <darts.h>

int main (int argc, char **argv)
{
  using namespace std;

  Darts::DoubleArray da;
  if (da.open("some_file") == -1) return -1;

  Darts::DoubleArray::result_type  r [1024];
  Darts::DoubleArray::key_type     buf [1024];

  while (cin.getline (buf, 1024)) {
    size_t result = da.commonPrefixSearch(buf, r, 1024);
    if (result == 0) {
       cout << buf << ": not found" << endl;
    } else {
       cout << buf << ": found, num=" << result << " ";
       copy (r, r + result, ostream_iterator<Darts::DoubleArray::result_type>(cout, " "));
       cout << endl;
    }
  }

  return 0;
}

他のサンプルとして, mkdarts.cpp や darts.cpp をご覧ください

付属プログラムの説明

mkdarts

% ./mkdart DictionaryFile DoubleArrayFile 

ソート済みの辞書を DoubleArrayFile に変換します.

darts

% ./darts DoubleArrayFile 

DoubleArrayFile に対し対話的に common prefix search を行います.
サンプルプログラムの 2番目とほぼ同じです.

使用例

% cd tests
% head -10 linux.words
ALGOL
ANSI
ARCO
ARPA
ARPANET
ASCII
 .. 

% ../mkdarts linux.words dar
Making Double Array: 100% |*******************************************|
Done!, Compression Ratio: 94.6903 %

% ../darts dar
Linux
Linux: found, num=2 3697 3713
Windows
Windows: not found
LaTeX
LaTeX: found, num=1 3529

既知の問題

構造体の表現方法

Double-Array は,

struct Unit
{
   ArrayType    base;
   ArrayUType   check;
};

のような Unit の配列として表現されています. このファイルの入出力は, fread, fwrite を用いて,

fread  ((Unit *)array,  sizeof(Unit), size, fp);
fwrite ((Unit *)array,  sizeof(Unit), size, fp);

のように, 行われています. ごくまれですが, 構造体の配列の間に gap を挿入 する OS/コンパイラがあるそうです. したがって, このような読み書きは厳密に言えば移植性がありません. 私が使用している g++ 2.95.2 と Tru64 に附属の cxx は問題ないようなので, このままの状態にしていますが, いずれ移植性を高めるために書きなおすつもりです.

TODO

• Double-Array の解説文書の作成
• 幅優先の格納を考える
• 一部 vector <> を使ってる部分を駆逐
• 英語のマニュアルを書く
• 動的な削除と追加をサポート

参考文献, リンク

• [Aoe1989] Aoe, J. An Efficient Digital Search Algorithm by Using a Double-Array Structure. IEEE Transactions on Software Engineering. Vol. 15, 9 (Sep 1989). pp. 1066-1077.
• [Datrie] Theppitak Karoonboonyanan An Implementation of Double-Array Triehttp://www.links.nectec.or.th/~thep/datrie/
• [単語と辞書] 松本裕治 ほか. 単語と辞書 岩波講座言語の科学 Vol.3 pp.79-81

---

$Id: index.html 1575 2007-01-27 13:24:27Z taku $;