ゴリラでもわかるSA-ISZennqdot3🦍ゴリラでもわかるSA-IS2024/10/14に公開RuststringAtCoderアルゴリズムtech初めにSA-IS[1]は接尾字配列を線形時間[2]で構築できるアルゴリズムの1つです。他の線形時間アルゴリズムと比較して高速かつ省メモリであり、コードもコンパクトです。SA-KASA-ISはSA-KA[3]を改良したものです。そこで、SA-ISの解説に入る前にSA-KAを概観します。SA-KAという名称は一般的ではないかもしれません。以下では、文字列Sのi文字目をS[i]と表記します。部分文字列S[i]..S[j]をS[i..j]と略記します。接尾字はS[i..n]です。Sは辞書順最小の(ユニークな)番兵\#を末尾に持ちます。これは証明の見通しをよくするためです。実装上は必要ありません。1..n]のとき、S[i..n]およびS[i]をL型・S型と定義します。番兵は常にS型とします。すべての接尾字はL型かS型に分類されます。接尾辞の長さが異なるため、等号が成立することはありません。線形時間でL型・S型を決定できる。Sを右から左に走査する。(1)S[i]=S[i+1]ならばS[i]とs[i+1]は同じ型。S[i+1]ならばS[i]はそれぞれL型・S型。L型・S型の接尾辞の一方がソート済みであれば、他方も線形時間でソートできる。S型の接尾辞がソートされている場合、後述のアルゴリズム1でソートできる。L型の接尾辞がソートされている場合も同様。これが、SA-ISおよびSA-KAで肝となる補題です。これにより、L型・S型の接尾辞の一方のみを線形時間で整列できればよいことが分かりました。番兵は1度しか登場しないことに注意します。S[i]=S[j]を満足するS型のS[i]とL型のS[j]を考えます。S[j+1]よりS[i..n]>S[j..n]が成り立ちます。接尾字配列において接尾辞が頭文字ごとにまとまっていることは自明です。このまとまりをバケットと呼ぶことにします。補題3はバケットの左側にL型が右側にS型が集まっていることを意味します。接尾字配列をSAとします。(1)ソート済みのS型接尾辞を右から左に走査し、SAのバケットに右から詰めていきます。SA[1]は番兵です。(2)SAを左から右にたどります。SA[i]が必ず存在します。S[SA[i]-1]がL型であれば、バケットの左から詰めていきます。小さな接尾辞に頭文字を追加してL型の接尾字を構築しています。SAを左から走査することでバケット内で小さなものから順に作られます。L型の接尾字SA[i]から頭文字を除いた部分SA[j]について、i>jが成り立ちます。SA[j]はソート済みです。形式的な証明は原著論文[3:1]を参照してください。丁寧な説明SA[1]=nは番兵\#です。番兵の次に小さな文字を\alphaとします。\alphaから始まる接尾字のうちL型のものは\alpha\dots\alpha\#の形に限られます。したがって、SAを左から走査することでバケット\alphaはソートされます。同様に、\alphaの次に小さな文字\betaから始まる接尾字は\beta\dots\beta\#または\beta\dots\beta\alpha\dots\#のみがL型です。前者が辞書順でバケットに詰められ、後者がそれに続きます。残る問題はL型・S型の接尾字の一方を線形時間でソートする方法ですが、これはSA-ISで解説することにします。基本的な考え方は同じですが、実装がより簡単だからです。SA-ISアルゴリズム1ではすべてのS型接尾字がソート済みであることを要求していますが、実際に使用されているのはL型の右にあるS型のみです。したがって、すべてのS型をソートする必要はありません。S型の文字S[i]のうちS[i-1]がL型のものを、とくにLMS型[4]と定義する。(1)LMS型を大きいものから順にバケットの右から詰める。(2)SAを左から右に走査する。SA[i]が存在し、S[SA[i]-1]がL型であれば、バケットに左から詰める。(3)SAを右から左に走査する。SA[i]が存在し、S[SA[i]+1]が(LMS型を含む)S型であれば、バケットに右から詰める。LMS型がある場合は上書きする。LMS型接尾字がソート済みであれば、L型接尾辞を線形時間でソートでき、S型接尾辞も線形時間でソートできる。補題2とアルゴリズム2より。残る問題はLMS型の接尾字を線形時間でソートすることです。\rceil個あるので、愚直にソートする訳にはいきません。そこで、LMS型接尾字を比較できるように文字列を圧縮することを考えます。LMS部分文字列を次のように定義する。