SA-IS(Suffix Array - Induced Sorting)をお勉強しました。 Suffix Array(SA)を線形時間で構築できるすごいやつです。 厳密な証明はめんどくさいので、省略！ｗ
アルゴリズムの概要
だいたい5段階から成ります。
- LMSを求める
- (未ソートの)LMSを使ってInduced SortしてLMS-substringをソート
- LMS-substring列を構成し、そのSAを構築(再帰)
- できたSAからLMSをソート
- ソートしたLMSを使ってInduced Sort
定義
未定義の言葉が沢山あるので、定義しておきます。 文字列は終端文字があるとします。
LとS
文字列\( T \)に対して、
\( T_i < T_{i+1} \)のとき、\( i \)をS-type(Smaller)、
\( T_i > T_{i+1} \) のとき、\( i \)をL-type(Larger)、
と呼びます。
\( T_i = T_{i+1} \)のときは、\( i \)のS/Lは、\( i+1 \)と等しいとします。
終端はSであると取り決めます。
LMS
\( i-1 \)がLで\( i \)がSであるような\( i \)のことをLMS(Left-Most S)と呼びます。 以降、LMSと言ったときにインデックスのことだけでなく、そこから定まるsuffixを指すこともあります。 終端はLMSであると取り決めます。
LMS-substring
となり合うLMSの間の連続部分文字列です。 すなわち、\( i,j \)がLMSであって、全ての\( i < k < j \)がLMSでないようなもので、 \( S_{i..j} \)なる部分列のこと。
LMS-substring列
これは一般的でない言葉だと思います。 LMS-substringを辞書順で昇順に番号をつけて、もとの文字列に登場する順番で並べたものです。
Induced Sort
名前にもなっているようにこれがキモ。 文字列と、そのLMSの並びが与えられたときに、
- LMSの初めの文字でバケットソート
- バケットを前から見ていって、要素の一つ前がLなら適切なバケットの一番前の空きに入れる。(新たに入れたのも処理)
- 1.で入れたLMSを除く。(ただし終端は残す)
- バケットを後ろから見ていって、要素の一つ前がSなら適切なバケットの一番後ろの空きに入れる。
これは二段階ソートを詰めたやつになっている。 二段階ソートは、LとSに分けたあと、Sだけソートすれば、2と同じ手順によってLも含めてソートできるというやつ。 一つ前がLのものだけ興味があるのでLMSだけ見ればいいじゃない、という話になる。
一体何が起こるのか
ここでアルゴリズムの概要を再掲。
- LMSを求める
- (未ソートの)LMSを使ってInduced SortしてLMS-substringをソート
- LMS-substring列を構成し、そのSAを構築(再帰)
- できたSAからLMSをソート
- ソートしたLMSを使ってInduced Sort
もしLMSがソートされていたら、Induced SortするとSAが得られる。(二段階ソートの要領)
LMSをソートするには、LMS-substring列のSAを構築すればよい。(これは例で試せばそれはそう、となる)
そのためにはLMS-substringをソートしたい。
テキトーなLMSの並びでInduced Sortすると実はLMS-substringがソートできる。
これは先頭\( n \)文字でソートされている\( i \)を見て、\( i-1 \)を入れるときに、先頭\( n+1 \)文字でソートされた部分に入るので、
最初初めの1文字だけでソートされていたが、再びLMSが入るまでには対応するLMS-substringの長さ分でソートされるから。
ここが一番すごいところ。一旦正確でない結果を得て、それを利用して正確な結果が得ている。
また、LMS-substringに重複がなければ、LMS-substringをソートしたらLMSもソートできるので再帰をサボれる。
計算量
再帰パート以外は割と明らかに線形なので、再帰のところだけ問題になります。 LMS-substringは必ず長さ3以上なので(終端を除き)、LMS-substring列は長さが元のやつの3分の1程度になるはずです。 そのため、計算量が等比級数になって、線形時間であることがわかります。
元論文
Two Efficient Algorithms for Linear Time Suffix Array Construction
とても頭のよさそうな実装も載っています。