接尾辞配列

接尾辞配列は、全接尾辞の開始位置を辞書順に保存する。テキストを固定して多くのパターンを検索するなら、索引を一度作り、各問い合わせを二分探索できる。本レッスンの接頭辞倍増法による構築は O(n log² n) 時間だ。

索引が保存するのは接尾辞のコピーではなく位置。BANANA の位置 3 は接尾辞 ANA を表し、配列は六つの開始位置だけを持つ。文字は元テキストから読む。位置の索引なら O(n)、全接尾辞のコピーなら O(n²) の記憶域を使う。

接尾辞配列の仕組み

長さ n のテキストで接尾辞 i は text[i:]。BANANA の並びは次のようになる。

接尾辞全体を直接比較する構築は簡単だが、一比較で O(n) 文字を調べうる。接頭辞倍増法は、比較対象を整数の組へ変える。

まず各文字へランクを付け、同じ先頭文字には同じランクを与える。ランクが各接尾辞の先頭 k 文字を区別するとき、接尾辞 i の先頭 2k 文字を (rank[i], rank[i + k]) で表せる。前半が最初の k 文字ブロック、後半が次のブロック。二番目の開始位置が末尾を越えたら -1 とし、共通接頭辞を持つ短い接尾辞を先に置く。例えば A は ANA より前になる。

整数の組を整列し、同じ組には同じ新ランクを付ける。隣り合う組が変わればランクを増やす。新ランクは 2k 文字を区別するので、k を倍にして繰り返す。全ランクが一意になれば接尾辞順が確定する。

検索は二分探索の下限探索を使う。中央の接尾辞からパターン長の接頭辞を取り、パターンと比べる。接頭辞が小さければ lo を右へ、同じか大きければ hi を左へ動かす。同じでも左へ行くのは、一致範囲の左端を求めるためだ。区間が閉じたら、一回の startswith で候補を確認する。

接尾辞配列のステップ

既定では text = "BANANA" の索引を作り、pattern = "ANA" を探す。

1. 文字順は A < B < N で、ランクは 0、1、2。テキスト位置順に書くと rank = [1, 0, 2, 0, 2, 0]。
2. k = 1 では、開始 0 のキーは (1, 0)、1 と 3 は (0, 2)、2 と 4 は (2, 0)。5 は A の後に文字がないため (0, -1)。
3. 整列結果は [5, 1, 3, 0, 2, 4]。1 と 3、2 と 4 はまだ同順位。元の開始位置順へ書き戻す新ランクは [2, 1, 3, 1, 3, 0]。
4. k = 2 へ倍増する。前回のランクは二文字を区別する。開始 1 のブロックは AN | AN で、両方の AN のランクが 1 なので (1, 1) が四文字の接頭辞を表す。全キーは、5 が (0, -1)、1 が (1, 1)、3 が (1, 0)、0 が (2, 3)、2 が (3, 3)、4 が (3, -1)。
5. 再整列すると [5, 3, 1, 0, 4, 2]。新ランクは全て一意になり、構築を止める。A, ANA, ANANA, BANANA, NA, NANA の順を、文字列の個別保存なしで表せる。
6. 検索区間は [0, 6)。mid = 3 は開始位置 0 を指し、接頭辞は BAN。BAN > ANA なので hi = 3。
7. mid = 1 は開始位置 3 で、接頭辞は ANA。同じでも hi = 1 として左端を探し続ける。
8. mid = 0 は開始位置 5 で、接頭辞は A だけ。A < ANA なので lo = 1 とし、lo == hi になる。
9. SA[1] = 3。BANANA は添字 3 から ANA で始まるため、find_one は 3 を返す。

ANA はテキストの添字 1 にも現れる。それでも 3 は正しい。この関数が返すのは接尾辞配列順で最初の一致で、最小のテキスト添字ではない。全出現位置を求めるなら、一致する接頭辞範囲の右端も求め、その区間の開始位置を集める。

時間計算量と空間計算量

テキスト長を n、パターン長を m とする。

倍増は O(log n) 回。各回で定数サイズの組を n 個作り、O(n log n) の比較ソートを行うため、合計 O(n log² n) となる。整数ランクの基数ソートや計数ソートを使えば O(n log n) にできるが、表示コードはその実装ではない。

二分探索は O(log n) 回探査し、各回で高々 m 文字を比較する。教材のコードは接頭辞をスライスするため、一時的に O(m) 文字を持ちうる。添字で直接比較すれば割り当てを避けられ、時間の上界は変わらない。

一つのテキストへ何度も問い合わせるなら、構築コストを検索全体で分担できる。一回だけなら text.find(pattern) が通常適する。同じパターンを多くの到来テキストに使うなら、KMP はパターン側を前処理する。

境界ケース

• 一文字テキストでは接尾辞は一つ。初期ランクで決まり、倍増ループは実行しない。
• AAAAAAAA は k = 1, 2, 4 で同順位の群を残し、画面の八文字上限では最長の構築トレースになる。
• 接尾辞が二番目のブロック内で終わる場合も、末尾の -1 と前回のブロックランクが短い接尾辞を先に置く。範囲外の番兵を実ランク 0 に替えてはいけない。
• パターンがテキストより長くても二分探索は閉じ、最後の確認に失敗して -1 を返す。
• 複数の出現があれば、find_one は接尾辞配列順の位置を返し、最小のテキスト添字とは限らない。
• 純粋な構築関数は空テキストを SA = [] として扱う。UI は空パターンの規約の違いを避け、テキストとパターンを非空に制限する。

よくある間違い

• 全ての text[i:] をコピーし、構築前から O(n²) 空間を使う。配列に保存するのは開始位置だ。
• 末尾に 0 を使う。0 は実在する文字クラスのランクなので、番兵は全ての実ランクより小さくする。
• 新ランクの計算中に rank を上書きする。同じ回の全キーは同じ旧配列を読む必要があり、next_rank へ書いてから切り替える。
• rank[i] だけを比べる。二番目のブロックがなければ、区別できる接頭辞長を倍にできない。
• 二分探索で最初の等値を見つけて止める。一致は見つかっても下限ではない。左端が必要なら等値でも hi = mid とする。
• 現在の構築を O(n log n) と呼ぶ。各回が比較ソートなので O(n log² n)。速い上界には別の整列処理が必要になる。