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 のコードを 改めてパッケージングしたものです.
% ./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
引数で個々に指定してください.
テンプレート引数に与えられた型の別名定義です. 外部から型名を参照する 時に使います.
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)
result_type
Darts::DoubleArrayImpl::exactMatchSearch(const key_type *key, size_t len
= 0, size_t node_pos = 0)
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)
result_t
Darts::DoubleArrayImpl::traverse (const key_type *key,
size_t &node_pos, size_t &key_pos, size_t len = 0)
int
Darts::DoubleArrayImpl::save(const char *file, const char *mode = "wb",
size_t offset = 0)
int
Darts::DoubleArrayImpl::open
(const char *file, const char *mode = "rb", size_t offset = 0,
size_t size = 0)
size_t
Darts::DoubleArrayImpl::size()
size_t
Darts::DoubleArrayImpl::unit_size()
size_t
Darts::DoubleArrayImpl::nonzero_size()
void
Darts::DoubleArrayImpl::set_array(void *ptr, size_t array_size = 0)
const void*
Darts::DoubleArrayImpl::array()
Darts::DoubleArrayImpl::clear()
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 DictionaryFile DoubleArrayFileソート済みの辞書を DoubleArrayFile に変換します.
% ./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 は問題ないようなので, このままの状態にしていますが, いずれ移植性を高めるために書きなおすつもりです.
$Id: index.html 1674 2008-03-22 11:21:34Z taku $;