Suffix Array とは

与えられた文字列に対し、取りうる suffix(接尾辞)を辞書順に並べた配列。

文字列のパターンマッチングを効率的に行うためのデータ構造。

パターンマッチ方法 文字列 S(長さ \(n\))中にあるパターン P(長さ \(m\))を全て見つける計算量
逐次走査 \(O(mn)\)
Suffix Array \(O(m \log{n})\)

例えば文字列ABAAACBBAACCには以下の12の suffix がある。

suffix 開始位置
ABAAACBBAACC 0
BAAACBBAACC 1
AAACBBAACC 2
AACBBAACC 3
ACBBAACC 4
CBBAACC 5
BBAACC 6
BAACC 7
AACC 8
ACC 9
CC 10
C 11

Suffix Array はこれを辞書順に並べて、

suffix_array = [
  'AAACBBAACC',
  'AACBBAACC',
  'AACC',
  'ABAAACBBAACC',
  'ACBBAACC',
  'ACC',
  'BAAACBBAACC',
  'BAACC',
  'BBAACC',
  'C',
  'CBBAACC',
  'CC'
]

文字列そのものを配列に格納すると \(O(n^2)\) のメモリを食う。

→ suffix の代わりに、suffix の開始位置を格納する(\(O(n)\))。

suffix_array = [2, 3, 8, 0, 4, 9, 1, 7, 6, 11, 5, 10]

Suffix Array の構築

手順

(TODO)

具体例

(TODO)

Suffix Array によるパターンマッチング

問題設定

【問題】文字列 S 中にあるパターン P の位置を全て見つける

基本的な考え方

  • この問題は、以下のように書き換えられる。
    • 【問題】文字列 S の suffix のうち、その先頭(接頭辞、prefix)がパターン P に一致するものを全て見つける
    • ex. 文字列ABABAA中にあるパターンABの位置を全て見つける場合、6つの suffixABABAA,BABAA,ABAA,BAA,AA,Aのうち、先頭がABのものを見つければ、その suffix の開始位置が求める答えになる
  • Suffix Array では suffix が辞書順に並ぶので、条件を満たす suffix は Suffix Array 中では連続して固まっている
ABABAAの suffix 開始位置 パターンABで始まるか?
A 5 x
AA 4 x
ABAA 2 o
ABABAA 0 o
BAA 3 x
BABAA 1 x

処理の流れ(一例)

例題として、S = ABAAACBBAACBACから P = BAを探す。

1. Suffix Array の構築

文字列 S の suffix_array を構築する

  • 例題の場合、下表に相当する suffix_array が得られる
suffix 開始位置
AAACBBAACBAC 2
AACBAC 8
AACBBAACBAC 3
ABAAACBBAACBAC 0
AC 12
ACBAC 9
ACBBAACBAC 4
BAAACBBAACBAC 1
BAACBAC 7
BAC 11
BBAACBAC 6
C 13
CBAC 10
CBBAACBAC 5
suffix_array = [2, 8, 3, 0, 12, 9, 4, 1, 7, 11, 6, 13, 10, 5]

2. マッチ範囲の左端を探す

Suffix Array を二分探索し、パターン P と一致、もしくは P よりも辞書順が後であるような最小の suffix(suffix_left)を探す。

  • 例題の場合、BAAACBBAACBAC(開始位置:1)を得る

3. パターンマッチ結果の存在チェック

suffix_leftがパターン P で始まるかチェック。

  • 始まるなら1件以上マッチする。次へ
  • 始まらないなら1件もマッチしない。処理終了

4. マッチ範囲の右端を探す

Suffix Array を二分探索し、パターン P で始まる最大の suffix(suffix_right)を探す。

  • 例題の場合、BAC(開始位置:11)を得る

5. 解を求める

suffix_leftsuffix_rightの間にある全ての suffix の開始位置が求める答えとなる。

  • 例題の場合、Suffix Array 内のBAAACBBAACBAC(開始位置:1)とBAC(開始位置:11)の間を調べて 1, 7, 11 が答え