SAIS(Suffix Array - Induced Sorting)

計算機科学

SAIS論文を読了した。これは賢いなあと思った。ので概要だけ書いておく。

参考: SACAs(Suffix Array Construction Algorithms)


本手法ではLMS-substringという可変長の部分文字列を使って再帰的にsuffix arrayを構築する。再帰時に文字列長は最大でも1/2のサイズになるため高速な構築が期待できる。ただし構築に必要なメモリ空間は従来のsuffix arrayと変わらない。

まず文字列S(長さはn)のそれぞれの文字にSまたはLというフラグを立てる。直後の文字より小さければS、大きければL、同じならば同じフラグを付ける。文字列の末尾には$という記号がついていて、これはあらゆる文字より小さく、フラグはSとする。例えば

abracadabra$
SSLSLSLSSLLS

となる。ここで直前の文字がLで、自分がSであるような文字をLMS-charとする。先程の例でLMS-charに該当する文字には*をつけた。

abracadabra$
SSLSLSLSSLLS
   * * *   *

ここで*で挟まれた文字列(と末尾の$)をLMS-substringという。この例では

aca
ada
abra$
$

の4つが該当する。
ここで、LMS-substringに対してsuffix arrayが構築されている場合にはinduced sortingという方法を使うと元の文字列Sに対するsuffix arrayが構築できる。induced sortingはO(n)であり文字列長に対して線形でソートできるため高速。(この部分はちょっと複雑なので元論文を参照いただきたい。)
LMS-substringに対するsuffix arrayの構築は本手法を再帰的に適用すればよい。(一つのLMS-substringを1文字とみなした文字列S1に対してSAISを実行する。)ここで↑のabracadabraの例のようにLMS-substringに重複したものが無ければ単純にLMS-substringをソートすることでsuffix arrayの構築ができる。再帰呼び出しを繰り返すと最終的には重複のないLMS-substringができるのでこの時点で再帰が終わる。
と、ここまではKAアルゴリズムという既存の手法と同じ(たぶん)。SAISの新しいところは重複のないLMS-substringに対して行われるソート部分。この部分のソートを普通の手法でやるとO(nlog(n))かかってしまう。KAアルゴリズムではテーブルを用意することでこの問題を解決しているが、これでは余分なメモリを使ってしまう。
本論文ではsuffixが持つ性質からinduced sortingがこの部分でも適用することができるよ、という事を述べている。induced sortingであれば余分なメモリを使わずにO(n)でソートができる。ここがSAISの画期的な点。

まとめると

SAIS
  1: 文字列SからLMS-substringを切り出す
  2: LMS-substringのsuffix arrayを得る
    2-1: LMS-substringをinduced sortする
    2-2: 重複があれば再帰的にSAISを実行
  3: LMS-substringのsuffix arrayを使ってinduced sortする

となる。

なお本論文ではSAISのような可変長部分文字列を使う方法とは別に固定長文字列を使ったSADSという手法も提案していて、そちらも興味深い。