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 のコードを 改めてパッケージングしたものです.

ダウンロード

Source

インストール

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

新着情報

使い方

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, const key_type **str, const size_t *len = 0, const 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 を用いて設定された メモリ領域への解放作業は行われません.

const 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

% ./mkdarts 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

参考文献, リンク


$Id: index.html 1674 2008-03-22 11:21:34Z taku $;