CSA vs FM-index - DO++

今年もCopressed Suffix Arrays (CSA) とFM-indexに関する論文がたくさんでている。話は理論的なものからより実用面での話しに変わってきている。 CSA、FM-indexどちらもBWTをベースにしていて、nバイトをインデクシングするのに4nバイトかかるSAをそのまま保存するかわりにCSAはψ、Fm-indexはBWT後のテキストを圧縮した形（rank操作付き）で保存する。FM-indexはψ^{-1}の情報（のようなもの）を保持しているので対称なindexともいえる。 今後は圧縮率ではなく検索速度の方が重要になってくると思われる。今はまだ圧縮なしSAよりはるかに遅い（実装やパラメーターにもよるけど、まだ十倍程度の差がある）。パターン長を変えたときの比較がよくあるが、圧縮Hgt配列をCSAに組み合わせての検索ってまだないのだろうか。そうするとパターン長に依存せず

[kontonb]

CSA vs FM-index: DO++