これは何
Darts (Double-ARray Trie System) データ構造のトライ木 (Trie) の全単語をダンプするツール
あるいは
mkdarts した元の単語ファイルを失くしてしまった残念な人を救済するツール
インストールに必要なもの
実際に必要なのはdarts.hだけです。
インストール
darts.h が /usr/local/include にインストールされていることを前提としています。
そうでない場合は Makefile をいじってください。
darts.h にパッチをあてて使っています。
$ make dump_darts
$ sudo make install
使い方
$ dump_darts <darts-file>
開発動機
Darts を DAWG で置き換えたかったのだけれど、mkdarts した元の単語ファイルを失くしてしまったのですよ…
これを書いたおかげで double-array で Trie がどう実装されているのか自分なりに理解できたのが不幸中の幸い。
実装
darts.h の DArray::DoubleArrayImpl クラスに dump_all_keys() メソッドを追加する形で実装しています。
namespace Darts {
...
class DoubleArrayImpl {
...
void dump_all_keys(bool show_pos=false) {
std::vector<size_t> rev(size_);
std::vector<size_t> goals;
for (size_t i=0; i<size_; ++i) {
array_type_ base = array_[i].base;
if (base == 0) {
continue;
} else if (base < 0) {
goals.push_back(i);
continue;
}
if (array_[i].check == 0) continue;
rev[base] = i;
}
for (size_t i=0, sz=goals.size(); i<sz; ++i) {
array_type_ goal = array_[goals[i]].base; // goal < 0
array_u_type_ check = array_[goals[i]].check;
size_t here = rev[check];
std::vector<unsigned char> way;
while (true) {
array_u_type_ check = array_[here].check;
if (check == 0) break; // root
way.push_back(here - check - 1);
here = rev[check];
}
if (show_pos) printf("%d\t", -goal-1);
for (int i=way.size()-1; i>=0; --i) putchar(way[i]);
printf("\n");
}
}
...
};
...
}
#include <stdio.h>
#include "darts.h"
int main(int argc, char *argv[]) {
Darts::DoubleArray da;
if (argc != 2) {
printf("usage: %s <darts-file>\n", argv[0]);
return 0;
}
da.open(argv[1]);
da.dump_all_keys();
return 0;
}
やっている事は、array_[] を走査して base < 0 なノード（単語の終端。-base-1 でその単語が何番目のエントリなのかが分かる）から check を逆行し、array_[] 内の位置と check の値から文字コードを復号しつつ、Trie の根本までさかのぼっているだけです。
Trieの葉から根の方向へ１文字分遡る計算量を O(1) にするために、最初に array_[] の check の逆引き辞書を作っています。
全体の計算量は単語数を N、単語の平均長を L とすると O(NL) ですかね。
根に近づけば近づくほど多くの単語のプレフィックスが重複しているはずなので、復号した文字をキャッシュしておくなり何なりすれば O(NlogL) とかになるのかもですが、現状の実装で元の単語ファイルの復元という目的を果たしてしまったので放置します。
ライセンス
dump_darts はフリーソフトウェアです．
元の Darts に従い、LGPL(Lesser GNU General Public License) または BSD ライセンスに従って本ソフトウェアを使用、再配布することができるものとします。
詳細は COPYING, LGPL, BSD 各ファイルを参照して下さい。
作者
- naoya_t