SA_IS法の学習

qdot3

概要

サイズ $N$ の文字列の $i\space(1\le i\le N)$ 文字目以降を取り出した文字列を suffix という。sa_is 法では（ソート済みの） suffix array を時間計算量 $O(N)$ で取り出すことができる。
suffix は開始位置 $i$ で代表できます。これを利用すると、空間計算量も $O(N)$ になることが分かります。

活用例

文字列検索：suffix の preffix をとると、それは部分文字列です。suffix array がソート済みであることに注意すると、二分探索で任意の文字列を検索することができます。例えば文字列 X を検索する場合、「X+{小さな文字}」と「X+{大きな文字}」の場所を検索し、それらが連番であれば X を含まず、そうでなければ X を含みます。

qdot3

実装

0-origin
入力は ascii 文字列を想定。Unicode 文字列の場合は &[char]を引数にとればよい。

fn sa_is(s: &[u8]) -> Vec<usize> {
    let n = s.len();

    match n {
        0 => return vec![],
        1 => return vec![0],
        2 => return if s[0] < s[1] { vec![0, 1] } else { vec![1, 0] },
        _ => (),
    }

    todo!()
}

qdot3

step 1

各 suffix を２つのタイプに分類します。連続する２つの suffix をソートした時、順番が保たれる場合は S-type、逆転するなら L-type です。末尾の１文字は L-type とします。
- ソートが完了すると、先頭１文字が同じなら L-type が S-type よりも前に来ます。これは L/S-type の定義から従います。よって、末尾の１文字は L-type です。
- 例えば、１文字目と２文字目が異なる簡単な場合を考えてみます。１文字目を X とすると、 L-type の２文字目は X より小さく、 S-type の２文字目は X より大きいです。文字列の長さが１文字しかない場合は、２文字目に無限小に相当する文字があると考えればよいです。
- 一般には、「XXX...」よりも、小さいのが L-type、大きいのが S-type です。単一の文字からなる suffix は、「XXX...」よりも短いので L-type です。

qdot3

    let mut is_l_type = vec![true; n];
    for i in (1..n).rev() {
        match s[i-1].cmp(&s[i]) {
            std::cmp::Ordering::Less => is_l_type[i-1] = false,
            std::cmp::Ordering::Equal => is_l_type[i-1] = is_l_type[i],
            std::cmp::Ordering::Greater => (), // is L-type
        }
    }

qdot3

step 2

各 suffix の頭文字でバケットソートをします。そのためにはすべての頭文字について、バケットの開始位置と終了位置を記録しておく必要があります。これらを右半開区間 $[l, r)$ として持ちます。
Unicode 文字列を対象にするときは、登場する文字の数が膨大だがどうする？　現在何文字あるの？　さすがに 32bit 全部は使ってないはず。登場文字数を制限して FxHashMap が現実的？

    let mut is_l_type = vec![true; n];
+   let mut count_char = [0; 256];
+   count_char[s[0] as usize] += 1;
    for i in (1..n).rev() {
        match s[i-1].cmp(&s[i]) {
            std::cmp::Ordering::Less => is_l_type[i-1] = false,
            std::cmp::Ordering::Equal => is_l_type[i-1] = is_l_type[i],
            std::cmp::Ordering::Greater => (), // is L-type
        }
+       count_char[s[i] as usize] += 1;
    }

    let mut bucket_lr = [[0, n]; 256]; // [l, r)
    for (i, count) in (1..256).zip(count_char.into_iter()) {
        bucket_lr[i][0] = bucket_lr[i-1][0] + count;
        bucket_lr[i-1][1] = bucket_lr[i][0]
    }

qdot3

step 3: induced sort

sa: Vec<usize> の各バケットに suffix を詰めていきます。
頭文字が同じであれば L-type が S-type よりも前に来ることが分かっています。そこで、バケットソートの際に、少し工夫をします。
- 「L-type が続く L-type」と「S-type が続く L-type」を比較すると、前者が後者より後に来ます。 S-type についても同様です。
- そこで、「L-type に続く S-type」を特に LMS-type (Left-most S-type) と呼ぶことにし、各バケットの末尾から LMS-type を詰めていきます。LMS-type を詰める順番はでたらめで良いです。それでも部分的にソートされます。理由は後述（したい）。
- sa を正順に走査し、挿入済みの suffix の１つ前が L-type であればバケットの前方から挿入します。同時に、 LMS-type を回収します。
  - このとき、挿入位置は今見ている場所より後方になります。これは L-type の定義から従います。従って、このステップで全ての L-type が挿入されます。
  - ２種類の L-type を挿入していますが問題ありません？
- sa を逆順に走査し、挿入済みの suffix の１つ前が S-type であればバケットの後方から挿入します。

qdot3

このスクラップは4日前にクローズされました