SACAs(Suffix Array Construction Algorithms)
先日のnlp2010で岡野原さんが紹介されていたSAISの論文を調査中。
Two Efficient Algorithms for Linear Suffix Array Construction
まだ全部理解していないのだが、Introductionに書いてあったSACAs(Suffix Array Construction Algorithms)というのが面白かったのでメモ。
SACAsというのは特にそういうアルゴリズムがあるのではなく、SuffixArrayの構築に関するアルゴリズムの総称らしい。Compressed Suffix Arrayは最終的なインデックスサイズを圧縮する方法だったので、SACAsとは異なる(たぶん)。
同論文によるとSACAsで代表的なのはKSとKAの2種類だとか。どちらも分割統治によって部分的にSuffixArrayを作ってマージする方法。KSは固定長に分割するので仕組みが簡単。一回の分割でサイズが2/3になる。KAは可変長に分割するため複雑な反面、分割によってサイズが1/2になるため時間・空間の効率が良いことが期待できる。
で、本論文は上記の2手法よりも時間・空間両方で効率のよい手法を考えましたよ、というものらしい。面白そう。(しかもC++コードで100行とか。すごい)
このあたりの話は岡野原さんが非常に詳しいので↓も併せて読んでおきたいところ。というか先に読んだ方がいいのかも。
余談だが、こういうのもあるみたい。こっちも読まないと。
