1*ab8db090SAndroid Build Coastguard Worker<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"> 2*ab8db090SAndroid Build Coastguard Worker<html lang="ja"> 3*ab8db090SAndroid Build Coastguard Worker <head> 4*ab8db090SAndroid Build Coastguard Worker <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> 5*ab8db090SAndroid Build Coastguard Worker <title>MARISA: Matching Algorithm with Recursively Implemented StorAge</title> 6*ab8db090SAndroid Build Coastguard Worker <link rel="stylesheet" type="text/css" href="./style.css"> 7*ab8db090SAndroid Build Coastguard Worker </head> 8*ab8db090SAndroid Build Coastguard Worker <body> 9*ab8db090SAndroid Build Coastguard Worker <div id="header"> 10*ab8db090SAndroid Build Coastguard Worker <div class="left">MARISA: Matching Algorithm with Recursively Implemented StorAge</div> 11*ab8db090SAndroid Build Coastguard Worker <div class="right">Last modified: 14 Jun 2020</div> 12*ab8db090SAndroid Build Coastguard Worker <div class="end"></div> 13*ab8db090SAndroid Build Coastguard Worker </div><!-- header --> 14*ab8db090SAndroid Build Coastguard Worker <div id="body"> 15*ab8db090SAndroid Build Coastguard Worker <h1>MARISA: Matching Algorithm with Recursively Implemented StorAge</h1> 16*ab8db090SAndroid Build Coastguard Worker <p id="abstract"> 17*ab8db090SAndroid Build Coastguard Worker <span id="heading">Abstract: </span> 18*ab8db090SAndroid Build Coastguard Worker Matching Algorithm with Recursively Implemented StorAge (MARISA) は Trie をコンパクトに表現する程度の能力を持つデータ構造です．libmarisa は MARISA を C++ で実装したライブラリであり，MARISA による辞書を構築したり，辞書からの検索をおこなったりできます．libmarisa の基本的な機能に対応するコマンドラインツールを用意しているので，辞書のサイズがどのくらいになるのか，検索にどのくらい時間がかかるのか，などを手軽に試すことができます． 19*ab8db090SAndroid Build Coastguard Worker </p><!-- abstract --> 20*ab8db090SAndroid Build Coastguard Worker 21*ab8db090SAndroid Build Coastguard Worker <div class="section"> 22*ab8db090SAndroid Build Coastguard Worker <h2><a name="introduction">はじめに</a></h2> 23*ab8db090SAndroid Build Coastguard Worker <div class="subsection"> 24*ab8db090SAndroid Build Coastguard Worker <h3><a name="overview">概要</a></h3> 25*ab8db090SAndroid Build Coastguard Worker <p> 26*ab8db090SAndroid Build Coastguard Worker Matching Algorithm with Recursively Implemented StorAge (MARISA) は Trie に対するコンパクトなデータ構造であり，動的な更新には対応していないものの，高い空間効率とそれなりの時間効率を実現できます．また，Trie の特徴を引き継いでいるため，MARISA による辞書は，単純な辞書引きだけでなく，逆引き，Common Prefix Search や Predictive Search を効率良く実現できます． 27*ab8db090SAndroid Build Coastguard Worker </p> 28*ab8db090SAndroid Build Coastguard Worker <p> 29*ab8db090SAndroid Build Coastguard Worker ほとんどの場合，MARISA による辞書は，登録文字列の集合を連結してできるテキストと比べて，ずっとコンパクトになります．そのため，登録文字列をそのまま保持する標準的な二分探索木やハッシュ表と比べると，ずーっとコンパクトです．一方で，確率的なデータ構造である Bloom Filter と比べてみると，空間効率の面では劣りますが，False Positive がなく，逆引きに加えて Common Prefix Search や Predictive Search を効率良く実現できることが特徴になります． 30*ab8db090SAndroid Build Coastguard Worker </p> 31*ab8db090SAndroid Build Coastguard Worker <p> 32*ab8db090SAndroid Build Coastguard Worker libmarisa は MARISA を C++ で実装したライブラリであり，MARISA による辞書を構築したり，辞書からの検索をおこなったりできます．libmarisa の基本的な機能に対応するコマンドラインツールを用意しているので，辞書のサイズがどのくらいになるのか，検索にどのくらい時間がかかるのか，などを手軽に試すことができます． 33*ab8db090SAndroid Build Coastguard Worker </p> 34*ab8db090SAndroid Build Coastguard Worker </div><!-- subsection --> 35*ab8db090SAndroid Build Coastguard Worker <div class="subsection"> 36*ab8db090SAndroid Build Coastguard Worker <h3><a name="ability">できること</a></h3> 37*ab8db090SAndroid Build Coastguard Worker <p> 38*ab8db090SAndroid Build Coastguard Worker libmarisa による辞書の構築では，登録文字列に <var>0</var> から順に固有の ID を割り当てるようになっています．ID は自動的に割り当てられるので，登録文字列に任意の ID を割り当てることはできません．検索においては，文字列あるいは ID をクエリとして受け取り，適合する登録文字列と ID の組を検索結果として返すようになっています． 39*ab8db090SAndroid Build Coastguard Worker </p> 40*ab8db090SAndroid Build Coastguard Worker <ul> 41*ab8db090SAndroid Build Coastguard Worker <li>辞書引き（Lookup） 42*ab8db090SAndroid Build Coastguard Worker <ul> 43*ab8db090SAndroid Build Coastguard Worker <li>入力文字列が登録されているかどうかを確認します．</li> 44*ab8db090SAndroid Build Coastguard Worker </ul> 45*ab8db090SAndroid Build Coastguard Worker </li> 46*ab8db090SAndroid Build Coastguard Worker <li>逆引き（Reverse Lookup） 47*ab8db090SAndroid Build Coastguard Worker <ul> 48*ab8db090SAndroid Build Coastguard Worker <li>入力された ID から登録文字列を復元します．</li> 49*ab8db090SAndroid Build Coastguard Worker </ul> 50*ab8db090SAndroid Build Coastguard Worker </li> 51*ab8db090SAndroid Build Coastguard Worker <li>Common Prefix Search 52*ab8db090SAndroid Build Coastguard Worker <ul> 53*ab8db090SAndroid Build Coastguard Worker <li>入力文字列の前半部分に一致する登録文字列を検索します．</li> 54*ab8db090SAndroid Build Coastguard Worker </ul> 55*ab8db090SAndroid Build Coastguard Worker </li> 56*ab8db090SAndroid Build Coastguard Worker <li>Predictive Search 57*ab8db090SAndroid Build Coastguard Worker <ul> 58*ab8db090SAndroid Build Coastguard Worker <li>入力文字列で始まる登録文字列を検索します．</li> 59*ab8db090SAndroid Build Coastguard Worker </ul> 60*ab8db090SAndroid Build Coastguard Worker </li> 61*ab8db090SAndroid Build Coastguard Worker </ul> 62*ab8db090SAndroid Build Coastguard Worker </div><!-- subsection --> 63*ab8db090SAndroid Build Coastguard Worker </div><!-- section --> 64*ab8db090SAndroid Build Coastguard Worker <div class="section"> 65*ab8db090SAndroid Build Coastguard Worker <h2><a name="source">ソースコード</a></h2> 66*ab8db090SAndroid Build Coastguard Worker <div class="subsection"> 67*ab8db090SAndroid Build Coastguard Worker <h3><a name="license">ライセンス</a></h3> 68*ab8db090SAndroid Build Coastguard Worker <p> 69*ab8db090SAndroid Build Coastguard Worker libmarisa および付属のコマンドラインツールはフリーソフトウェアです．使用・再配布については，二条項 BSD ライセンスと LGPL のデュアルライセンスを採用しています． 70*ab8db090SAndroid Build Coastguard Worker </p> 71*ab8db090SAndroid Build Coastguard Worker </div><!-- subsection --> 72*ab8db090SAndroid Build Coastguard Worker <div class="subsection"> 73*ab8db090SAndroid Build Coastguard Worker <h3><a name="download">ダウンロード</a></h3> 74*ab8db090SAndroid Build Coastguard Worker <p> 75*ab8db090SAndroid Build Coastguard Worker プロジェクトの管理やソースコードの配布には <a href="https://github.com/">GitHub</a> を利用しています． 76*ab8db090SAndroid Build Coastguard Worker </p> 77*ab8db090SAndroid Build Coastguard Worker <ul> 78*ab8db090SAndroid Build Coastguard Worker <li>プロジェクト 79*ab8db090SAndroid Build Coastguard Worker <ul> 80*ab8db090SAndroid Build Coastguard Worker <li><a href="https://github.com/s-yata/marisa-trie">https://github.com/s-yata/marisa-trie</a></li> 81*ab8db090SAndroid Build Coastguard Worker </ul> 82*ab8db090SAndroid Build Coastguard Worker </li> 83*ab8db090SAndroid Build Coastguard Worker <li>ソースコード 84*ab8db090SAndroid Build Coastguard Worker <ul> 85*ab8db090SAndroid Build Coastguard Worker <li><a href="https://github.com/s-yata/marisa-trie/archive/v0.2.6.tar.gz">marisa-0.2.6.tar.gz</a></li> 86*ab8db090SAndroid Build Coastguard Worker </ul> 87*ab8db090SAndroid Build Coastguard Worker </li> 88*ab8db090SAndroid Build Coastguard Worker </ul> 89*ab8db090SAndroid Build Coastguard Worker </div><!-- subsection --> 90*ab8db090SAndroid Build Coastguard Worker </div><!-- section --> 91*ab8db090SAndroid Build Coastguard Worker 92*ab8db090SAndroid Build Coastguard Worker <div class="section"> 93*ab8db090SAndroid Build Coastguard Worker <h2><a name="install">インストール</a></h2> 94*ab8db090SAndroid Build Coastguard Worker <div class="subsection"> 95*ab8db090SAndroid Build Coastguard Worker <h3><a name="gcc">GCC & Clang</a></h3> 96*ab8db090SAndroid Build Coastguard Worker <div class="float"> 97*ab8db090SAndroid Build Coastguard Worker <pre class="console">$ tar zxf marisa-0.2.6.tar.gz 98*ab8db090SAndroid Build Coastguard Worker$ cd marisa-0.2.6 99*ab8db090SAndroid Build Coastguard Worker$ ./configure 100*ab8db090SAndroid Build Coastguard Worker$ make 101*ab8db090SAndroid Build Coastguard Worker$ make check 102*ab8db090SAndroid Build Coastguard Worker$ make install</pre> 103*ab8db090SAndroid Build Coastguard Worker </div><!-- float --> 104*ab8db090SAndroid Build Coastguard Worker <p> 105*ab8db090SAndroid Build Coastguard Worker <kbd>configure</kbd> と <kbd>make</kbd> によりインストールできるようになっています．<kbd>make install</kbd> については，必要に応じて <kbd>sudo</kbd> を付けてご利用ください．また，特に指定がなければ libmarisa は共有ライブラリとしてインストールされるので，<kbd>ldconfig</kbd> が必要になるかもしれません． 106*ab8db090SAndroid Build Coastguard Worker </p> 107*ab8db090SAndroid Build Coastguard Worker <p> 108*ab8db090SAndroid Build Coastguard Worker POPCNT 命令が使える環境では，<kbd>configure</kbd> に <kbd>--enable-popcnt</kbd> を渡すことで，少し高速化することができます．同様に，<kbd>--enable-sse2</kbd>, <kbd>--enable-sse3</kbd>, <kbd>--enable-ssse3</kbd>, <kbd>--enable-sse4.1</kbd>, <kbd>--enable-sse4.2</kbd>, <kbd>--enable-sse4</kbd>, <kbd>--enable-sse4a</kbd>, <kbd>--enable-bmi</kbd>, <kbd>--enable-bmi2</kbd> というオプションがあります．<kbd>--enable-native-code</kbd> を渡せば，コンパイル環境で使える命令がすべて有効になります．また，スタティックライブラリが必要なときは，<kbd>configure</kbd> に <kbd>--enable-static</kbd> を渡すようにしてください．その他，<kbd>configure</kbd> のオプションについては <kbd>./configure --help</kbd> をご覧ください． 109*ab8db090SAndroid Build Coastguard Worker </p> 110*ab8db090SAndroid Build Coastguard Worker </div><!-- subsection --> 111*ab8db090SAndroid Build Coastguard Worker <div class="subsection"> 112*ab8db090SAndroid Build Coastguard Worker <h3><a name="vc">Visual C++ 2008</a></h3> 113*ab8db090SAndroid Build Coastguard Worker <p> 114*ab8db090SAndroid Build Coastguard Worker Visual C++ 2008 にて作成したファイルを <kbd>vs2008/</kbd> 以下に配置しています．Visual C++ 2008 以降であれば，<kbd>vs2008/vs2008.sln</kbd> を開くだけでスタティックライブラリ <kbd>libmarisa.lib</kbd> とコマンドラインツールをビルドできます． 115*ab8db090SAndroid Build Coastguard Worker </p> 116*ab8db090SAndroid Build Coastguard Worker <p> 117*ab8db090SAndroid Build Coastguard Worker Visual C++ 2008 より古い環境では，新しくプロジェクトを作る必要があります．プロジェクトを作成すれば問題なくビルドできると思いますが，試していないので断言はできません． 118*ab8db090SAndroid Build Coastguard Worker </p> 119*ab8db090SAndroid Build Coastguard Worker </div><!-- subsection --> 120*ab8db090SAndroid Build Coastguard Worker <div class="subsection"> 121*ab8db090SAndroid Build Coastguard Worker <h3><a name="vc">Perl バインディング</a></h3> 122*ab8db090SAndroid Build Coastguard Worker <div class="float"> 123*ab8db090SAndroid Build Coastguard Worker <pre class="console">$ cd bindings/perl 124*ab8db090SAndroid Build Coastguard Worker$ perl Makefile.PL 125*ab8db090SAndroid Build Coastguard Worker$ make 126*ab8db090SAndroid Build Coastguard Worker$ make install</pre> 127*ab8db090SAndroid Build Coastguard Worker </div><!-- float --> 128*ab8db090SAndroid Build Coastguard Worker <p> 129*ab8db090SAndroid Build Coastguard Worker <a href="http://www.swig.org/">SWIG</a> による Perl バインディングが <kbd>bindings/perl/</kbd> にあります．<kbd>perl Makefile.PL</kbd> により <kbd>Makefile</kbd> を作成し，<kbd>make install</kbd> を実行することでインストールできます．使い方については，<kbd>bindings/perl/sample.pl</kbd> を参考にしてください． 130*ab8db090SAndroid Build Coastguard Worker </p> 131*ab8db090SAndroid Build Coastguard Worker </div><!-- subsection --> 132*ab8db090SAndroid Build Coastguard Worker <div class="subsection"> 133*ab8db090SAndroid Build Coastguard Worker <h3><a name="vc">Python バインディング</a></h3> 134*ab8db090SAndroid Build Coastguard Worker <div class="float"> 135*ab8db090SAndroid Build Coastguard Worker <pre class="console">$ cd bindings/python 136*ab8db090SAndroid Build Coastguard Worker$ python setup.py build 137*ab8db090SAndroid Build Coastguard Worker$ python setup.py install</pre> 138*ab8db090SAndroid Build Coastguard Worker </div><!-- float --> 139*ab8db090SAndroid Build Coastguard Worker <p> 140*ab8db090SAndroid Build Coastguard Worker <a href="http://www.swig.org/">SWIG</a> による Python バインディングが <kbd>bindings/python/</kbd> にあります．<kbd>python setup.py install</kbd> により インストールできます．使い方については，<kbd>bindings/python/sample.py</kbd> を参考にしてください． 141*ab8db090SAndroid Build Coastguard Worker </p> 142*ab8db090SAndroid Build Coastguard Worker </div><!-- subsection --> 143*ab8db090SAndroid Build Coastguard Worker <div class="subsection"> 144*ab8db090SAndroid Build Coastguard Worker <h3><a name="vc">Ruby バインディング</a></h3> 145*ab8db090SAndroid Build Coastguard Worker <div class="float"> 146*ab8db090SAndroid Build Coastguard Worker <pre class="console">$ cd bindings/ruby 147*ab8db090SAndroid Build Coastguard Worker$ ruby extconf.rb 148*ab8db090SAndroid Build Coastguard Worker$ make 149*ab8db090SAndroid Build Coastguard Worker$ make install</pre> 150*ab8db090SAndroid Build Coastguard Worker </div><!-- float --> 151*ab8db090SAndroid Build Coastguard Worker <p> 152*ab8db090SAndroid Build Coastguard Worker <a href="http://www.swig.org/">SWIG</a> による Ruby バインディングが <kbd>bindings/ruby/</kbd> にあります．<kbd>ruby extconf.rb</kbd> により <kbd>Makefile</kbd> を作成し，<kbd>make install</kbd> を実行することでインストールできます．使い方については，<kbd>bindings/ruby/sample.rb</kbd> を参考にしてください． 153*ab8db090SAndroid Build Coastguard Worker </p> 154*ab8db090SAndroid Build Coastguard Worker </div><!-- subsection --> 155*ab8db090SAndroid Build Coastguard Worker <div class="subsection"> 156*ab8db090SAndroid Build Coastguard Worker <h3><a name="vc">その他</a></h3> 157*ab8db090SAndroid Build Coastguard Worker <p> 158*ab8db090SAndroid Build Coastguard Worker 上記のバインディング以外にも，いくつかのバインディングがあります． 159*ab8db090SAndroid Build Coastguard Worker </p> 160*ab8db090SAndroid Build Coastguard Worker <ul> 161*ab8db090SAndroid Build Coastguard Worker <li>Python 162*ab8db090SAndroid Build Coastguard Worker <ul> 163*ab8db090SAndroid Build Coastguard Worker <li><a href="https://github.com/kmike/marisa-trie/">"https://github.com/kmike/marisa-trie/</a>高速・高機能な Python バインディング</li> 164*ab8db090SAndroid Build Coastguard Worker </ul> 165*ab8db090SAndroid Build Coastguard Worker </li> 166*ab8db090SAndroid Build Coastguard Worker <li>Node.js 167*ab8db090SAndroid Build Coastguard Worker <ul> 168*ab8db090SAndroid Build Coastguard Worker <li><a href="https://github.com/komiya-atsushi/node-marisa-trie">https://github.com/komiya-atsushi/node-marisa-trie</a>Node.js から使うためのモジュール</li> 169*ab8db090SAndroid Build Coastguard Worker </ul> 170*ab8db090SAndroid Build Coastguard Worker </li> 171*ab8db090SAndroid Build Coastguard Worker </p> 172*ab8db090SAndroid Build Coastguard Worker </div><!-- subsection --> 173*ab8db090SAndroid Build Coastguard Worker </div><!-- section --> 174*ab8db090SAndroid Build Coastguard Worker 175*ab8db090SAndroid Build Coastguard Worker <div class="section"> 176*ab8db090SAndroid Build Coastguard Worker <h2><a name="tools">コマンドラインツール</a></h2> 177*ab8db090SAndroid Build Coastguard Worker <div class="subsection"> 178*ab8db090SAndroid Build Coastguard Worker <h3><a name="marisa-build">marisa-build</a></h3> 179*ab8db090SAndroid Build Coastguard Worker <div class="float"> 180*ab8db090SAndroid Build Coastguard Worker <pre class="console">$ marisa-build < keyset.txt > keyset.dic 181*ab8db090SAndroid Build Coastguard Worker#keys: 1342099 182*ab8db090SAndroid Build Coastguard Worker#nodes: 1832373 183*ab8db090SAndroid Build Coastguard Workersize: 7841664</pre> 184*ab8db090SAndroid Build Coastguard Worker </div><!-- float --> 185*ab8db090SAndroid Build Coastguard Worker <p> 186*ab8db090SAndroid Build Coastguard Worker <kbd>marisa-build</kbd> は辞書を構築するツールです．改行を区切りとして文字列を受け取り，構築した辞書を標準出力に書き出すようになっています． 187*ab8db090SAndroid Build Coastguard Worker </p> 188*ab8db090SAndroid Build Coastguard Worker <p> 189*ab8db090SAndroid Build Coastguard Worker 構築する辞書のパラメータについては，オプションを使って指定できます．オプションの一覧は <kbd>marisa-build -h</kbd> により確認できます． 190*ab8db090SAndroid Build Coastguard Worker </p> 191*ab8db090SAndroid Build Coastguard Worker <p> 192*ab8db090SAndroid Build Coastguard Worker 入力は改行区切りとなっていますが，水平タブが存在する行については，最後の水平タブ以降を文字列の重みとして扱うようになっています．文字列の出現頻度や出現確率を与えることにより，検索時間を短縮できる可能性があります． 193*ab8db090SAndroid Build Coastguard Worker </p> 194*ab8db090SAndroid Build Coastguard Worker </div><!-- subsection --> 195*ab8db090SAndroid Build Coastguard Worker <div class="subsection"> 196*ab8db090SAndroid Build Coastguard Worker <h3><a name="marisa-lookup">marisa-lookup</a></h3> 197*ab8db090SAndroid Build Coastguard Worker <div class="float"> 198*ab8db090SAndroid Build Coastguard Worker <pre class="console">$ marisa-lookup keyset.dic 199*ab8db090SAndroid Build Coastguard Worker東方 200*ab8db090SAndroid Build Coastguard Worker174385 東方 201*ab8db090SAndroid Build Coastguard Workerとうほう 202*ab8db090SAndroid Build Coastguard Worker-1 とうほう</pre> 203*ab8db090SAndroid Build Coastguard Worker </div><!-- float --> 204*ab8db090SAndroid Build Coastguard Worker <p> 205*ab8db090SAndroid Build Coastguard Worker <kbd>marisa-lookup</kbd> は単純な辞書引きをおこなうツールです．入力された文字列が登録されていれば ID とともに出力し，登録されていなければ <var>-1</var> とともに出力します． 206*ab8db090SAndroid Build Coastguard Worker </p> 207*ab8db090SAndroid Build Coastguard Worker <p> 208*ab8db090SAndroid Build Coastguard Worker オプションの一覧は <kbd>marisa-lookup -h</kbd> により確認できます． 209*ab8db090SAndroid Build Coastguard Worker </p> 210*ab8db090SAndroid Build Coastguard Worker </div><!-- subsection --> 211*ab8db090SAndroid Build Coastguard Worker <div class="subsection"> 212*ab8db090SAndroid Build Coastguard Worker <h3><a name="marisa-reverse-lookup">marisa-reverse-lookup</a></h3> 213*ab8db090SAndroid Build Coastguard Worker <div class="float"> 214*ab8db090SAndroid Build Coastguard Worker <pre class="console">$ marisa-reverse-lookup keyset.dic 215*ab8db090SAndroid Build Coastguard Worker800000 216*ab8db090SAndroid Build Coastguard Worker800000 紀元前475年</pre> 217*ab8db090SAndroid Build Coastguard Worker </div><!-- float --> 218*ab8db090SAndroid Build Coastguard Worker <p> 219*ab8db090SAndroid Build Coastguard Worker <kbd>marisa-reverse-lookup</kbd> は辞書に登録されている文字列を ID から復元するツールです．登録文字列には <var>0</var> から順に固有の ID が割り当てられるので，指定できる値は <var>0</var> 以上で<var>登録文字列数</var>より小さい整数となります．範囲外の値を入力するとエラーになるので注意してください． 220*ab8db090SAndroid Build Coastguard Worker </p> 221*ab8db090SAndroid Build Coastguard Worker <p> 222*ab8db090SAndroid Build Coastguard Worker オプションの一覧は <kbd>marisa-reverse-lookup -h</kbd> により確認できます． 223*ab8db090SAndroid Build Coastguard Worker </p> 224*ab8db090SAndroid Build Coastguard Worker </div><!-- subsection --> 225*ab8db090SAndroid Build Coastguard Worker <div class="subsection"> 226*ab8db090SAndroid Build Coastguard Worker <h3><a name="marisa-common-prefix-search">marisa-common-prefix-search</a></h3> 227*ab8db090SAndroid Build Coastguard Worker <div class="float"> 228*ab8db090SAndroid Build Coastguard Worker <pre class="console">$ marisa-common-prefix-search keyset.dic 229*ab8db090SAndroid Build Coastguard Worker東方 230*ab8db090SAndroid Build Coastguard Worker2 found 231*ab8db090SAndroid Build Coastguard Worker3542 東 東方 232*ab8db090SAndroid Build Coastguard Worker174385 東方 東方</pre> 233*ab8db090SAndroid Build Coastguard Worker </div><!-- float --> 234*ab8db090SAndroid Build Coastguard Worker <p> 235*ab8db090SAndroid Build Coastguard Worker <kbd>marisa-common-prefix-search</kbd> は Common Prefix Search をおこなうツールです．入力された文字列の前半部分に一致する登録文字列を ID とともに出力します． 236*ab8db090SAndroid Build Coastguard Worker </p> 237*ab8db090SAndroid Build Coastguard Worker <p> 238*ab8db090SAndroid Build Coastguard Worker オプションの一覧は <kbd>marisa-common-prefix-search -h</kbd> により確認できます． 239*ab8db090SAndroid Build Coastguard Worker </p> 240*ab8db090SAndroid Build Coastguard Worker </div><!-- subsection --> 241*ab8db090SAndroid Build Coastguard Worker <div class="subsection"> 242*ab8db090SAndroid Build Coastguard Worker <h3><a name="marisa-predictive-search">marisa-predictive-search</a></h3> 243*ab8db090SAndroid Build Coastguard Worker <div class="float"> 244*ab8db090SAndroid Build Coastguard Worker <pre class="console">$ marisa-predictive-search keyset.dic -n 2 245*ab8db090SAndroid Build Coastguard Worker東方 246*ab8db090SAndroid Build Coastguard Worker200 found 247*ab8db090SAndroid Build Coastguard Worker174385 東方 東方 248*ab8db090SAndroid Build Coastguard Worker639679 東方文花帖 東方</pre> 249*ab8db090SAndroid Build Coastguard Worker </div><!-- float --> 250*ab8db090SAndroid Build Coastguard Worker <p> 251*ab8db090SAndroid Build Coastguard Worker <kbd>marisa-predictive-search</kbd> は Predictive Search をおこなうツールです．入力された文字列で始まる登録文字列を ID とともに出力します． 252*ab8db090SAndroid Build Coastguard Worker </p> 253*ab8db090SAndroid Build Coastguard Worker <p> 254*ab8db090SAndroid Build Coastguard Worker オプションの一覧は <kbd>marisa-predictive-search -h</kbd> により確認できます． 255*ab8db090SAndroid Build Coastguard Worker </p> 256*ab8db090SAndroid Build Coastguard Worker </div><!-- subsection --> 257*ab8db090SAndroid Build Coastguard Worker <div class="subsection"> 258*ab8db090SAndroid Build Coastguard Worker <h3><a name="marisa-benchmark">marisa-benchmark</a></h3> 259*ab8db090SAndroid Build Coastguard Worker <div class="float"> 260*ab8db090SAndroid Build Coastguard Worker <pre class="console">$ marisa-benchmark keyset.txt 261*ab8db090SAndroid Build Coastguard WorkerNumber of tries: 1 - 5 262*ab8db090SAndroid Build Coastguard WorkerTAIL mode: Text mode 263*ab8db090SAndroid Build Coastguard WorkerNode order: Descending weight order 264*ab8db090SAndroid Build Coastguard WorkerCache level: Normal cache 265*ab8db090SAndroid Build Coastguard WorkerNumber of keys: 1342099 266*ab8db090SAndroid Build Coastguard WorkerTotal length: 28308027 267*ab8db090SAndroid Build Coastguard Worker------+----------+--------+--------+--------+--------+-------- 268*ab8db090SAndroid Build Coastguard Worker#tries size build lookup reverse prefix predict 269*ab8db090SAndroid Build Coastguard Worker lookup search search 270*ab8db090SAndroid Build Coastguard Worker [bytes] [K/s] [K/s] [K/s] [K/s] [K/s] 271*ab8db090SAndroid Build Coastguard Worker------+----------+--------+--------+--------+--------+-------- 272*ab8db090SAndroid Build Coastguard Worker 1 11588904 506.45 1187.70 1109.17 1040.39 596.49 273*ab8db090SAndroid Build Coastguard Worker 2 8467920 424.71 699.01 677.83 636.07 300.25 274*ab8db090SAndroid Build Coastguard Worker 3 7841664 405.47 615.64 601.84 563.91 254.67 275*ab8db090SAndroid Build Coastguard Worker 4 7633584 399.43 593.85 583.52 545.57 242.69 276*ab8db090SAndroid Build Coastguard Worker 5 7548584 395.90 526.31 563.91 504.55 236.70 277*ab8db090SAndroid Build Coastguard Worker------+----------+--------+--------+--------+--------+--------</pre> 278*ab8db090SAndroid Build Coastguard Worker </div><!-- float --> 279*ab8db090SAndroid Build Coastguard Worker <p> 280*ab8db090SAndroid Build Coastguard Worker <kbd>marisa-benchmark</kbd> は，<kbd>marisa-build</kbd> と同様の入力を受け取り，辞書のサイズや構築・検索にかかる時間を調べるツールです．辞書を構成する Trie の数を選択するのに有用です． 281*ab8db090SAndroid Build Coastguard Worker </p> 282*ab8db090SAndroid Build Coastguard Worker <p> 283*ab8db090SAndroid Build Coastguard Worker 検索時間については，入力された文字列を一通り検索するのに要した時間を <code>std::clock()</code> で計測した結果を出力します．文字列を整列してから入力とした場合はキャッシュが効きやすい状況での検索時間になり，文字列をランダムに並べ替えてから入力とした場合はキャッシュが効きにくい状況での検索時間になります． 284*ab8db090SAndroid Build Coastguard Worker </p> 285*ab8db090SAndroid Build Coastguard Worker <p> 286*ab8db090SAndroid Build Coastguard Worker オプションの一覧は <kbd>marisa-benchmark -h</kbd> により確認できます． 287*ab8db090SAndroid Build Coastguard Worker </p> 288*ab8db090SAndroid Build Coastguard Worker </div><!-- subsection --> 289*ab8db090SAndroid Build Coastguard Worker <div class="subsection"> 290*ab8db090SAndroid Build Coastguard Worker <h3><a name="marisa-dump">marisa-dump</a></h3> 291*ab8db090SAndroid Build Coastguard Worker <div class="float"> 292*ab8db090SAndroid Build Coastguard Worker <pre class="console">$ marisa-dump keyset.dic | head -3 293*ab8db090SAndroid Build Coastguard Workerinput: keyset.dic 294*ab8db090SAndroid Build Coastguard Workerフ 295*ab8db090SAndroid Build Coastguard Workerファ 296*ab8db090SAndroid Build Coastguard Workerファン</pre> 297*ab8db090SAndroid Build Coastguard Worker </div><!-- float --> 298*ab8db090SAndroid Build Coastguard Worker <p> 299*ab8db090SAndroid Build Coastguard Worker <kbd>marisa-dump</kbd> は辞書に登録されている文字列をすべて出力するツールです．デフォルトの区切り文字は改行（LF）ですが，オプションにより変更することができます． 300*ab8db090SAndroid Build Coastguard Worker </p> 301*ab8db090SAndroid Build Coastguard Worker <p> 302*ab8db090SAndroid Build Coastguard Worker オプションの一覧は <kbd>marisa-dump -h</kbd> により確認できます． 303*ab8db090SAndroid Build Coastguard Worker </p> 304*ab8db090SAndroid Build Coastguard Worker </div><!-- subsection --> 305*ab8db090SAndroid Build Coastguard Worker </div><!-- section --> 306*ab8db090SAndroid Build Coastguard Worker 307*ab8db090SAndroid Build Coastguard Worker <div class="section"> 308*ab8db090SAndroid Build Coastguard Worker <h2><a name="library">ライブラリ</a></h2> 309*ab8db090SAndroid Build Coastguard Worker <div class="subsection"> 310*ab8db090SAndroid Build Coastguard Worker <h3><a name="howto">使い方</a></h3> 311*ab8db090SAndroid Build Coastguard Worker <div class="float"> 312*ab8db090SAndroid Build Coastguard Worker <pre class="code">// sample.cc 313*ab8db090SAndroid Build Coastguard Worker#include <iostream> 314*ab8db090SAndroid Build Coastguard Worker#include <marisa.h> 315*ab8db090SAndroid Build Coastguard Worker 316*ab8db090SAndroid Build Coastguard Workerint main() { 317*ab8db090SAndroid Build Coastguard Worker marisa::Keyset keyset; 318*ab8db090SAndroid Build Coastguard Worker keyset.push_back("a"); 319*ab8db090SAndroid Build Coastguard Worker keyset.push_back("app"); 320*ab8db090SAndroid Build Coastguard Worker keyset.push_back("apple"); 321*ab8db090SAndroid Build Coastguard Worker 322*ab8db090SAndroid Build Coastguard Worker marisa::Trie trie; 323*ab8db090SAndroid Build Coastguard Worker trie.build(keyset); 324*ab8db090SAndroid Build Coastguard Worker 325*ab8db090SAndroid Build Coastguard Worker marisa::Agent agent; 326*ab8db090SAndroid Build Coastguard Worker agent.set_query("apple"); 327*ab8db090SAndroid Build Coastguard Worker while (trie.common_prefix_search(agent)) { 328*ab8db090SAndroid Build Coastguard Worker std::cout.write(agent.key().ptr(), agent.key().length()); 329*ab8db090SAndroid Build Coastguard Worker std::cout << ": " << agent.key().id() << std::endl; 330*ab8db090SAndroid Build Coastguard Worker } 331*ab8db090SAndroid Build Coastguard Worker return 0; 332*ab8db090SAndroid Build Coastguard Worker}</pre> 333*ab8db090SAndroid Build Coastguard Worker </div><!-- float --> 334*ab8db090SAndroid Build Coastguard Worker <div class="float"> 335*ab8db090SAndroid Build Coastguard Worker <pre class="console">$ g++ sample.cc -lmarisa 336*ab8db090SAndroid Build Coastguard Worker$ ./a.out 337*ab8db090SAndroid Build Coastguard Workera: 0 338*ab8db090SAndroid Build Coastguard Workerapp: 1 339*ab8db090SAndroid Build Coastguard Workerapple: 2</pre> 340*ab8db090SAndroid Build Coastguard Worker </div><!-- float --> 341*ab8db090SAndroid Build Coastguard Worker <p> 342*ab8db090SAndroid Build Coastguard Worker libmarisa のヘッダは <kbd>marisa.h</kbd> です．名前空間には <code>marisa</code> を使っています．危険なので，<code>using namespace marisa</code> とするのは避けてください．最後に，<kbd>gcc</kbd> や <kbd>clang</kbd> によるリンクでは <kbd>-lmarisa</kbd> が必要となることに注意してください． 343*ab8db090SAndroid Build Coastguard Worker </p> 344*ab8db090SAndroid Build Coastguard Worker <p> 345*ab8db090SAndroid Build Coastguard Worker libmarisa の主要なクラスは <a href="#keyset">Keyset</a>, <a href="#agent">Agent</a>, <a href="#trie">Trie</a> の 3 つです．サンプルコードでは明示的に使っていませんが，例外のクラスとして <a href="#exception">Exception</a> があるほか，<code>Keyset</code>, <code>Agent</code> のメンバとして <a href="#key">Key</a> や <a href="#query">Query</a> が存在します． 346*ab8db090SAndroid Build Coastguard Worker </p> 347*ab8db090SAndroid Build Coastguard Worker <ul> 348*ab8db090SAndroid Build Coastguard Worker <li><code>Keyset</code>: 文字列の集合を格納するクラスです．辞書を構築するときの入力として使うほか，検索結果の保存にも利用できます．</li> 349*ab8db090SAndroid Build Coastguard Worker <li><code>Agent</code>: 検索の入出力と途中経過を格納するクラスです．検索用の関数はすべて Agent への参照を引数とします．</li> 350*ab8db090SAndroid Build Coastguard Worker <li><code>Trie</code>: 辞書のクラスです．</li> 351*ab8db090SAndroid Build Coastguard Worker </ul> 352*ab8db090SAndroid Build Coastguard Worker <p> 353*ab8db090SAndroid Build Coastguard Worker コマンドラインツールのソースコードが <kbd>tools/</kbd> にあり，例外処理やファイル入出力，Predictive Search などのサンプルとして利用できます． 354*ab8db090SAndroid Build Coastguard Worker </p> 355*ab8db090SAndroid Build Coastguard Worker </div><!-- subsection --> 356*ab8db090SAndroid Build Coastguard Worker 357*ab8db090SAndroid Build Coastguard Worker <div class="subsection"> 358*ab8db090SAndroid Build Coastguard Worker <h3><a name="enum">定数</a></h3> 359*ab8db090SAndroid Build Coastguard Worker <div class="subsubsection"> 360*ab8db090SAndroid Build Coastguard Worker <h4>エラーコード</h4> 361*ab8db090SAndroid Build Coastguard Worker <div class="float"> 362*ab8db090SAndroid Build Coastguard Worker <pre class="code">typedef enum marisa_error_code_ { 363*ab8db090SAndroid Build Coastguard Worker MARISA_OK = 0, 364*ab8db090SAndroid Build Coastguard Worker MARISA_STATE_ERROR = 1, 365*ab8db090SAndroid Build Coastguard Worker MARISA_NULL_ERROR = 2, 366*ab8db090SAndroid Build Coastguard Worker MARISA_BOUND_ERROR = 3, 367*ab8db090SAndroid Build Coastguard Worker MARISA_RANGE_ERROR = 4, 368*ab8db090SAndroid Build Coastguard Worker MARISA_CODE_ERROR = 5, 369*ab8db090SAndroid Build Coastguard Worker MARISA_RESET_ERROR = 6, 370*ab8db090SAndroid Build Coastguard Worker MARISA_SIZE_ERROR = 7, 371*ab8db090SAndroid Build Coastguard Worker MARISA_MEMORY_ERROR = 8, 372*ab8db090SAndroid Build Coastguard Worker MARISA_IO_ERROR = 9, 373*ab8db090SAndroid Build Coastguard Worker MARISA_FORMAT_ERROR = 10, 374*ab8db090SAndroid Build Coastguard Worker} marisa_error_code;</pre> 375*ab8db090SAndroid Build Coastguard Worker </div><!-- float --> 376*ab8db090SAndroid Build Coastguard Worker <p> 377*ab8db090SAndroid Build Coastguard Worker libmarisa では，ファイル入出力に失敗したときや辞書のサイズが上限に到達したときなどに，<code>Exception</code> を送出します．そして，<code>Exception</code> に格納される情報の 1 つが <code>marisa_error_code</code> です． 378*ab8db090SAndroid Build Coastguard Worker </p> 379*ab8db090SAndroid Build Coastguard Worker <p> 380*ab8db090SAndroid Build Coastguard Worker 辞書の入出力に関するエラーコードである <var>MARISA_IO_ERROR</var> と <var>MARISA_FORMAT_ERROR</var> 以外については，バグによる可能性が高いと思います．各エラーコードの詳細については，<kbd>marisa/base.h</kbd> をご覧ください． 381*ab8db090SAndroid Build Coastguard Worker </p> 382*ab8db090SAndroid Build Coastguard Worker </div><!-- subsubsection --> 383*ab8db090SAndroid Build Coastguard Worker <div class="subsubsection"> 384*ab8db090SAndroid Build Coastguard Worker <h4>トライの数</h4> 385*ab8db090SAndroid Build Coastguard Worker <div class="float"> 386*ab8db090SAndroid Build Coastguard Worker <pre class="code"> 387*ab8db090SAndroid Build Coastguard Workertypedef enum marisa_num_tries_ { 388*ab8db090SAndroid Build Coastguard Worker MARISA_MIN_NUM_TRIES = 0x00001, 389*ab8db090SAndroid Build Coastguard Worker MARISA_MAX_NUM_TRIES = 0x0007F, 390*ab8db090SAndroid Build Coastguard Worker MARISA_DEFAULT_NUM_TRIES = 0x00003, 391*ab8db090SAndroid Build Coastguard Worker} marisa_num_tries;</pre> 392*ab8db090SAndroid Build Coastguard Worker </div><!-- float --> 393*ab8db090SAndroid Build Coastguard Worker <p> 394*ab8db090SAndroid Build Coastguard Worker MARISA は複数の Patricia Trie を組み合わせて 1 つの Trie を構成することが特徴の 1 つであり，Patricia Trie の数を増やすほど，辞書はコンパクトになるものの，検索が遅くなるという傾向があります．<code>marisa_num_tries</code> では，辞書を構成する Patricia Trie の数について，最小値・最大値とデフォルトの値を提供します． 395*ab8db090SAndroid Build Coastguard Worker </p> 396*ab8db090SAndroid Build Coastguard Worker <p> 397*ab8db090SAndroid Build Coastguard Worker 適切な設定は登録文字列やアプリケーションによって異なります．ほとんどの場合はデフォルトの設定で問題ないと思いますが，検索時間が問題になるときは，思い切って <var>1</var> にしてください．また，登録文字列が長くて少し複雑な構成になる場合，デフォルトより大きな値にすることで，辞書のサイズをさらに小さくできることがあります．設定が気になるときは，<kbd>marisa-benchmark</kbd> をお試しください． 398*ab8db090SAndroid Build Coastguard Worker </p> 399*ab8db090SAndroid Build Coastguard Worker </div><!-- subsubsection --> 400*ab8db090SAndroid Build Coastguard Worker <div class="subsubsection"> 401*ab8db090SAndroid Build Coastguard Worker <h4>キャッシュのサイズ</h4> 402*ab8db090SAndroid Build Coastguard Worker <div class="float"> 403*ab8db090SAndroid Build Coastguard Worker <pre class="code">typedef enum marisa_cache_level_ { 404*ab8db090SAndroid Build Coastguard Worker MARISA_HUGE_CACHE = 0x00080, 405*ab8db090SAndroid Build Coastguard Worker MARISA_LARGE_CACHE = 0x00100, 406*ab8db090SAndroid Build Coastguard Worker MARISA_NORMAL_CACHE = 0x00200, 407*ab8db090SAndroid Build Coastguard Worker MARISA_SMALL_CACHE = 0x00400, 408*ab8db090SAndroid Build Coastguard Worker MARISA_TINY_CACHE = 0x00800, 409*ab8db090SAndroid Build Coastguard Worker MARISA_DEFAULT_CACHE = MARISA_NORMAL_CACHE 410*ab8db090SAndroid Build Coastguard Worker} marisa_cache_level;</pre> 411*ab8db090SAndroid Build Coastguard Worker </div><!-- float --> 412*ab8db090SAndroid Build Coastguard Worker <p> 413*ab8db090SAndroid Build Coastguard Worker libmarisa では，検索時間の短縮を目的として，辞書にキャッシュを埋め込むようになっています．キャッシュの内容は通過する確率の高い遷移に関する情報であり，キャッシュを大きくすることによって，辞書は大きくなるものの，検索時間を短縮できます． 414*ab8db090SAndroid Build Coastguard Worker </p> 415*ab8db090SAndroid Build Coastguard Worker <p> 416*ab8db090SAndroid Build Coastguard Worker <code>marisa_cache_level</code> は，キャッシュのサイズを制御するための定数を提供します．<var>MARISA_NORMAL_CACHE</var> を基準として，<var>MARISA_LARGE_CACHE</var> は 2 倍，<var>MARISA_HUGE_CACHE</var> は 4 倍になり，<var>MARISA_SMALL_CACHE</var> は 1/2，<var>MARISA_TINY_CACHE</var> は 1/4 になります． 417*ab8db090SAndroid Build Coastguard Worker </p> 418*ab8db090SAndroid Build Coastguard Worker </div><!-- subsubsection --> 419*ab8db090SAndroid Build Coastguard Worker <div class="subsubsection"> 420*ab8db090SAndroid Build Coastguard Worker <h4>TAIL の種類</h4> 421*ab8db090SAndroid Build Coastguard Worker <div class="float"> 422*ab8db090SAndroid Build Coastguard Worker <pre class="code">typedef enum marisa_tail_mode_ { 423*ab8db090SAndroid Build Coastguard Worker MARISA_TEXT_TAIL = 0x01000, 424*ab8db090SAndroid Build Coastguard Worker MARISA_BINARY_TAIL = 0x02000, 425*ab8db090SAndroid Build Coastguard Worker MARISA_DEFAULT_TAIL = MARISA_TEXT_TAIL, 426*ab8db090SAndroid Build Coastguard Worker} marisa_tail_mode;</pre> 427*ab8db090SAndroid Build Coastguard Worker </div><!-- float --> 428*ab8db090SAndroid Build Coastguard Worker <p> 429*ab8db090SAndroid Build Coastguard Worker libmarisa による辞書では，最後の Patiricia Trie について，ラベルをそのまま保存するようになっています．<code>marisa_tail_mode</code> はラベルの保存方法を選ぶためのパラメータです． 430*ab8db090SAndroid Build Coastguard Worker </p> 431*ab8db090SAndroid Build Coastguard Worker <p> 432*ab8db090SAndroid Build Coastguard Worker <var>MARISA_TEXT_TAIL</var> はラベルを <var>'\0'</var> を終端とする文字列として保存します．そのため，ラベルに <var>'\0'</var> が含まれるときは，自動的に <var>MARISA_BINARY_TAIL</var> へと切り替わるようになっています．明示的に <var>MARISA_BINARY_TAIL</var> を選ぶ理由はほとんどありません． 433*ab8db090SAndroid Build Coastguard Worker </p> 434*ab8db090SAndroid Build Coastguard Worker <p> 435*ab8db090SAndroid Build Coastguard Worker 一方，<var>MARISA_BINARY_TAIL</var> では，ラベルの終端を検出するために，<var>'\0'</var> の代わりにビット列を使用します．そのため，ラベルの平均長が <var>8 bytes</var> を超えるときは <var>MARISA_TEXT_TAIL</var> の方がコンパクトになります． 436*ab8db090SAndroid Build Coastguard Worker </p> 437*ab8db090SAndroid Build Coastguard Worker </div><!-- subsubsection --> 438*ab8db090SAndroid Build Coastguard Worker <div class="subsubsection"> 439*ab8db090SAndroid Build Coastguard Worker <h4>ノードの順序</h4> 440*ab8db090SAndroid Build Coastguard Worker <div class="float"> 441*ab8db090SAndroid Build Coastguard Worker <pre class="code">typedef enum marisa_node_order_ { 442*ab8db090SAndroid Build Coastguard Worker MARISA_LABEL_ORDER = 0x10000, 443*ab8db090SAndroid Build Coastguard Worker MARISA_WEIGHT_ORDER = 0x20000, 444*ab8db090SAndroid Build Coastguard Worker MARISA_DEFAULT_ORDER = MARISA_WEIGHT_ORDER, 445*ab8db090SAndroid Build Coastguard Worker} marisa_node_order;</pre> 446*ab8db090SAndroid Build Coastguard Worker </div><!-- float --> 447*ab8db090SAndroid Build Coastguard Worker <p> 448*ab8db090SAndroid Build Coastguard Worker libmarisa では，ノードの順序が辞書のパラメータになっています．選択肢は <var>MARISA_LABEL_ORDER</var> と <var>MARISA_WEIGHT_ORDER</var> の 2 つであり，前者はラベルが昇順になるようにノードを配列し，後者は重み（出現しやすさ）が降順になるようにノードを配列します．一般的な Trie の実装では <var>MARISA_LABEL_ORDER</var> の順序を用いますが，libmarisa では <var>MARISA_WEIGHT_ORDER</var> がデフォルトになっています． 449*ab8db090SAndroid Build Coastguard Worker </p> 450*ab8db090SAndroid Build Coastguard Worker <p> 451*ab8db090SAndroid Build Coastguard Worker <var>MARISA_WEIGHT_ORDER</var> の目的は，出現しやすいノードから順に並べておくことにより，線形探索の効率を高め，検索時間を短縮することにあります．日本語の単語やフレーズを用いた実験においては，辞書引きにかかる時間を 1/2 程度に短縮できることが確認されています．一方，<var>MARISA_LABEL_ORDER</var> については，検索時間は長くなるものの，Predictive Search の検索結果が文字列昇順になるという特徴があります． 452*ab8db090SAndroid Build Coastguard Worker </p> 453*ab8db090SAndroid Build Coastguard Worker </div><!-- subsubsection --> 454*ab8db090SAndroid Build Coastguard Worker <div class="subsubsection"> 455*ab8db090SAndroid Build Coastguard Worker <h4>別名</h4> 456*ab8db090SAndroid Build Coastguard Worker <div class="float"> 457*ab8db090SAndroid Build Coastguard Worker <pre class="code">namespace marisa { 458*ab8db090SAndroid Build Coastguard Worker typedef ::marisa_error_code ErrorCode; 459*ab8db090SAndroid Build Coastguard Worker typedef ::marisa_cache_level CacheLevel; 460*ab8db090SAndroid Build Coastguard Worker typedef ::marisa_tail_mode TailMode; 461*ab8db090SAndroid Build Coastguard Worker typedef ::marisa_node_order NodeOrder; 462*ab8db090SAndroid Build Coastguard Worker} // namespace marisa</pre> 463*ab8db090SAndroid Build Coastguard Worker </div><!-- float --> 464*ab8db090SAndroid Build Coastguard Worker <p> 465*ab8db090SAndroid Build Coastguard Worker 以上の列挙型については，マクロとの衝突を避けるために，グローバル名前空間にて定義しています．<code>namespace marisa</code> に別名を用意しているので，お好きな方をご利用ください． 466*ab8db090SAndroid Build Coastguard Worker </p> 467*ab8db090SAndroid Build Coastguard Worker </div><!-- subsubsection --> 468*ab8db090SAndroid Build Coastguard Worker </div><!-- subsection --> 469*ab8db090SAndroid Build Coastguard Worker 470*ab8db090SAndroid Build Coastguard Worker <div class="subsection"> 471*ab8db090SAndroid Build Coastguard Worker <h3><a name="exception">class Exception</a></h3> 472*ab8db090SAndroid Build Coastguard Worker <div class="float"> 473*ab8db090SAndroid Build Coastguard Worker <pre class="code">class Exception { 474*ab8db090SAndroid Build Coastguard Worker public: 475*ab8db090SAndroid Build Coastguard Worker const char *filename() const; 476*ab8db090SAndroid Build Coastguard Worker int line() const; 477*ab8db090SAndroid Build Coastguard Worker ErrorCode error_code() const; 478*ab8db090SAndroid Build Coastguard Worker const char *error_message() const; 479*ab8db090SAndroid Build Coastguard Worker 480*ab8db090SAndroid Build Coastguard Worker const char *what() const; 481*ab8db090SAndroid Build Coastguard Worker};</pre> 482*ab8db090SAndroid Build Coastguard Worker </div><!-- float --> 483*ab8db090SAndroid Build Coastguard Worker <p> 484*ab8db090SAndroid Build Coastguard Worker <code>Exception</code> は libmarisa が例外として送出するクラスです．エラーが検出されたファイルの名前（<code>__FILE__</code>）と行番号（<code>__LINE__</code>），さらにエラーコードを取り出せるようになっています．<code>what()</code> は使いやすさのために用意した関数であり，<code>error_message()</code> と同じく，<var>__FILE__:__LINE__: error_code: error_message</var> という書式の文字列を返します． 485*ab8db090SAndroid Build Coastguard Worker </p> 486*ab8db090SAndroid Build Coastguard Worker </div><!-- subsection --> 487*ab8db090SAndroid Build Coastguard Worker 488*ab8db090SAndroid Build Coastguard Worker <div class="subsection"> 489*ab8db090SAndroid Build Coastguard Worker <h3><a name="key">class Key</a></h3> 490*ab8db090SAndroid Build Coastguard Worker <div class="float"> 491*ab8db090SAndroid Build Coastguard Worker <pre class="code">class Key { 492*ab8db090SAndroid Build Coastguard Worker public: 493*ab8db090SAndroid Build Coastguard Worker char operator[](std::size_t i) const; 494*ab8db090SAndroid Build Coastguard Worker const char *ptr() const; 495*ab8db090SAndroid Build Coastguard Worker std::size_t length() const; 496*ab8db090SAndroid Build Coastguard Worker std::size_t id() const; 497*ab8db090SAndroid Build Coastguard Worker};</pre> 498*ab8db090SAndroid Build Coastguard Worker </div><!-- float --> 499*ab8db090SAndroid Build Coastguard Worker <p> 500*ab8db090SAndroid Build Coastguard Worker <code>Key</code> は後述する <a href="#keyset">Keyset</a> および <a href="#agent">Agent</a> のメンバになっているクラスです．登録しようとしている文字列や，検索で見つけた登録文字列の情報を格納するために使われています．基本的な使い方では，既に情報が格納されたインスタンスのみを目にすることになります． 501*ab8db090SAndroid Build Coastguard Worker </p> 502*ab8db090SAndroid Build Coastguard Worker </div><!-- subsection --> 503*ab8db090SAndroid Build Coastguard Worker 504*ab8db090SAndroid Build Coastguard Worker <div class="subsection"> 505*ab8db090SAndroid Build Coastguard Worker <h3><a name="query">class Query</a></h3> 506*ab8db090SAndroid Build Coastguard Worker <div class="float"> 507*ab8db090SAndroid Build Coastguard Worker <pre class="code">class Query { 508*ab8db090SAndroid Build Coastguard Worker public: 509*ab8db090SAndroid Build Coastguard Worker char operator[](std::size_t i) const; 510*ab8db090SAndroid Build Coastguard Worker const char *ptr() const; 511*ab8db090SAndroid Build Coastguard Worker std::size_t length() const; 512*ab8db090SAndroid Build Coastguard Worker std::size_t id() const; 513*ab8db090SAndroid Build Coastguard Worker};</pre> 514*ab8db090SAndroid Build Coastguard Worker </div><!-- float --> 515*ab8db090SAndroid Build Coastguard Worker <p> 516*ab8db090SAndroid Build Coastguard Worker <code>Query</code> は後述する <a href="#agent">Agent</a> のメンバになっているクラスです．検索しようとしている文字列や参照したい登録文字列の ID を格納するようになっています．<code>Query</code> に対する文字列や ID の設定は <code>Agent</code> を介しておこなうため，基本的な使い方では，意識する必要はありません．内容を確認したいときに参照する程度です． 517*ab8db090SAndroid Build Coastguard Worker </p> 518*ab8db090SAndroid Build Coastguard Worker </div><!-- subsection --> 519*ab8db090SAndroid Build Coastguard Worker 520*ab8db090SAndroid Build Coastguard Worker <div class="subsection"> 521*ab8db090SAndroid Build Coastguard Worker <h3><a name="keyset">class Keyset</a></h3> 522*ab8db090SAndroid Build Coastguard Worker <div class="float"> 523*ab8db090SAndroid Build Coastguard Worker <pre class="code">class Keyset { 524*ab8db090SAndroid Build Coastguard Worker public: 525*ab8db090SAndroid Build Coastguard Worker Keyset(); 526*ab8db090SAndroid Build Coastguard Worker 527*ab8db090SAndroid Build Coastguard Worker void push_back(const Key &key); 528*ab8db090SAndroid Build Coastguard Worker void push_back(const Key &key, char end_marker); 529*ab8db090SAndroid Build Coastguard Worker 530*ab8db090SAndroid Build Coastguard Worker void push_back(const char *str); 531*ab8db090SAndroid Build Coastguard Worker void push_back(const char *ptr, 532*ab8db090SAndroid Build Coastguard Worker std::size_t length, 533*ab8db090SAndroid Build Coastguard Worker float weight = 1.0); 534*ab8db090SAndroid Build Coastguard Worker 535*ab8db090SAndroid Build Coastguard Worker const Key &operator[](std::size_t i) const; 536*ab8db090SAndroid Build Coastguard Worker Key &operator[](std::size_t i); 537*ab8db090SAndroid Build Coastguard Worker 538*ab8db090SAndroid Build Coastguard Worker std::size_t num_keys(); 539*ab8db090SAndroid Build Coastguard Worker 540*ab8db090SAndroid Build Coastguard Worker bool empty() const; 541*ab8db090SAndroid Build Coastguard Worker std::size_t size() const; 542*ab8db090SAndroid Build Coastguard Worker std::size_t total_length() const; 543*ab8db090SAndroid Build Coastguard Worker 544*ab8db090SAndroid Build Coastguard Worker void reset(); 545*ab8db090SAndroid Build Coastguard Worker 546*ab8db090SAndroid Build Coastguard Worker void clear(); 547*ab8db090SAndroid Build Coastguard Worker void swap(Keyset &rhs); 548*ab8db090SAndroid Build Coastguard Worker};</pre> 549*ab8db090SAndroid Build Coastguard Worker </div><!-- float --> 550*ab8db090SAndroid Build Coastguard Worker <div class="subsubsection"> 551*ab8db090SAndroid Build Coastguard Worker <h4>概要</h4> 552*ab8db090SAndroid Build Coastguard Worker <p> 553*ab8db090SAndroid Build Coastguard Worker <code>Keyset</code> は辞書に登録しようとしている文字列もしくは登録されている文字列を詰め込むためのクラスです．辞書を構築するときの入力として，あるいは検索結果を保存しておくために使います． 554*ab8db090SAndroid Build Coastguard Worker </p> 555*ab8db090SAndroid Build Coastguard Worker </div><!-- subsubsection --> 556*ab8db090SAndroid Build Coastguard Worker <div class="subsubsection"> 557*ab8db090SAndroid Build Coastguard Worker <h4>辞書の構築</h4> 558*ab8db090SAndroid Build Coastguard Worker <p> 559*ab8db090SAndroid Build Coastguard Worker 辞書の構築に使う場合，<code>push_back()</code> で登録したい文字列を追加してから，後述する <a href="#trie">Trie</a> の <code>build()</code> に渡します．<var>weight</var> は文字列の出現しやすさを示す重みであり，同じ文字列を繰り返し追加した場合，辞書を構築する段階で加算されるようになっています． 560*ab8db090SAndroid Build Coastguard Worker </p> 561*ab8db090SAndroid Build Coastguard Worker <p> 562*ab8db090SAndroid Build Coastguard Worker 辞書を構築した後は，<code>operator[]()</code> により登録文字列の ID を確認できます．その代わり，<code>Key</code> は重みと ID を共用体のメンバとして持つため，辞書の構築に使用した重みを参照できなくなります． 563*ab8db090SAndroid Build Coastguard Worker </p> 564*ab8db090SAndroid Build Coastguard Worker </div><!-- subsubsection --> 565*ab8db090SAndroid Build Coastguard Worker <div class="subsubsection"> 566*ab8db090SAndroid Build Coastguard Worker <h4>検索結果の保存</h4> 567*ab8db090SAndroid Build Coastguard Worker <p> 568*ab8db090SAndroid Build Coastguard Worker 検索結果の保存に使う場合，後述する <a href="#agent">Agent</a> に格納されている検索結果を <code>push_back()</code> に渡すことで，文字列を複製し，ID を残しておくことができます．検索結果の文字列に終端記号を加えたいときは <var>end_marker</var> を利用してください．文字列の長さには影響を与えず，<var>end_marker</var> を終端文字として加えることができます． 569*ab8db090SAndroid Build Coastguard Worker </p> 570*ab8db090SAndroid Build Coastguard Worker <p> 571*ab8db090SAndroid Build Coastguard Worker 検索結果を破棄して別の検索結果を保存するために再利用するという場合，<code>clear()</code> の代わりに <code>reset()</code> を使うことで，既に確保している領域を再利用できます．メモリの確保・解放にかかるオーバーヘッドが気になるときにご利用ください． 572*ab8db090SAndroid Build Coastguard Worker </p> 573*ab8db090SAndroid Build Coastguard Worker <p> 574*ab8db090SAndroid Build Coastguard Worker <code>empty()</code> は文字列が格納されていないかどうかを返す関数です．<code>size()</code> は <code>num_keys()</code> と同じく格納されている文字列の数を返す関数であり，<code>total_length()</code> は格納されている文字列の合計長を byte 単位で返す関数です． 575*ab8db090SAndroid Build Coastguard Worker </p> 576*ab8db090SAndroid Build Coastguard Worker </div><!-- subsubsection --> 577*ab8db090SAndroid Build Coastguard Worker </div><!-- subsection --> 578*ab8db090SAndroid Build Coastguard Worker 579*ab8db090SAndroid Build Coastguard Worker <div class="subsection"> 580*ab8db090SAndroid Build Coastguard Worker <h3><a name="agent">class Agent</a></h3> 581*ab8db090SAndroid Build Coastguard Worker <div class="float"> 582*ab8db090SAndroid Build Coastguard Worker <pre class="code">class Agent { 583*ab8db090SAndroid Build Coastguard Worker public: 584*ab8db090SAndroid Build Coastguard Worker Agent(); 585*ab8db090SAndroid Build Coastguard Worker 586*ab8db090SAndroid Build Coastguard Worker const Query &query() const; 587*ab8db090SAndroid Build Coastguard Worker const Key &key() const; 588*ab8db090SAndroid Build Coastguard Worker 589*ab8db090SAndroid Build Coastguard Worker void set_query(const char *str); 590*ab8db090SAndroid Build Coastguard Worker void set_query(const char *ptr, 591*ab8db090SAndroid Build Coastguard Worker std::size_t length); 592*ab8db090SAndroid Build Coastguard Worker void set_query(std::size_t key_id); 593*ab8db090SAndroid Build Coastguard Worker};</pre> 594*ab8db090SAndroid Build Coastguard Worker </div><!-- float --> 595*ab8db090SAndroid Build Coastguard Worker <p> 596*ab8db090SAndroid Build Coastguard Worker <code>Agent</code> は <code>Query</code> と <code>Key</code> をメンバとして持つクラスです．検索における入出力の受け渡し，および途中経過の保存に使います．後述する <a href="#trie">Trie</a> の検索関数は，例外なく <code>Agent</code> への参照を引数として受け取るようになっています． 597*ab8db090SAndroid Build Coastguard Worker </p> 598*ab8db090SAndroid Build Coastguard Worker <p> 599*ab8db090SAndroid Build Coastguard Worker 検索の手順は，<code>set_query()</code> を使って検索したい文字列もしくは参照したい登録文字列の ID を設定し，<code>Trie</code> の関数に渡した後，<code>key()</code> により検索結果を取り出すという流れになります． 600*ab8db090SAndroid Build Coastguard Worker </p> 601*ab8db090SAndroid Build Coastguard Worker </div><!-- subsection --> 602*ab8db090SAndroid Build Coastguard Worker 603*ab8db090SAndroid Build Coastguard Worker <div class="subsection"> 604*ab8db090SAndroid Build Coastguard Worker <h3><a name="trie">class Trie</a></h3> 605*ab8db090SAndroid Build Coastguard Worker <div class="float"> 606*ab8db090SAndroid Build Coastguard Worker <pre class="code">class Trie { 607*ab8db090SAndroid Build Coastguard Worker public: 608*ab8db090SAndroid Build Coastguard Worker Trie(); 609*ab8db090SAndroid Build Coastguard Worker 610*ab8db090SAndroid Build Coastguard Worker void build(Keyset &keyset, 611*ab8db090SAndroid Build Coastguard Worker int config_flags = 0); 612*ab8db090SAndroid Build Coastguard Worker 613*ab8db090SAndroid Build Coastguard Worker void mmap(const char *filename); 614*ab8db090SAndroid Build Coastguard Worker void map(const void *ptr, 615*ab8db090SAndroid Build Coastguard Worker std::size_t size); 616*ab8db090SAndroid Build Coastguard Worker 617*ab8db090SAndroid Build Coastguard Worker void load(const char *filename); 618*ab8db090SAndroid Build Coastguard Worker void read(int fd); 619*ab8db090SAndroid Build Coastguard Worker 620*ab8db090SAndroid Build Coastguard Worker void save(const char *filename) const; 621*ab8db090SAndroid Build Coastguard Worker void write(int fd) const; 622*ab8db090SAndroid Build Coastguard Worker 623*ab8db090SAndroid Build Coastguard Worker bool lookup(Agent &agent) const; 624*ab8db090SAndroid Build Coastguard Worker void reverse_lookup(Agent &agent) const; 625*ab8db090SAndroid Build Coastguard Worker bool common_prefix_search(Agent &agent) const; 626*ab8db090SAndroid Build Coastguard Worker bool predictive_search(Agent &agent) const; 627*ab8db090SAndroid Build Coastguard Worker 628*ab8db090SAndroid Build Coastguard Worker std::size_t num_tries() const; 629*ab8db090SAndroid Build Coastguard Worker std::size_t num_keys() const; 630*ab8db090SAndroid Build Coastguard Worker std::size_t num_nodes() const; 631*ab8db090SAndroid Build Coastguard Worker 632*ab8db090SAndroid Build Coastguard Worker TailMode tail_mode() const; 633*ab8db090SAndroid Build Coastguard Worker NodeOrder node_order() const; 634*ab8db090SAndroid Build Coastguard Worker 635*ab8db090SAndroid Build Coastguard Worker bool empty() const; 636*ab8db090SAndroid Build Coastguard Worker std::size_t size() const; 637*ab8db090SAndroid Build Coastguard Worker std::size_t io_size() const; 638*ab8db090SAndroid Build Coastguard Worker 639*ab8db090SAndroid Build Coastguard Worker void clear(); 640*ab8db090SAndroid Build Coastguard Worker void swap(Trie &rhs); 641*ab8db090SAndroid Build Coastguard Worker};</pre> 642*ab8db090SAndroid Build Coastguard Worker </div><!-- float --> 643*ab8db090SAndroid Build Coastguard Worker <div class="subsubsection"> 644*ab8db090SAndroid Build Coastguard Worker <h4>概要</h4> 645*ab8db090SAndroid Build Coastguard Worker <p> 646*ab8db090SAndroid Build Coastguard Worker <code>Trie</code> は辞書のクラスです．libmarisa において最も重要なクラスであり，辞書の構築・検索からファイル入出力にいたるまで，あらゆる操作に必要となります． 647*ab8db090SAndroid Build Coastguard Worker </p> 648*ab8db090SAndroid Build Coastguard Worker <p> 649*ab8db090SAndroid Build Coastguard Worker 実際には，辞書のハンドルに相当するクラスであり，辞書の実体がない状況では，<code>build()</code>, <code>mmap()</code>, <code>map()</code>, <code>load()</code>, <code>read()</code>, <code>clear()</code>, <code>swap()</code> 以外の関数を呼び出すと例外が送出されます． 650*ab8db090SAndroid Build Coastguard Worker </p> 651*ab8db090SAndroid Build Coastguard Worker </div><!-- subsubsection --> 652*ab8db090SAndroid Build Coastguard Worker <div class="subsubsection"> 653*ab8db090SAndroid Build Coastguard Worker <h4>辞書の構築</h4> 654*ab8db090SAndroid Build Coastguard Worker <p> 655*ab8db090SAndroid Build Coastguard Worker 辞書の構築には <code>build()</code> を使います．引数は，前述の <a href="#keyset">Keyset</a> と，辞書の設定を XOR（<code>|</code>） で組み合わせた <var>config_flags</var> です．<var>config_flags</var> については，<var>2 | MARISA_BINARY_TAIL</var> のように指定します．この例では，辞書を構成する Patricia Trie の数を <var>2</var> つに制限し，ラベルの保存方法を <var>MARISA_BINARY_TAIL</var> に固定します．省略されているノードの順序とキャッシュのサイズについては，デフォルトの設定である <var>MARISA_DEFAULT_ORDER</var> と <var>MARISA_DEFAULT_CACHE</var> が採用されます． 656*ab8db090SAndroid Build Coastguard Worker </p> 657*ab8db090SAndroid Build Coastguard Worker <p> 658*ab8db090SAndroid Build Coastguard Worker 辞書の構築において登録文字列に割り当てられた ID は，<var>keyset</var> の <code>operator[]()</code> を使って確認できます．登録文字列に対して関連付ける情報がある場合にご利用ください． 659*ab8db090SAndroid Build Coastguard Worker </p> 660*ab8db090SAndroid Build Coastguard Worker </div><!-- subsubsection --> 661*ab8db090SAndroid Build Coastguard Worker <div class="subsubsection"> 662*ab8db090SAndroid Build Coastguard Worker <h4>ファイル入出力</h4> 663*ab8db090SAndroid Build Coastguard Worker <p> 664*ab8db090SAndroid Build Coastguard Worker <code>mmap()</code> は，Memory Mapped I/O により，辞書全体をファイルから読み込むことなく検索できる状態にする関数です．少ししか検索しないのに辞書全体を読み込むのは勿体ないという状況や，異なるプロセスで同じ辞書を共有したいという状況で使うと効果的です．逆に，たくさんの文字列を検索する場合，あらかじめ辞書全体を読み込んでおかないと，外部記憶に対するランダムアクセスにより検索時間が極端に長くなる可能性があります． 665*ab8db090SAndroid Build Coastguard Worker </p> 666*ab8db090SAndroid Build Coastguard Worker <p> 667*ab8db090SAndroid Build Coastguard Worker <code>map()</code> はメモリ上に展開されている辞書のバイナリを使って検索できる状態にする関数です．<code>load()</code> と <code>read()</code> は辞書を入力する関数であり，<code>save()</code> と <code>write()</code> は辞書を出力する関数です． 668*ab8db090SAndroid Build Coastguard Worker </p> 669*ab8db090SAndroid Build Coastguard Worker </div><!-- subsubsection --> 670*ab8db090SAndroid Build Coastguard Worker <div class="subsubsection"> 671*ab8db090SAndroid Build Coastguard Worker <h4>辞書からの検索</h4> 672*ab8db090SAndroid Build Coastguard Worker <p> 673*ab8db090SAndroid Build Coastguard Worker 検索をおこなう関数は <code>lookup()</code>, <code>reverse_lookup()</code>, <code>common_prefix_search()</code>, <code>predictive_search()</code> の 4 種類です． 674*ab8db090SAndroid Build Coastguard Worker </p> 675*ab8db090SAndroid Build Coastguard Worker <ul> 676*ab8db090SAndroid Build Coastguard Worker <li> 677*ab8db090SAndroid Build Coastguard Worker <code>lookup()</code>: 文字列が登録されているかどうかを確認します．登録されていれば <var>true</var> を返します．このとき，<code>agent.key()</code> により検索結果を取り出すことができます．ただし，<code>agent.key().ptr()</code> については，入力として渡された文字列を指しているだけであり，文字列の複製を持っているわけではないことに注意してください．登録されていなければ <var>false</var> を返して終了です． 678*ab8db090SAndroid Build Coastguard Worker </li> 679*ab8db090SAndroid Build Coastguard Worker <li> 680*ab8db090SAndroid Build Coastguard Worker <code>reverse_lookup()</code>: ID から登録文字列を復元します．返り値はなく，復元された文字列は <var>agent.key()</var> を介してアクセスできます．文字列の実体は <var>agent</var> 内部に保持されています．<var>agent</var> を使って次の検索をおこなった段階で失われるものと考えてください．ID が範囲外であれば例外を送出して終了です． 681*ab8db090SAndroid Build Coastguard Worker </li> 682*ab8db090SAndroid Build Coastguard Worker <li> 683*ab8db090SAndroid Build Coastguard Worker <code>common_prefix_search()</code>: 入力文字列の前半部分に一致する登録文字列を検索します．該当する登録文字列があれば <var>true</var> を返します．このとき，<code>agent.key()</code> には検索結果が格納されています．<code>agent.key().ptr() == agent.query().ptr()</code> が成立することに注意してください．該当する登録文字列が複数ある場合，返り値が <var>false</var> になるまで繰り返し <code>common_prefix_search()</code> を呼び出すことにより，すべての検索結果を取得できます． 684*ab8db090SAndroid Build Coastguard Worker </li> 685*ab8db090SAndroid Build Coastguard Worker <li> 686*ab8db090SAndroid Build Coastguard Worker <code>predictive_search()</code>: 入力文字列で始まる登録文字列を検索します．該当する登録文字列があれば <var>true</var> を返します．検索によって復元された文字列には，<code>agent.key()</code> を介してアクセスできます．文字列の実体は，<var>agent</var> 内部に検索の途中経過として保持されているので，<var>agent</var> を使って次の検索をおこなった段階で失われるものと考えてください．該当する登録文字列が複数ある場合，返り値が <var>false</var> になるまで繰り返し <code>predictive_search()</code> を呼び出すことにより，すべての検索結果を取得できます． 687*ab8db090SAndroid Build Coastguard Worker </li> 688*ab8db090SAndroid Build Coastguard Worker </ul> 689*ab8db090SAndroid Build Coastguard Worker <p> 690*ab8db090SAndroid Build Coastguard Worker 繰り返しにより検索が進行する <code>common_prefix_search()</code> と <code>predictive_search()</code> については，<code>agent</code> が検索の途中経過を保持するようになっています．そのため，<code>agent</code> を別の関数に渡したり，<code>agent.set_query()</code> を呼び出したりした時点で，検索の進行はリセットされます． 691*ab8db090SAndroid Build Coastguard Worker </p> 692*ab8db090SAndroid Build Coastguard Worker <p> 693*ab8db090SAndroid Build Coastguard Worker <code>empty()</code> は登録文字列が存在するかどうかを返す関数です．<code>size()</code> は <code>num_keys()</code> と同じく登録文字列の数を返す関数であり，<code>io_size()</code> は辞書をファイルに出力した場合のサイズを返す関数です． 694*ab8db090SAndroid Build Coastguard Worker </p> 695*ab8db090SAndroid Build Coastguard Worker </div><!-- subsubsection --> 696*ab8db090SAndroid Build Coastguard Worker </div><!-- subsection --> 697*ab8db090SAndroid Build Coastguard Worker 698*ab8db090SAndroid Build Coastguard Worker <div class="subsection"> 699*ab8db090SAndroid Build Coastguard Worker <h3><a name="stdio">stdio</a></h3> 700*ab8db090SAndroid Build Coastguard Worker <div class="float"> 701*ab8db090SAndroid Build Coastguard Worker <pre class="code">void fread(std::FILE *file, Trie *trie); 702*ab8db090SAndroid Build Coastguard Workervoid fwrite(std::FILE *file, const Trie &trie);</pre> 703*ab8db090SAndroid Build Coastguard Worker </div><!-- float --> 704*ab8db090SAndroid Build Coastguard Worker <p> 705*ab8db090SAndroid Build Coastguard Worker <code>std::FILE</code> を用いる関数は <kbd>marisa/stdio.h</kbd> で宣言されています．<code>#include <cstdio></code> を入れたくないときは，<kbd>marisa.h</kbd> の代わりに <kbd>marisa/trie.h</kbd> を使ってください． 706*ab8db090SAndroid Build Coastguard Worker </p> 707*ab8db090SAndroid Build Coastguard Worker </div><!-- subsection --> 708*ab8db090SAndroid Build Coastguard Worker 709*ab8db090SAndroid Build Coastguard Worker <div class="subsection"> 710*ab8db090SAndroid Build Coastguard Worker <h3><a name="iostream">iostream</a></h3> 711*ab8db090SAndroid Build Coastguard Worker <div class="float"> 712*ab8db090SAndroid Build Coastguard Worker <pre class="code">std::istream &read(std::istream &stream, Trie *trie); 713*ab8db090SAndroid Build Coastguard Workerstd::ostream &write(std::ostream &stream, const Trie &trie); 714*ab8db090SAndroid Build Coastguard Worker 715*ab8db090SAndroid Build Coastguard Workerstd::istream &operator>>(std::istream &stream, Trie &trie); 716*ab8db090SAndroid Build Coastguard Workerstd::ostream &operator<<(std::ostream &stream, const Trie &trie);</pre> 717*ab8db090SAndroid Build Coastguard Worker </div><!-- float --> 718*ab8db090SAndroid Build Coastguard Worker <p> 719*ab8db090SAndroid Build Coastguard Worker <code>std::iostream</code> を用いる関数は <kbd>marisa/iostream.h</kbd> で宣言されています．<code>#include <iosfwd></code> を入れたくないときは，<kbd>marisa.h</kbd> の代わりに <kbd>marisa/trie.h</kbd> を使ってください． 720*ab8db090SAndroid Build Coastguard Worker </p> 721*ab8db090SAndroid Build Coastguard Worker </div><!-- subsection --> 722*ab8db090SAndroid Build Coastguard Worker </div><!-- section --> 723*ab8db090SAndroid Build Coastguard Worker 724*ab8db090SAndroid Build Coastguard Worker <div class="section"> 725*ab8db090SAndroid Build Coastguard Worker <h2><a name="compatibility">辞書の互換性</a></h2> 726*ab8db090SAndroid Build Coastguard Worker <p> 727*ab8db090SAndroid Build Coastguard Worker libmarisa により構築される辞書の書式はアーキテクチャに依存します．Little Endian な環境で構築した辞書は，Big Endian な環境では使えません．あらためて構築しなおす必要があります．また，Little Endian 形式の辞書は 32/64-bit 環境における互換性があるのに対し，Big Endian 形式の辞書は 32/64-bit 環境における互換性がありません． 728*ab8db090SAndroid Build Coastguard Worker </p> 729*ab8db090SAndroid Build Coastguard Worker </div><!-- section --> 730*ab8db090SAndroid Build Coastguard Worker 731*ab8db090SAndroid Build Coastguard Worker <div class="section"> 732*ab8db090SAndroid Build Coastguard Worker <h2><a name="references">参考資料</a></h2> 733*ab8db090SAndroid Build Coastguard Worker <ul> 734*ab8db090SAndroid Build Coastguard Worker <li><a href="http://www.anlp.jp/proceedings/annual_meeting/2011/html/program.html">言語処理学会第 17 回年次大会（NLP2011）</a> 735*ab8db090SAndroid Build Coastguard Worker <ul> 736*ab8db090SAndroid Build Coastguard Worker <li>言語処理学会年次大会の予稿集が公開されていて，MARISA に関する論文（<a href="http://www.anlp.jp/proceedings/annual_meeting/2011/pdf_dir/F2-6.pdf">F2-6.pdf</a>）をダウンロードできます．</li> 737*ab8db090SAndroid Build Coastguard Worker </ul> 738*ab8db090SAndroid Build Coastguard Worker </li> 739*ab8db090SAndroid Build Coastguard Worker <li><a href="http://d.hatena.ne.jp/s-yata/20110310/1299777228">発表資料（Prefix/Patricia Trie の入れ子による辞書圧縮）</a> 740*ab8db090SAndroid Build Coastguard Worker <ul> 741*ab8db090SAndroid Build Coastguard Worker <li>MARISA に関する発表資料（<a href="https://sites.google.com/site/headdythehero/cabine/2011/0311/NLP2011-F2-6.pptx?attredirects=0&d=1">NLP2011-F2-6.pptx</a>, <a href="https://sites.google.com/site/headdythehero/cabine/2011/0311/NLP2011-F2-6.pdf?attredirects=0&d=1">NLP2011-F2-6.pdf</a>, <a href="https://sites.google.com/site/headdythehero/cabine/2011/0311/NLP2011-F2-6-notes.pdf?attredirects=0&d=1">NLP2011-F2-6-notes.pdf</a>）をダウンロードできます．</li> 742*ab8db090SAndroid Build Coastguard Worker </ul> 743*ab8db090SAndroid Build Coastguard Worker </li> 744*ab8db090SAndroid Build Coastguard Worker </ul> 745*ab8db090SAndroid Build Coastguard Worker </div><!-- section --> 746*ab8db090SAndroid Build Coastguard Worker 747*ab8db090SAndroid Build Coastguard Worker <div class="section"> 748*ab8db090SAndroid Build Coastguard Worker <h2><a name="conclusion">おわりに</a></h2> 749*ab8db090SAndroid Build Coastguard Worker <p> 750*ab8db090SAndroid Build Coastguard Worker 質問などありましたら，欄外のメールアドレス宛てに，お気軽にご連絡ください． 751*ab8db090SAndroid Build Coastguard Worker </p> 752*ab8db090SAndroid Build Coastguard Worker </div><!-- section --> 753*ab8db090SAndroid Build Coastguard Worker </div><!-- body --> 754*ab8db090SAndroid Build Coastguard Worker <div id="footer"> 755*ab8db090SAndroid Build Coastguard Worker <div class="left">MARISA: Matching Algorithm with Recursively Implemented StorAge</div> 756*ab8db090SAndroid Build Coastguard Worker <div class="right"> 757*ab8db090SAndroid Build Coastguard Worker [email protected] 758*ab8db090SAndroid Build Coastguard Worker </div> 759*ab8db090SAndroid Build Coastguard Worker <div class="end"></div> 760*ab8db090SAndroid Build Coastguard Worker </div><!-- footer --> 761*ab8db090SAndroid Build Coastguard Worker </body> 762*ab8db090SAndroid Build Coastguard Worker</html> 763