新しいトライのライブラリを公開しました

概要

トライのライブラリを公開しました．ドキュメントはまったく用意できていませんが，とりあえず使えます．（追記 2011-01-09）ドキュメントを追加しました．

インストール

ビルド・インストールの方法は configure と make です．以下のようにすればインストールできます．

./configure
make
make check
sudo make install

インストールせずに試したいという方は，make install を省略して，tools/ 内部のツールを使うなり，lib/marisa/trie.h を見て使い方を確認するなりしてください．インストールせずにライブラリを利用するには，lib/ 以下のヘッダすべてと lib/libmarisa.a が必要になります．

ツール

marisa-trie に含まれるツールは，今のところ marisa-build, marisa-lookup, marisa-find, marisa-predict, marisa-benchmark の 5 つです．オプション "-h" を与えて実行することにより，オプションの一覧を確認できます．

# コマンドの動作自体には問題ないものの，ヘルプの内容が少しおかしいことに気づきました．次のバージョンにて修正します．

先頭の 4 つは，それぞれ marisa::Trie のメソッドと以下のように対応しています．

  • ツールとメソッドの対応
    • marisa-build <-> marisa::Trie::build()
      • 辞書を構築します．
    • marisa-lookup <-> marisa::Trie::lookup
      • 完全一致検索をおこないます．
    • marisa-find <-> marisa::Trie::find
      • クエリの前半部分と一致するキーを検索します．
    • marisa-predict <-> marisa::Trie::predict
      • クエリで始まるキーを検索します．

日本語 Wikipedia のタイトル一覧をキー集合としてツールの動作を確認したところ，以下に示す結果となりました．

$ gzip -cd jawiki-20101102-all-titles-in-ns0.gz | marisa-build > jawiki.dic
#keys: 1146584
#tries: 3
#nodes: 2264302
size: 6522558

$ marisa-lookup jawiki.dic
あ
2578	あ

$ marisa-find jawiki.dic 
トライ
3 found
2462	ト	トライ
132331	トラ	トライ
500091	トライ	トライ

$ marisa-predict -n 3 jawiki.dic
あ
2342 found
2578	あ	あ
134977	あい	あ
855840	あいち健康の森	あ

残る marisa-benchmark は，辞書のサイズや構築・検索時間を調べるためのツールです．キー集合を入力として与えると，トライの数を変更しながら前述の項目を調べて出力します．多層トライの実験結果 - やた＠はてな日記 のような結果が得られます．

ライブラリ

ライブラリの名前は marisa で，インクルードすべきヘッダは marisa.h です．ドキュメントは用意できていないので，気になる方は marisa/trie.h や tests/trie-test.cc, tools/*.cc をご覧ください．

// a.cc
#include <marisa.h>
...

g++ -Wall -O2 a.cc -lmarisa