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