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.32.tar.gz: HTTP