marisa-trie の解説まとめ
どのような読者を想定しているのか甚だ疑問な連載と化していましたが,とりあえず,今までの記事をまとめておきます.
marisa-trie における rank/select の実装
rank/select の索引については,ブロック単位で rank/select の値を保存するという基本的な構造を使用しています.後は,PopCount の使い方を少し工夫してみたり,あらかじめ計算しておいたテーブルを使って効率化してみたりという内容です.rank/select の効率は検索時間に対する影響が大きいので,とても大事なところです.
世の中には二種類の文字列がある…
0 を終端とする文字列と,始点と長さにより表現される文字列,どちらも同じように扱いましょうという内容です.
文字列の前向き・後ろ向き
辞書を構築するとき,ラベルを前向きに参照したり後ろ向きに参照したりするけれど,文字列を複製するのは嫌だし,ほとんど同じ内容の関数を 2 種類用意するのも嫌….そんなわけで,文字列の使い分けと同じように対処してしまおうという内容です.
marisa-trie におけるラベル・リンクの格納方法
複数のトライと TAIL を組み合わせて辞書を構成するには,トライからトライへのリンク,トライから TAIL へのリンクが必要になります.この記事では,ラベルの格納方法と絡めて,リンクの格納方法について説明しています.
TAIL のバイナリモードとテキストモード
2 種類の TAIL について,それぞれの構造と特徴の簡単な説明になっています.