TAIL のバイナリモードとテキストモード

概要

marisa-trie にて選択できる TAIL の実装は，TAIL なし（MARISA_WITHOUT_TAIL），バイナリモード（MARISA_BINARY_TAIL），テキストモード（MARISA_TEXT_TAIL）の 3 種類です．それぞれの簡単な説明は以下の通りです．

# marisa-0.0.1 ではテキストモードのみでしたが，marisa-0.1.0 にてバイナリモードを追加しました．

  • TAIL なし（MARISA_WITHOUT_TAIL）
    • 最後段のトライでラベルの長さを 1 byte に限定します．
    • 2 bytes 以上のラベルがないので TAIL は必要ありません．
  • バイナリモード（MARISA_BINARY_TAIL）
    • ラベルを文字列の開始位置と終了位置（正確には次の文字列の開始位置）の組で参照するようにします．
    • 出現する順番通りにラベルを TAIL に格納する必要があります．
  • テキストモード（MARISA_TEXT_TAIL）
    • ラベルを文字列の開始位置から終端記号が現れるまでとします．
    • 終端記号用の領域が必要になるものの，ラベルの順番を任意に変更できます．

終端記号を必要とするテキストモードの方が不利に見えるかもしれませんが，ラベルの順序を任意に変更できるという特徴から，重複しているラベルを併合できるという利点が生まれるので，どちらかというとテキストモードの方がコンパクトになる傾向にあります．また，marisa-trie では，ラベルの位置情報を格納する方法が少し特殊なので，検索時に連続する位置情報を取り出さなければならないバイナリモードは，時間的にも不利になっています．

そういうわけで，デフォルトの設定では，最初にテキストモードを試して，ダメだったらバイナリモードに切り替えるようにしています．

テキストモード：ラベルの併合

終端記号を用いる文字列の特徴に，開始位置をずらすだけで後方部分列を取り出せることがあります．そして，この特徴を利用することにより，完全に一致する文字列だけでなく，後方部分列も併合することができます．C 言語の感覚で 1 つの例を示すとすれば，例えば，("ABC"+1) と "BC" は文字列として等しいということです．

ラベルを併合するときは，すべてのラベルを逆順に変換してから（"XYZ" -> "ZYX"），それらを降順に整列しなおします．次の手順では，直前のラベルに前方一致するようなラベルを併合していきます．例えば，"XYZ" の次に "XY" が現れたのであれば，"XY" を "XYZ" に併合します．後は，再び逆順に変換して連結すれば，TAIL のできあがりです．

バイナリモード：TAIL との照合

バイナリモードで TAIL を参照するときは開始位置と終了位置を組にすると説明しましたが，ラベルの長さは 2 bytes 以上ということが確定しているので，1 byte 目の照合については開始位置のみで事足ります．そのため，開始位置をたよりに 1 byte 目を照合し，一致した場合にのみ終了位置を取得するようにしています．