第4回 2019/4/25
- 講師：森下 真一
Suffix Array
接尾辞配列(Suffix Array)とは，接尾辞(Suffix)、つまり「文字列のある位置から末尾までの文字列」を辞書順にソートしたもの。
例)「\(\mathrm{ATGATTCGA\\)}$」
| 開始位置 | Suffix |
|---|---|
| 0 | ATGATTCGA$ |
| 1 | TGATTCGA$ |
| 2 | GATTCGA$ |
| 3 | ATTCGA$ |
| 4 | TTCGA$ |
| 5 | TCGA$ |
| 6 | CGA$ |
| 7 | GA$ |
| 8 | A$ |
| 9 | $ |
これを辞書順(ここではアルファベット順)に並べ替えたものが Suffix Array である。
| 開始位置 | Suffix |
|---|---|
| 9 | $ |
| 8 | A$ |
| 3 | ATTCGA$ |
| 0 | ATGATTCGA$ |
| 5 | TCGA$ |
| 4 | TTCGA$ |
| 1 | TGATTCGA$ |
| 7 | GA$ |
| 2 | GATTCGA$ |
| 6 | CGA$ |
なお、Suffix は元の文字列と開始位置さえわかれば特定できるので、表の開始位置の列だけ覚えておけば Suffix Array を表すことができる。
Doubling
Suffix Array の構築手法の１つ、Doublingについて解説する。
- 補助的なデータ構造として、「逆接尾辞配列(inverse suffix array, ISA)」というものを利用する。これは、\(\mathrm{SA}[k] = v \leftrightarrow \mathrm{ISA}[v] = k\) と記録されているも。
- 最初の \(h\) 文字だけでソートしたsuffixの順序を \(h\)-順序( \(h\)-ordering)と呼ぶ。
- 前半の \(h\) 文字のみで判断した \(\mathrm{SA}_h\), \(\mathrm{ISA}_h\) を利用する。
- \(h\) 文字目までの順番が確定している時、その順番を利用して \(h+h=2h\) 文字目までの順番も分かる、ということを利用する。
例
「TAAAAGCTAAC$」という配列のSuffix Arrayを求める。
| h | |
|---|---|
| 1 |  |
| 2 |  |
| 3 |  |
このように、１つ前の結果を利用することで効率的にSuffix Arrayを構築できる。
この時、最悪計算量は \(\mathrm{O}(n\log n)\)
実装例
ここに記載しています。