marisa-trie におけるラベル・リンクの格納方法

概要

marisa-trie では，1 byte のラベル（Single-byte（SB）ラベル）は各トライに格納し，2 bytes 以上のラベル（Multi-byte（MB）ラベル）は次のトライもしくは TAIL に格納するようになっています．そのため，SB/MB ラベルを区別するためのフラグを各ノードに持たせるとともに，SB ラベルを格納する領域と MB ラベルへのリンクを格納する領域を用意しています．

以下は，もう少し詳しい内容です．

ノード単位での実装

フラグ・ラベル・リンクを格納する簡単な方法は，これらの要素を各ノードに区別なく持たせることです．しかし，SB ラベルを持つノードと MB ラベルを持つノードでは割り当てるべき領域の大きさが異なるため，かなりの無駄が発生します．例えば，SB ラベルの格納に 8 bits，リンクの格納に 20 bits を使うのであれば，フラグも併せて各ノードを 21 bits で表現することになり，SB ラベルを持つノードに対しては 12 bits を余分に割り当ててしまいます．

ラベル・リンクの分割

次の案は，ラベルとリンクを別々に格納するというものです．分割に利用するのは，SB/MB ラベルを区別するフラグを格納しているビット列に対する rank 関数です．すなわち，flags[i] が false であれば labels[flags.rank0(i)] を参照し，flags[i] が true であれば links[flags.rank1(i)] を参照するようにします．

この方法であれば，flags に対して rank 関数用の索引を与えるだけで，ラベル用の領域とリンク用の領域を分割することができます．SB ラベルを持つノードには (9+α) bits，MB ラベルを持つノードには (21+α) bits という割り当てになるため，領域を無駄にすることがなく，高い空間効率を実現できます．

しかしながら，ラベル・リンクの取り出しにおいて rank 関数が必要になり，時間計算量は増大します．フラグ・ラベル・リンクを別々に格納することも，キャッシュミスが発生しやすくなるため，時間効率の面からすれば欠点になります．

今回の実装では，木構造の探索において rank 関数より時間計算量の大きい select 関数を使うため，全体として見ると，それほど大きな問題にはなっていません．

ラベル用領域の共有

ラベル・リンクの分割に続いて考えた内容が，ラベル用の領域をリンクの格納にも使うという実装です．すなわち，flags[i] が false であれば labels[i] を参照し，flags[i] が true であれば (labels[i] + (links[flags.rank1(i)] * 256)) を参照するようにします．

この実装では，リンクの取り出しにかかるコストが少しだけ割り増しになるものの，ラベルの取り出しに rank 関数が不要になります．どちらの実装がより高速に動作するのかについては，使い道とデータに依存すると思います．今回はラベル用の領域を共有する方を選択しましたが，ラベル・リンクを完全に分割した方が高速に動作するかもしれません．実際に比較したわけではないため，どちらが本当に速いのかは不明です．