marisa-0.1 系と marisa-0.2 系の違いをまとめてみる

# 書いている途中で寝てしまったので，一日遅れでお送りしています．

LOUDS ベースの Patricia Trie を入れ子にするというコンセプトで開発された marisa-0.1 系と marisa-0.2 系ですが，インタフェースが大きく異なるという目に見える違いの他にも，いくつかの相違点があります．それは例えば，いくつかのオプションが廃止されたことであったり，幅優先探索による Predictive Search がサポートされなくなったことであったり，64 ビット環境用のコードが追加されたことであったりします．

今回の記事は，これら marisa-0.1 と marisa-0.2 の違いをまとめた内容になっています．とはいっても，思い出したことを並べただけなので，可読性に難ありです．

インタフェース

前述したように，特に分かりやすいのがインタフェースの違いです．

新しいクラスの導入

marisa-0.1 系では const char * const * や std::vector を使うようになっていましたが，marisa-0.2 系では構築や検索における入出力用のクラスが提供されています．

例えば，marisa::Keyset は，std::vector<std::pair<std::string, double> >（キーと重みの組を配列にしたもの）と std::vector<UInt32>（キー ID の配列）を組み合わせたようなクラスになっていて，辞書の構築に使う以外に，検索結果の保存にも使えます．marisa::Keyset の導入によって，誰が使う場合でも同じようなコードになり，それで高い性能を発揮するようになっています．

もう一つの重要なクラスが marisa::Agent です．こちらは，検索の入出力と内部状態をまとめたクラスであり，検索のインタフェースを統一しつつ，逐次検索を可能とすることが導入の目的です．marisa-0.1 系でもコールバックを上手く利用すれば対話的に検索できたのですが，そのようなコールバック関数を適切に設計するのはヒジョーに面倒でした．一方，marisa-0.2 系のインタフェースであれば，単純なループで検索を進めることができます．

入出力インタフェース

辞書を入出力する関数について，marisa-0.2 系では，読み込み位置や書き込み位置を変更できないようにしました．一つのファイルに複数の辞書を保存したり，ファイルの途中に辞書を埋め込んだりするには，ユーザ側で std::FILE や std::fstream を管理する必要があります．一方で，marisa::Trie にメモリマッピング用のハンドルを持たせるようにしたたため，ユーザ側で marisa::Mapper を意識する必要はなくなっています．

また，std::FILE や std::iostream を用いるインタフェースを個別のヘッダに記述することで，標準ライブラリへの依存関係を減らせるようにしてあります．#include <marisa.h> は #include <cstdio> や #include <iosfwd> を挿入するようになっていますが，std::FILE や std::iostream が不要な状況であれば，#include <marisa/trie.h> を代わりに使うことができます．

整数型の変更

marisa-0.2 系では，marisa::UInt32 をインタフェースとして使うことを避け，代わりに std::size_t を使うようにしています．理由としては，marisa::UInt32 という型を明示的に使うのが面倒だということが挙げられます．実際には，64 ビット整数から marisa::UInt32 への暗黙的なキャストに対して警告をしてくれる Visual C++ の存在が嬉しいような忌々しいような…，という微妙な裏事情もあります．

# そういえば，64 ビット版の Windows 環境では試していません．警告やエラーが出ないようになっていればよいのですが…．

一方で，ライブラリの内部では marisa::UInt32 を使うようにしています．理由は，64 ビット環境におけるメモリ消費を抑えるためです．marisa::Keyset を導入した影響もあり，辞書の構築に必要となる領域は 70% 以下に抑えられています．

実数型の変更

辞書を構築するときに指定する重みについて，メモリ消費を抑えるために，double ではなく float を使うように変更しました．ただし，重みの計算において発生する誤差を抑えるため，重みを計算するときは倍精度でおこなうようにしています．

廃止したもの

空間効率や時間効率を悪化させてしまうだけなので，MARISA_PREFIX_TRIE と MARISA_WITHOUT_TAIL は廃止しました．同時に，MARISA_PATRICIA_TRIE というオプションも廃止されています．

登録文字列を復元せずに ID のみを取り出すという用途は滅多にないと考え，幅優先探索による Predictive Search も廃止しました．marisa-0.2 系では，登録文字列を効率良く復元できる深さ優先タイプのみをサポートしています．

内部実装

64 ビット環境用のコード

marisa::BitVector と marisa::FlatVector について，64 ビット環境用のコードを追加しました．結果として，64 ビット環境における性能がわずかに向上しています．検索時間で評価するのであれば，最大で 5% 程度の短縮につながります．

TAIL のバイナリモード

TAIL のバイナリモードについては，データ構造に変更を加えました．marisa-0.1 系ではラベルを順番に並べておき，始点と終点の組でラベルを切り出すようになっていましたが，marisa-0.2 系では別のビット列に終端かどうかを示すフラグを保存するようにしました．結果として，テキストモードとバイナリモードの差は小さくなっています．

TAIL の構造はそのままに，単調増加になるという特徴を利用してリンク情報を圧縮することも考えたのですが，モードによって参照方法を変更しなければならないという欠点が厄介なので，最終的には追加のビット列を使うという方法を採用しました．

共有ライブラリ化（追記 2011-04-11）

marisa-0.1 系はスタティックライブラリでしたが，marisa-0.2 系は共有ライブラリになっています．