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