Suffix Array

Suffix Array ということで、軽く言及。

もう一つの難点は、そろそろトウが立っていること。アルゴリズムというのは比較的経年変化の少ない分野ではあるけれども、それでもその後見つかった新たなアルゴリズムだって知りたい。たとえばSuffix Arrayとかは、分かりやすくて使い易い、もっと知られてもいいアルゴリズムなのに、まだこの手の本に取り上げられた例というのがありません。

Suffix Array って名前で proceedings に載ったのが1990年*1、Journal に載ったのが1993年で*2 、Mastering Algorithm with Perl の出版が1999年だから、新しいとか古いとかそういう問題ではないと思うがなぁ。
まぁ、アルゴリズムの教科書レベルの本で Suffix Array を取り扱ったとしても、Suffix Array の構築コストは結構高いし、テキストの更新があると再構築だしで使いにくいかなぁ、とか思ったり。まぁ、自分は Suffix Array 使ってすべての任意部分文字列の統計量を線形時間で計算する*3なんてことを去年やってたわけだけど、Suffix Array なんかより Double Array Trie とか Multikey Quick Sort とかの方が汎用性があっていいかなぁと思う。ちょい難しいけど。
しかし、Suffix Array は線形時間で構築するアルゴリズムがあったり、統計量を扱ったり、圧縮したり、それだけで本が1冊くらいにはなりそうではある。

*1:U. Manber and G. Myers. Suffix arrays: A new method fo on-line string searches. In Ist ACM-SIAM Symp. on Discrete Algorithms, pages 319 -- 327, San Fancisco, 1990.

*2:U. Manber and G. Myers. Suffix arrays: a new method for on-line string searches. SIAM Journal of Computing, 22(5):935-948, 1993.

*3:Suffix Array の構築含む