|
Packit |
de3218 |
|
|
Packit |
de3218 |
<html lang="ja">
|
|
Packit |
de3218 |
<head>
|
|
Packit |
de3218 |
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
|
|
Packit |
de3218 |
<title>MARISA: Matching Algorithm with Recursively Implemented StorAge</title>
|
|
Packit |
de3218 |
<link rel="stylesheet" type="text/css" href="./style.css">
|
|
Packit |
de3218 |
</head>
|
|
Packit |
de3218 |
<body>
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
MARISA: Matching Algorithm with Recursively Implemented StorAge
|
|
Packit |
de3218 |
Last modified: 13 April 2013
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
MARISA: Matching Algorithm with Recursively Implemented StorAge
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
Abstract:
|
|
Packit |
de3218 |
Matching Algorithm with Recursively Implemented StorAge (MARISA) は Trie をコンパクトに表現する程度の能力を持つデータ構造です．libmarisa は MARISA を C++ で実装したライブラリであり，MARISA による辞書を構築したり，辞書からの検索をおこなったりできます．libmarisa の基本的な機能に対応するコマンドラインツールを用意しているので，辞書のサイズがどのくらいになるのか，検索にどのくらい時間がかかるのか，などを手軽に試すことができます．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
Matching Algorithm with Recursively Implemented StorAge (MARISA) は Trie に対するコンパクトなデータ構造であり，動的な更新には対応していないものの，高い空間効率とそれなりの時間効率を実現できます．また，Trie の特徴を引き継いでいるため，MARISA による辞書は，単純な辞書引きだけでなく，逆引き，Common Prefix Search や Predictive Search を効率良く実現できます．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
ほとんどの場合，MARISA による辞書は，登録文字列の集合を連結してできるテキストと比べて，ずっとコンパクトになります．そのため，登録文字列をそのまま保持する標準的な二分探索木やハッシュ表と比べると，ずーっとコンパクトです．一方で，確率的なデータ構造である Bloom Filter と比べてみると，空間効率の面では劣りますが，False Positive がなく，逆引きに加えて Common Prefix Search や Predictive Search を効率良く実現できることが特徴になります．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
libmarisa は MARISA を C++ で実装したライブラリであり，MARISA による辞書を構築したり，辞書からの検索をおこなったりできます．libmarisa の基本的な機能に対応するコマンドラインツールを用意しているので，辞書のサイズがどのくらいになるのか，検索にどのくらい時間がかかるのか，などを手軽に試すことができます．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
libmarisa による辞書の構築では，登録文字列に 0 から順に固有の ID を割り当てるようになっています．ID は自動的に割り当てられるので，登録文字列に任意の ID を割り当てることはできません．検索においては，文字列あるいは ID をクエリとして受け取り，適合する登録文字列と ID の組を検索結果として返すようになっています．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
辞書引き（Lookup）
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
入力文字列が登録されているかどうかを確認します．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
逆引き（Reverse Lookup）
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
入力された ID から登録文字列を復元します．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
Common Prefix Search
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
入力文字列の前半部分に一致する登録文字列を検索します．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
Predictive Search
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
入力文字列で始まる登録文字列を検索します．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
libmarisa および付属のコマンドラインツールはフリーソフトウェアです．使用・再配布については，二条項 BSD ライセンスと LGPL のデュアルライセンスを採用しています．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
プロジェクトの管理やソースコードの配布には Google Project Hosting を利用しています．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
プロジェクト
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
http://code.google.com/p/marisa-trie/
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
ソースコード
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
marisa-0.2.4.tar.gz
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
$ tar zxf marisa-0.2.4.tar.gz
|
|
Packit |
de3218 |
$ cd marisa-0.2.4
|
|
Packit |
de3218 |
$ ./configure
|
|
Packit |
de3218 |
$ make
|
|
Packit |
de3218 |
$ make check
|
|
Packit |
de3218 |
$ make install
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
configure と make によりインストールできるようになっています．make install については，必要に応じて sudo を付けてご利用ください．また，特に指定がなければ libmarisa は共有ライブラリとしてインストールされるので，ldconfig が必要になるかもしれません．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
POPCNT 命令が使える環境では，configure に --enable-popcnt を渡すことで，少し高速化することができます．同様に，--enable-sse2, --enable-sse3, --enable-ssse3, --enable-sse4.1, --enable-sse4.2, --enable-sse4, --enable-sse4a というオプションがあります．また，スタティックライブラリが必要なときは，configure に --enable-static を渡すようにしてください．その他，configure のオプションについては ./configure --help をご覧ください．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
Visual C++ 2008 にて作成したファイルを vs2008/ 以下に配置しています．Visual C++ 2008 以降であれば，vs2008/vs2008.sln を開くだけでスタティックライブラリ libmarisa.lib とコマンドラインツールをビルドできます．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
Visual C++ 2008 より古い環境では，新しくプロジェクトを作る必要があります．プロジェクトを作成すれば問題なくビルドできると思いますが，試していないので断言はできません．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
$ cd bindings/perl
|
|
Packit |
de3218 |
$ perl Makefile.PL
|
|
Packit |
de3218 |
$ make
|
|
Packit |
de3218 |
$ make install
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
SWIG による Perl バインディングが bindings/perl/ にあります．perl Makefile.PL により Makefile を作成し，make install を実行することでインストールできます．使い方については，bindings/perl/sample.pl を参考にしてください．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
$ cd bindings/python
|
|
Packit |
de3218 |
$ python setup.py build
|
|
Packit |
de3218 |
$ python setup.py install
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
SWIG による Python バインディングが bindings/python/ にあります．python setup.py install により インストールできます．使い方については，bindings/python/sample.py を参考にしてください．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
$ cd bindings/ruby
|
|
Packit |
de3218 |
$ ruby extconf.rb
|
|
Packit |
de3218 |
$ make
|
|
Packit |
de3218 |
$ make install
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
SWIG による Ruby バインディングが bindings/ruby/ にあります．ruby extconf.rb により Makefile を作成し，make install を実行することでインストールできます．使い方については，bindings/ruby/sample.rb を参考にしてください．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
上記のバインディング以外にも，高速・高機能な Python バインディング や Node.js から使うためのモジュール が開発されています．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
$ marisa-build < keyset.txt > keyset.dic
|
|
Packit |
de3218 |
#keys: 1342099
|
|
Packit |
de3218 |
#nodes: 1832373
|
|
Packit |
de3218 |
size: 7841664
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
marisa-build は辞書を構築するツールです．改行を区切りとして文字列を受け取り，構築した辞書を標準出力に書き出すようになっています．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
構築する辞書のパラメータについては，オプションを使って指定できます．オプションの一覧は marisa-build -h により確認できます．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
入力は改行区切りとなっていますが，水平タブが存在する行については，最後の水平タブ以降を文字列の重みとして扱うようになっています．文字列の出現頻度や出現確率を与えることにより，検索時間を短縮できる可能性があります．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
$ marisa-lookup keyset.dic
|
|
Packit |
de3218 |
東方
|
|
Packit |
de3218 |
174385 東方
|
|
Packit |
de3218 |
とうほう
|
|
Packit |
de3218 |
-1 とうほう
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
marisa-lookup は単純な辞書引きをおこなうツールです．入力された文字列が登録されていれば ID とともに出力し，登録されていなければ -1 とともに出力します．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
オプションの一覧は marisa-lookup -h により確認できます．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
$ marisa-reverse-lookup keyset.dic
|
|
Packit |
de3218 |
800000
|
|
Packit |
de3218 |
800000 紀元前475年
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
marisa-reverse-lookup は辞書に登録されている文字列を ID から復元するツールです．登録文字列には 0 から順に固有の ID が割り当てられるので，指定できる値は 0 以上で登録文字列数より小さい整数となります．範囲外の値を入力するとエラーになるので注意してください．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
オプションの一覧は marisa-reverse-lookup -h により確認できます．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
$ marisa-common-prefix-search keyset.dic
|
|
Packit |
de3218 |
東方
|
|
Packit |
de3218 |
2 found
|
|
Packit |
de3218 |
3542 東 東方
|
|
Packit |
de3218 |
174385 東方 東方
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
marisa-common-prefix-search は Common Prefix Search をおこなうツールです．入力された文字列の前半部分に一致する登録文字列を ID とともに出力します．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
オプションの一覧は marisa-common-prefix-search -h により確認できます．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
$ marisa-predictive-search keyset.dic -n 2
|
|
Packit |
de3218 |
東方
|
|
Packit |
de3218 |
200 found
|
|
Packit |
de3218 |
174385 東方 東方
|
|
Packit |
de3218 |
639679 東方文花帖 東方
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
marisa-predictive-search は Predictive Search をおこなうツールです．入力された文字列で始まる登録文字列を ID とともに出力します．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
オプションの一覧は marisa-predictive-search -h により確認できます．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
$ marisa-benchmark keyset.txt
|
|
Packit |
de3218 |
Number of tries: 1 - 5
|
|
Packit |
de3218 |
TAIL mode: Text mode
|
|
Packit |
de3218 |
Node order: Descending weight order
|
|
Packit |
de3218 |
Cache level: Normal cache
|
|
Packit |
de3218 |
Number of keys: 1342099
|
|
Packit |
de3218 |
Total length: 28308027
|
|
Packit |
de3218 |
------+----------+--------+--------+--------+--------+--------
|
|
Packit |
de3218 |
#tries size build lookup reverse prefix predict
|
|
Packit |
de3218 |
lookup search search
|
|
Packit |
de3218 |
[bytes] [K/s] [K/s] [K/s] [K/s] [K/s]
|
|
Packit |
de3218 |
------+----------+--------+--------+--------+--------+--------
|
|
Packit |
de3218 |
1 11588904 506.45 1187.70 1109.17 1040.39 596.49
|
|
Packit |
de3218 |
2 8467920 424.71 699.01 677.83 636.07 300.25
|
|
Packit |
de3218 |
3 7841664 405.47 615.64 601.84 563.91 254.67
|
|
Packit |
de3218 |
4 7633584 399.43 593.85 583.52 545.57 242.69
|
|
Packit |
de3218 |
5 7548584 395.90 526.31 563.91 504.55 236.70
|
|
Packit |
de3218 |
------+----------+--------+--------+--------+--------+--------
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
marisa-benchmark は，marisa-build と同様の入力を受け取り，辞書のサイズや構築・検索にかかる時間を調べるツールです．辞書を構成する Trie の数を選択するのに有用です．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
検索時間については，入力された文字列を一通り検索するのに要した時間を std::clock() で計測した結果を出力します．文字列を整列してから入力とした場合はキャッシュが効きやすい状況での検索時間になり，文字列をランダムに並べ替えてから入力とした場合はキャッシュが効きにくい状況での検索時間になります．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
オプションの一覧は marisa-benchmark -h により確認できます．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
$ marisa-dump keyset.dic | head -3
|
|
Packit |
de3218 |
input: keyset.dic
|
|
Packit |
de3218 |
フ
|
|
Packit |
de3218 |
ファ
|
|
Packit |
de3218 |
ファン
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
marisa-dump は辞書に登録されている文字列をすべて出力するツールです．デフォルトの区切り文字は改行（LF）ですが，オプションにより変更することができます．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
オプションの一覧は marisa-dump -h により確認できます．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
// sample.cc
|
|
Packit |
de3218 |
#include <iostream>
|
|
Packit |
de3218 |
#include <marisa.h>
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
int main() {
|
|
Packit |
de3218 |
marisa::Keyset keyset;
|
|
Packit |
de3218 |
keyset.push_back("a");
|
|
Packit |
de3218 |
keyset.push_back("app");
|
|
Packit |
de3218 |
keyset.push_back("apple");
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
marisa::Trie trie;
|
|
Packit |
de3218 |
trie.build(keyset);
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
marisa::Agent agent;
|
|
Packit |
de3218 |
agent.set_query("apple");
|
|
Packit |
de3218 |
while (trie.common_prefix_search(agent)) {
|
|
Packit |
de3218 |
std::cout.write(agent.key().ptr(), agent.key().length());
|
|
Packit |
de3218 |
std::cout << ": " << agent.key().id() << std::endl;
|
|
Packit |
de3218 |
}
|
|
Packit |
de3218 |
return 0;
|
|
Packit |
de3218 |
}
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
$ g++ sample.cc -lmarisa
|
|
Packit |
de3218 |
$ ./a.out
|
|
Packit |
de3218 |
a: 0
|
|
Packit |
de3218 |
app: 1
|
|
Packit |
de3218 |
apple: 2
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
libmarisa のヘッダは marisa.h です．名前空間には marisa を使っています．危険なので，using namespace marisa とするのは避けてください．最後に，gcc や clang によるリンクでは -lmarisa が必要となることに注意してください．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
libmarisa の主要なクラスは Keyset, Agent, Trie の 3 つです．サンプルコードでは明示的に使っていませんが，例外のクラスとして Exception があるほか，Keyset, Agent のメンバとして Key や Query が存在します．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
Keyset: 文字列の集合を格納するクラスです．辞書を構築するときの入力として使うほか，検索結果の保存にも利用できます．
|
|
Packit |
de3218 |
Agent: 検索の入出力と途中経過を格納するクラスです．検索用の関数はすべて Agent への参照を引数とします．
|
|
Packit |
de3218 |
Trie: 辞書のクラスです．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
コマンドラインツールのソースコードが tools/ にあり，例外処理やファイル入出力，Predictive Search などのサンプルとして利用できます．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
エラーコード
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
typedef enum marisa_error_code_ {
|
|
Packit |
de3218 |
MARISA_OK = 0,
|
|
Packit |
de3218 |
MARISA_STATE_ERROR = 1,
|
|
Packit |
de3218 |
MARISA_NULL_ERROR = 2,
|
|
Packit |
de3218 |
MARISA_BOUND_ERROR = 3,
|
|
Packit |
de3218 |
MARISA_RANGE_ERROR = 4,
|
|
Packit |
de3218 |
MARISA_CODE_ERROR = 5,
|
|
Packit |
de3218 |
MARISA_RESET_ERROR = 6,
|
|
Packit |
de3218 |
MARISA_SIZE_ERROR = 7,
|
|
Packit |
de3218 |
MARISA_MEMORY_ERROR = 8,
|
|
Packit |
de3218 |
MARISA_IO_ERROR = 9,
|
|
Packit |
de3218 |
MARISA_FORMAT_ERROR = 10,
|
|
Packit |
de3218 |
} marisa_error_code;
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
libmarisa では，ファイル入出力に失敗したときや辞書のサイズが上限に到達したときなどに，Exception を送出します．そして，Exception に格納される情報の 1 つが marisa_error_code です．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
辞書の入出力に関するエラーコードである MARISA_IO_ERROR と MARISA_FORMAT_ERROR 以外については，バグによる可能性が高いと思います．各エラーコードの詳細については，marisa/base.h をご覧ください．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
トライの数
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
typedef enum marisa_num_tries_ {
|
|
Packit |
de3218 |
MARISA_MIN_NUM_TRIES = 0x00001,
|
|
Packit |
de3218 |
MARISA_MAX_NUM_TRIES = 0x0007F,
|
|
Packit |
de3218 |
MARISA_DEFAULT_NUM_TRIES = 0x00003,
|
|
Packit |
de3218 |
} marisa_num_tries;
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
MARISA は複数の Patricia Trie を組み合わせて 1 つの Trie を構成することが特徴の 1 つであり，Patricia Trie の数を増やすほど，辞書はコンパクトになるものの，検索が遅くなるという傾向があります．marisa_num_tries では，辞書を構成する Patricia Trie の数について，最小値・最大値とデフォルトの値を提供します．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
適切な設定は登録文字列やアプリケーションによって異なります．ほとんどの場合はデフォルトの設定で問題ないと思いますが，検索時間が問題になるときは，思い切って 1 にしてください．また，登録文字列が長くて少し複雑な構成になる場合，デフォルトより大きな値にすることで，辞書のサイズをさらに小さくできることがあります．設定が気になるときは，marisa-benchmark をお試しください．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
キャッシュのサイズ
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
typedef enum marisa_cache_level_ {
|
|
Packit |
de3218 |
MARISA_HUGE_CACHE = 0x00080,
|
|
Packit |
de3218 |
MARISA_LARGE_CACHE = 0x00100,
|
|
Packit |
de3218 |
MARISA_NORMAL_CACHE = 0x00200,
|
|
Packit |
de3218 |
MARISA_SMALL_CACHE = 0x00400,
|
|
Packit |
de3218 |
MARISA_TINY_CACHE = 0x00800,
|
|
Packit |
de3218 |
MARISA_DEFAULT_CACHE = MARISA_NORMAL_CACHE
|
|
Packit |
de3218 |
} marisa_cache_level;
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
libmarisa では，検索時間の短縮を目的として，辞書にキャッシュを埋め込むようになっています．キャッシュの内容は通過する確率の高い遷移に関する情報であり，キャッシュを大きくすることによって，辞書は大きくなるものの，検索時間を短縮できます．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
marisa_cache_level は，キャッシュのサイズを制御するための定数を提供します．MARISA_NORMAL_CACHE を基準として，MARISA_LARGE_CACHE は 2 倍，MARISA_HUGE_CACHE は 4 倍になり，MARISA_SMALL_CACHE は 1/2，MARISA_TINY_CACHE は 1/4 になります．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
TAIL の種類
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
typedef enum marisa_tail_mode_ {
|
|
Packit |
de3218 |
MARISA_TEXT_TAIL = 0x01000,
|
|
Packit |
de3218 |
MARISA_BINARY_TAIL = 0x02000,
|
|
Packit |
de3218 |
MARISA_DEFAULT_TAIL = MARISA_TEXT_TAIL,
|
|
Packit |
de3218 |
} marisa_tail_mode;
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
libmarisa による辞書では，最後の Patiricia Trie について，ラベルをそのまま保存するようになっています．marisa_tail_mode はラベルの保存方法を選ぶためのパラメータです．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
MARISA_TEXT_TAIL はラベルを '\0' を終端とする文字列として保存します．そのため，ラベルに '\0' が含まれるときは，自動的に MARISA_BINARY_TAIL へと切り替わるようになっています．明示的に MARISA_BINARY_TAIL を選ぶ理由はほとんどありません．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
一方，MARISA_BINARY_TAIL では，ラベルの終端を検出するために，'\0' の代わりにビット列を使用します．そのため，ラベルの平均長が 8 bytes を超えるときは MARISA_TEXT_TAIL の方がコンパクトになります．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
ノードの順序
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
typedef enum marisa_node_order_ {
|
|
Packit |
de3218 |
MARISA_LABEL_ORDER = 0x10000,
|
|
Packit |
de3218 |
MARISA_WEIGHT_ORDER = 0x20000,
|
|
Packit |
de3218 |
MARISA_DEFAULT_ORDER = MARISA_WEIGHT_ORDER,
|
|
Packit |
de3218 |
} marisa_node_order;
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
libmarisa では，ノードの順序が辞書のパラメータになっています．選択肢は MARISA_LABEL_ORDER と MARISA_WEIGHT_ORDER の 2 つであり，前者はラベルが昇順になるようにノードを配列し，後者は重み（出現しやすさ）が降順になるようにノードを配列します．一般的な Trie の実装では MARISA_LABEL_ORDER の順序を用いますが，libmarisa では MARISA_WEIGHT_ORDER がデフォルトになっています．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
MARISA_WEIGHT_ORDER の目的は，出現しやすいノードから順に並べておくことにより，線形探索の効率を高め，検索時間を短縮することにあります．日本語の単語やフレーズを用いた実験においては，辞書引きにかかる時間を 1/2 程度に短縮できることが確認されています．一方，MARISA_LABEL_ORDER については，検索時間は長くなるものの，Predictive Search の検索結果が文字列昇順になるという特徴があります．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
別名
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
namespace marisa {
|
|
Packit |
de3218 |
typedef ::marisa_error_code ErrorCode;
|
|
Packit |
de3218 |
typedef ::marisa_cache_level CacheLevel;
|
|
Packit |
de3218 |
typedef ::marisa_tail_mode TailMode;
|
|
Packit |
de3218 |
typedef ::marisa_node_order NodeOrder;
|
|
Packit |
de3218 |
} // namespace marisa
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
以上の列挙型については，マクロとの衝突を避けるために，グローバル名前空間にて定義しています．namespace marisa に別名を用意しているので，お好きな方をご利用ください．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
class Exception {
|
|
Packit |
de3218 |
public:
|
|
Packit |
de3218 |
const char *filename() const;
|
|
Packit |
de3218 |
int line() const;
|
|
Packit |
de3218 |
ErrorCode error_code() const;
|
|
Packit |
de3218 |
const char *error_message() const;
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
const char *what() const;
|
|
Packit |
de3218 |
};
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
Exception は libmarisa が例外として送出するクラスです．エラーが検出されたファイルの名前（__FILE__）と行番号（__LINE__），さらにエラーコードを取り出せるようになっています．what() は使いやすさのために用意した関数であり，error_message() と同じく，__FILE__:__LINE__: error_code: error_message という書式の文字列を返します．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
class Key {
|
|
Packit |
de3218 |
public:
|
|
Packit |
de3218 |
char operator[](std::size_t i) const;
|
|
Packit |
de3218 |
const char *ptr() const;
|
|
Packit |
de3218 |
std::size_t length() const;
|
|
Packit |
de3218 |
std::size_t id() const;
|
|
Packit |
de3218 |
};
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
Key は後述する Keyset および Agent のメンバになっているクラスです．登録しようとしている文字列や，検索で見つけた登録文字列の情報を格納するために使われています．基本的な使い方では，既に情報が格納されたインスタンスのみを目にすることになります．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
class Query {
|
|
Packit |
de3218 |
public:
|
|
Packit |
de3218 |
char operator[](std::size_t i) const;
|
|
Packit |
de3218 |
const char *ptr() const;
|
|
Packit |
de3218 |
std::size_t length() const;
|
|
Packit |
de3218 |
std::size_t id() const;
|
|
Packit |
de3218 |
};
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
Query は後述する Agent のメンバになっているクラスです．検索しようとしている文字列や参照したい登録文字列の ID を格納するようになっています．Query に対する文字列や ID の設定は Agent を介しておこなうため，基本的な使い方では，意識する必要はありません．内容を確認したいときに参照する程度です．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
class Keyset {
|
|
Packit |
de3218 |
public:
|
|
Packit |
de3218 |
Keyset();
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
void push_back(const Key &key);
|
|
Packit |
de3218 |
void push_back(const Key &key, char end_marker);
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
void push_back(const char *str);
|
|
Packit |
de3218 |
void push_back(const char *ptr,
|
|
Packit |
de3218 |
std::size_t length,
|
|
Packit |
de3218 |
float weight = 1.0);
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
const Key &operator[](std::size_t i) const;
|
|
Packit |
de3218 |
Key &operator[](std::size_t i);
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
std::size_t num_keys();
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
bool empty() const;
|
|
Packit |
de3218 |
std::size_t size() const;
|
|
Packit |
de3218 |
std::size_t total_length() const;
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
void reset();
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
void clear();
|
|
Packit |
de3218 |
void swap(Keyset &rhs);
|
|
Packit |
de3218 |
};
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
概要
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
Keyset は辞書に登録しようとしている文字列もしくは登録されている文字列を詰め込むためのクラスです．辞書を構築するときの入力として，あるいは検索結果を保存しておくために使います．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
辞書の構築
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
辞書の構築に使う場合，push_back() で登録したい文字列を追加してから，後述する Trie の build() に渡します．weight は文字列の出現しやすさを示す重みであり，同じ文字列を繰り返し追加した場合，辞書を構築する段階で加算されるようになっています．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
辞書を構築した後は，operator[]() により登録文字列の ID を確認できます．その代わり，Key は重みと ID を共用体のメンバとして持つため，辞書の構築に使用した重みを参照できなくなります．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
検索結果の保存
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
検索結果の保存に使う場合，後述する Agent に格納されている検索結果を push_back() に渡すことで，文字列を複製し，ID を残しておくことができます．検索結果の文字列に終端記号を加えたいときは end_marker を利用してください．文字列の長さには影響を与えず，end_marker を終端文字として加えることができます．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
検索結果を破棄して別の検索結果を保存するために再利用するという場合，clear() の代わりに reset() を使うことで，既に確保している領域を再利用できます．メモリの確保・解放にかかるオーバーヘッドが気になるときにご利用ください．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
empty() は文字列が格納されていないかどうかを返す関数です．size() は num_keys() と同じく格納されている文字列の数を返す関数であり，total_length() は格納されている文字列の合計長を byte 単位で返す関数です．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
class Agent {
|
|
Packit |
de3218 |
public:
|
|
Packit |
de3218 |
Agent();
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
const Query &query() const;
|
|
Packit |
de3218 |
const Key &key() const;
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
void set_query(const char *str);
|
|
Packit |
de3218 |
void set_query(const char *ptr,
|
|
Packit |
de3218 |
std::size_t length);
|
|
Packit |
de3218 |
void set_query(std::size_t key_id);
|
|
Packit |
de3218 |
};
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
Agent は Query と Key をメンバとして持つクラスです．検索における入出力の受け渡し，および途中経過の保存に使います．後述する Trie の検索関数は，例外なく Agent への参照を引数として受け取るようになっています．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
検索の手順は，set_query() を使って検索したい文字列もしくは参照したい登録文字列の ID を設定し，Trie の関数に渡した後，key() により検索結果を取り出すという流れになります．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
class Trie {
|
|
Packit |
de3218 |
public:
|
|
Packit |
de3218 |
Trie();
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
void build(Keyset &keyset,
|
|
Packit |
de3218 |
int config_flags = 0);
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
void mmap(const char *filename);
|
|
Packit |
de3218 |
void map(const void *ptr,
|
|
Packit |
de3218 |
std::size_t size);
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
void load(const char *filename);
|
|
Packit |
de3218 |
void read(int fd);
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
void save(const char *filename) const;
|
|
Packit |
de3218 |
void write(int fd) const;
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
bool lookup(Agent &agent) const;
|
|
Packit |
de3218 |
void reverse_lookup(Agent &agent) const;
|
|
Packit |
de3218 |
bool common_prefix_search(Agent &agent) const;
|
|
Packit |
de3218 |
bool predictive_search(Agent &agent) const;
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
std::size_t num_tries() const;
|
|
Packit |
de3218 |
std::size_t num_keys() const;
|
|
Packit |
de3218 |
std::size_t num_nodes() const;
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
TailMode tail_mode() const;
|
|
Packit |
de3218 |
NodeOrder node_order() const;
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
bool empty() const;
|
|
Packit |
de3218 |
std::size_t size() const;
|
|
Packit |
de3218 |
std::size_t io_size() const;
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
void clear();
|
|
Packit |
de3218 |
void swap(Trie &rhs);
|
|
Packit |
de3218 |
};
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
概要
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
Trie は辞書のクラスです．libmarisa において最も重要なクラスであり，辞書の構築・検索からファイル入出力にいたるまで，あらゆる操作に必要となります．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
実際には，辞書のハンドルに相当するクラスであり，辞書の実体がない状況では，build(), mmap(), map(), load(), read(), clear(), swap() 以外の関数を呼び出すと例外が送出されます．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
辞書の構築
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
辞書の構築には build() を使います．引数は，前述の Keyset と，辞書の設定を XOR（|） で組み合わせた config_flags です．config_flags については，2 | MARISA_BINARY_TAIL のように指定します．この例では，辞書を構成する Patricia Trie の数を 2 つに制限し，ラベルの保存方法を MARISA_BINARY_TAIL に固定します．省略されているノードの順序とキャッシュのサイズについては，デフォルトの設定である MARISA_DEFAULT_ORDER と MARISA_DEFAULT_CACHE が採用されます．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
辞書の構築において登録文字列に割り当てられた ID は，keyset の operator[]() を使って確認できます．登録文字列に対して関連付ける情報がある場合にご利用ください．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
ファイル入出力
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
mmap() は，Memory Mapped I/O により，辞書全体をファイルから読み込むことなく検索できる状態にする関数です．少ししか検索しないのに辞書全体を読み込むのは勿体ないという状況や，異なるプロセスで同じ辞書を共有したいという状況で使うと効果的です．逆に，たくさんの文字列を検索する場合，あらかじめ辞書全体を読み込んでおかないと，外部記憶に対するランダムアクセスにより検索時間が極端に長くなる可能性があります．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
map() はメモリ上に展開されている辞書のバイナリを使って検索できる状態にする関数です．load() と read() は辞書を入力する関数であり，save() と write() は辞書を出力する関数です．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
辞書からの検索
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
検索をおこなう関数は lookup(), reverse_lookup(), common_prefix_search(), predictive_search() の 4 種類です．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
lookup(): 文字列が登録されているかどうかを確認します．登録されていれば true を返します．このとき，agent.key() により検索結果を取り出すことができます．ただし，agent.key().ptr() については，入力として渡された文字列を指しているだけであり，文字列の複製を持っているわけではないことに注意してください．登録されていなければ false を返して終了です．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
reverse_lookup(): ID から登録文字列を復元します．返り値はなく，復元された文字列は agent.key() を介してアクセスできます．文字列の実体は agent 内部に保持されています．agent を使って次の検索をおこなった段階で失われるものと考えてください．ID が範囲外であれば例外を送出して終了です．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
common_prefix_search(): 入力文字列の前半部分に一致する登録文字列を検索します．該当する登録文字列があれば true を返します．このとき，agent.key() には検索結果が格納されています．agent.key().ptr() == agent.query().ptr() が成立することに注意してください．該当する登録文字列が複数ある場合，返り値が false になるまで繰り返し common_prefix_search() を呼び出すことにより，すべての検索結果を取得できます．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
predictive_search(): 入力文字列で始まる登録文字列を検索します．該当する登録文字列があれば true を返します．検索によって復元された文字列には，agent.key() を介してアクセスできます．文字列の実体は，agent 内部に検索の途中経過として保持されているので，agent を使って次の検索をおこなった段階で失われるものと考えてください．該当する登録文字列が複数ある場合，返り値が false になるまで繰り返し predictive_search() を呼び出すことにより，すべての検索結果を取得できます．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
繰り返しにより検索が進行する common_prefix_search() と predictive_search() については，agent が検索の途中経過を保持するようになっています．そのため，agent を別の関数に渡したり，agent.set_query() を呼び出したりした時点で，検索の進行はリセットされます．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
empty() は登録文字列が存在するかどうかを返す関数です．size() は num_keys() と同じく登録文字列の数を返す関数であり，io_size() は辞書をファイルに出力した場合のサイズを返す関数です．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
void fread(std::FILE *file, Trie *trie);
|
|
Packit |
de3218 |
void fwrite(std::FILE *file, const Trie &trie);
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
std::FILE を用いる関数は marisa/stdio.h で宣言されています．#include <cstdio> を入れたくないときは，marisa.h の代わりに marisa/trie.h を使ってください．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
std::istream &read(std::istream &stream, Trie *trie);
|
|
Packit |
de3218 |
std::ostream &write(std::ostream &stream, const Trie &trie);
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
std::istream &operator>>(std::istream &stream, Trie &trie);
|
|
Packit |
de3218 |
std::ostream &operator<<(std::ostream &stream, const Trie &trie);
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
std::iostream を用いる関数は marisa/iostream.h で宣言されています．#include <iosfwd> を入れたくないときは，marisa.h の代わりに marisa/trie.h を使ってください．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
libmarisa により構築される辞書の書式はアーキテクチャに依存します．Little Endian な環境で構築した辞書は，Big Endian な環境では使えません．あらためて構築しなおす必要があります．また，Little Endian 形式の辞書は 32/64-bit 環境における互換性があるのに対し，Big Endian 形式の辞書は 32/64-bit 環境における互換性がありません．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
言語処理学会第 17 回年次大会（NLP2011）
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
言語処理学会年次大会の予稿集が公開されていて，MARISA に関する論文（F2-6.pdf）をダウンロードできます．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
発表資料（Prefix/Patricia Trie の入れ子による辞書圧縮）
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
MARISA に関する発表資料（NLP2011-F2-6.pptx, NLP2011-F2-6.pdf, NLP2011-F2-6-notes.pdf）をダウンロードできます．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
質問などありましたら，欄外のメールアドレス宛てに，お気軽にご連絡ください．
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
MARISA: Matching Algorithm with Recursively Implemented StorAge
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
moc.liamg@atay.umusus
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
|
|
Packit |
de3218 |
</body>
|
|
Packit |
de3218 |
</html>
|