配列解析アルゴリズム特論 渋谷

接尾辞木について渋谷
東京大学医科学研究所ヒトゲノム解析センター（兼）情報理工学系研究科コンピュータ科学専攻
http://www.hgc.jp/~tshibuya

文字列索引
配列解析アルゴリズム特論 渋谷文字列探索を効率化するためのデータ構造のこと
テキスト文字列に対して前処理を行うことによって得る
厳密マッチング
接尾辞木、接尾辞配列、FM-index

非厳密マッチング
FASTA、BLAST （いずれもヒューリスティック）

接尾辞木とは
配列解析アルゴリズム特論 渋谷文字列 S のすべての接尾辞を表した trie
枝のラベル ⇔ S の部分文字列
ルートから葉までのラベルを連結したもの ⇔ S の接尾辞
Suffix tree of 'mississippi$'
All thesuffixes

mississippi$
ississippi$
ssissippi$
sissippi$
issippi$ssippi$sippi$
ippi$
ppi$
pi$
i$

s

i

ppi$

ppi$

$
ssi

p
i$

pi$

issi
ppi$

ssippi$

i

si

ppi$

mississippi$
ssippi$ssippi$$について
配列解析アルゴリズム特論 渋谷テキスト・パタンに含まれない文字
接尾辞木に限らず、様々な場面で有効に用いられる
多くの場合、終端記号として用いられる＄があれば、すべての接尾辞と葉ノードが１：１に対応する

Suffix tree of 'mississippi$'
All thesuffixes

mississippi$
ississippi$
ssissippi$
sissippi$
issippi$ssippi$sippi$
ippi$
ppi$
pi$
i$

s

i

ppi$

ppi$

$
ssi

p
i$

pi$

issi
ppi$

ssippi$

i

si

ppi$

mississippi$
ssippi$ssippi$接尾辞木のサイズ
配列解析アルゴリズム特論 渋谷 もし、ナイーブにラベルを格納したとすると？
 O(n2)のサイズが必要になる

 うまくやれば全体でO(n)のサイズで表現できる
 枝のラベルは文字列のインデックスで表現可能
１つのノードあたりコンスタントメモリー（たった２つの整数）
テキスト自体は別に覚えておく

 葉の数（＝接尾辞の数＝文字列の長さ）は n 全体のノードの数（＝枝数＋１）は 2n−1 以下
内部ノードの次数は２以上なので
テキスト
の位置で
表現

[3..7]ATACCGTCTTAGC[3..7]

Text

Suffix Tree

ノードの表現について
配列解析アルゴリズム特論 渋谷 様々なノードとその子ノードの表現nil リスト （もっとも一般的） 各ノードが子供へのポインタと次の兄弟へのポインタを持つ
 ソートする場合としない場合がある
 最悪の場合、子供を辿る際に子供をすべてチェックする必要がある

 配列
 アルファベットサイズが小さい場合にはＯＫ ソートした配列を持てば二分探索が可能（ただし更新は非効率的） ハッシュ
 文字数が多い場合によくする実装
 木をすべてtraverseするのに不利f() となりのノードを見つけるのに余計な時間がかかる（ことが多い） 二分木（様々なバリエーションが存在する）
 ラベルを辿る際にアルファベットサイズ s に関する計算量を log sのオーダーに抑えることができる 子供を追加するといった、更新も同じ計算量で可能 ラベルと関係なく子供を辿る場合は、O(1)F
BK 実際の実装ではなかなか使われない
 実装に必要なメモリ量が大きすぎる

A

D

H

接尾辞木の特技
配列解析アルゴリズム特論 渋谷 構築：なんと線形時間！！
 検索：もともとあるテキストに対して、あるパタンがあるかどうか、あればどこにあるかを探す パタンの長さに対して線形時間 （アルファベットサイズ：固定）
 木を上から辿る

 頻出部分文字列検索：あるテキスト中で頻出する部分文字列を探す
 線形時間 単にノードに対応する文字列を列挙するだけ

 共通部分文字列探索：複数のテキスト中で共通に出現する部分文字列を探す これも線形時間
 異なる終端文字を加えてから連結し、接尾辞木を作成する
text 1text 2$1

text 3$2$3

他にもたくさんの応用がある。
Gusfieldの本に詳しい

接尾辞木の作成アルゴリズムの歴史
配列解析アルゴリズム特論 渋谷歴史Weiner '73
O(n s) （s: アルファベットサイズ）

McCreight '76
O(n log s)[Gusfield '97]に詳しい

Ukkonen '95
O(n log s)
McCreightの簡単化・On-line化

Farach '97
O(n) for integer alphabet [1..n]接尾辞配列から作成
O(n) for integer alphabet [1..n]Kasai et al. '00 + Kärkkäinen & Sanders '03, etc.
 逆に接尾辞木から接尾辞配列は、自明に線形時間で作成可能。

ナイーブに作ると？
配列解析アルゴリズム特論 渋谷ひとつの葉を挿入するのにO(n log s)時間
もっとナイーブに作るとO(n·s)時間
n: 文字列の長さ s: アルファベットサイズ

全体でO(n2 log s) 時間 → 遅すぎる！
Suffix tree of 'mississippi$'
All thesuffixes

mississippi$
ississippi$
ssissippi$
sissippi$
issippi$ssippi$sippi$
ippi$
ppi$
pi$
i$

s

i

ppi$

ppi$

$
ssi

p
i$

pi$

issi
ppi$

ssippi$

i

si

ppi$

mississippi$
ssippi$ssippi$Ukkonen’s Algorithm (1)[Ukkonen ’95]
配列解析アルゴリズム特論 渋谷S[1..n]の接尾辞木の作成方法
 左から順番に作っていく Phase i S[1..i]にノードを（必要なら）挿入することでS[1..i]の接尾辞木を作る O ( n log |  |) time (n : string length,  : alphabet)
Ukkonen Algorithm for ‘mississippi$’
Phase

1

2

3

4

5

6

Suffixes

m

mi
i

mis
is
s

miss
iss
ss
s

missi
issi
ssi
si
i

missis
issis
ssis
sis
is
s

....

Ti

: Added nodes

Ukkonen’s Algorithm (2)配列解析アルゴリズム特論 渋谷Implicit Suffix Tree
葉に関してはテキスト上の始めの位置のみを記憶
右に伸ばした時に、変更する必要をなくするため。

mississippiの接尾辞木を作成中

mississ
missis
issis
ssis
sis
is
s

T[1..]
ississT[0..]

T[2]smississT[4..]
iss

T[3..]siss

次はiを加えることになるが、ノードを追加する必要はない

Ukkonen's Algorithm (3)配列解析アルゴリズム特論 渋谷各phase で葉を追加する必要がある接尾辞は？
前のphaseで最後に 縦は同じ文字
作った葉
１番長い
接尾辞
２番目に長
い接尾辞
３番目に長
い接尾辞

このphaseで最後に作る葉計算不要（理由は次頁）

現在のphaseで加わる文字
すでに対応する葉ノードを作成済。
implicit suffix treeなので、ラベルの変更も必要もない。
相当する場所が存在するかチェックして、存在しない場
合は、対応する葉ノードを新規に作成する
この文字列に相当する場所
がすでに木に存在していたな
らば、ここより下はこのphase
では計算しないでよい。
次のphaseはこの行から下で計算を開始する。

Ukkonen's Algorithm (4)配列解析アルゴリズム特論 渋谷なぜ、下は計算しなくてよいのか？
現在のphaseで加わる文字

前のphaseで最後に作った葉このphaseで最後に作る葉（たとえば）こういったところですでに計算している！

この行に対応するノードがある、ということは、それ以下のノード
すべてと同じものをすでに計算していて、対応ノードはすべて作成済であることを表している！

Ukkonen's Algorithm (5)配列解析アルゴリズム特論 渋谷しかしながら、ノードを加える時に木をルートから辿って作成すると、線形時間にはならない！→ suffix links
現在のphaseで加わる文字

上から辿ればO(n2)になってしまうUkkonen's Algorithm (6)配列解析アルゴリズム特論 渋谷 Suffix Links
 ノード p から p より１だけ短い接尾辞 q へのポインタ Lq is a suffix of Lp
 |Lq| = |Lp|−1(Lp: label of p, Lq: label of q) 理論的に必ず存在する

 一つ短いsuffixの位置を知ることができる。
 他にも様々な応用がある（最大共通部分文字列の計算など）

Suffix tree of 'mississippi$'
All thesuffixes

mississippi$
ississippi$
ssissippi$
sissippi$
issippi$ssippi$sippi$
ippi$
ppi$
pi$
i$

s

i

p

i
pp$

issi

$

ssi

i$

ppi$

pi$

ppi$

ssippi$

i

si

ssi
ppi$
ssippi$mississippi$

ssippi$

ississippi$

ssissippi$

Ukkonen's Algorithm (7)配列解析アルゴリズム特論 渋谷 なぜsuffix linkが「必ず」存在するのか？
 あるノードが存在する ＝ そのノードのラベル（そこまでの枝のラベルの連結したもの）で始まり、その次の文字が異なる部分文字列が２組以上存在する、ということ
 当然、その接頭辞１文字を除いた部分文字列の組も存在するため、それに対応したノード、すなわちsuffix link先も存在する
Suffix tree of 'mississippi$'
All thesuffixes

mississippi$
ississippi$
ssissippi$
sissippi$
issippi$ssippi$sippi$
ippi$
ppi$
pi$
i$

s

i

p

i
pp$

issi

$

ssi

i$

ppi$

pi$

ppi$

ssippi$

i

si

ssi
ppi$
ssippi$mississippi$

ssippi$

ississippi$

ssissippi$

Ukkonen's Algorithm (8)配列解析アルゴリズム特論 渋谷 Suffix Linkの利用
 Suffix linkを辿れば、全体の比較回数はO(n)ですむ
 cf. Aho-Corasick Algorithm

 葉のsuffix linkは(作成時には）不要 但し応用アルゴリズムでは、作ると便利なことも葉を作るために作成する（葉の親となる）
内部ノード
現在のphaseで加わる文字葉

新しい葉
問題はココ！
（複数辿る可能性がある）
しかし、ここで葉を探しながら辿る量の総和は、この三角形の横幅（＝文字列長）
で抑えられる作りながら計算

Ukkonen's Algorithm (9)配列解析アルゴリズム特論 渋谷全体の計算時間O(n log s)sはアルファベットサイズ
アルファベットを平衡木でアクセスするようにした場合
ハッシュで表せば平均的にO(n)配列で持つ場合は初期化するだけでO(ns)必要
子供をリストで持つ場合もO(ns)McCreight Algorithm （概略のみ）
配列解析アルゴリズム特論 渋谷アルゴリズムとしてはUkkonenと殆ど同じ一つ目のsuffix から順に挿入していくのは同じ
Ukkonenと違って、suffixは末尾まで考えていた
したがってMcCreightでは、テキストの文字が1字1字来る度に接尾辞木をupdateすることはできないSuffix linkを活用することで計算時間はUkkonenと同じ
活用方法も理論解析もUkkonenのアルゴリズムとほぼ同様
mississippi$
ississippi$
ssissippi$
sissippi$
issippi$ssippi$sippi$
ippi$
ppi$
pi$
i$

s

i
ppi$

$
ssi

p
i$

ppi$

pi$

ppi$

ssippi$

i

si

ppi$

mississippi$
ssippi$ssippi$Weiner's Algorithm (1)
配列解析アルゴリズム特論 渋谷Ukkonen と逆方向に接尾辞木を作成する
O(n·s)のメモリー・計算時間が必要 (s: alphabet size)ナイーブにすればやはりO(n2)かかってしまう。

mississippi$
ississippi$
ssissippi$
sissippi$
issippi$ssippi$sippi$
ippi$
ppi$
pi$
i$

Phases
10

9

i$

i$

8
pi$

7
i$

p
i$

...
i

pi$

$

p
ppi$

i$

pi$

Weiner's Algorithm (2)配列解析アルゴリズム特論 渋谷 suffix linkの逆のリンク(prefix link)を作成すればよい
 各ノードで最大アルファベットサイズの数のリンクが必要
 各ノードにフラグindicator[x] を用意
 x はprefix linkに対応するアルファベット (すなわちアルファベットサイズ分必要)
 初期状態ではフラグは何も立っていない状態とする

新たに加える接尾辞の１文字目（prefix linkに対応するアルファベット)xαα③ この間にノードはない。
一文字目だけをチェックして枝を選択。
④ このノードv''を作成⑤ v'からv''へのprefix link を作成⑥ 新しい葉を作成

v''

x
x

② vの祖先の中で、xに対応するprefix linkを持っている一番下のノードを見つける① v の祖先の中でindicator[x]のフラグが立っている一番下のノードv'を探す（⑤で必要）
previous leaf v

v'

x
x

⑦ vとv'の間のノードのindicator[x] フラグを立てる

Weiner's Algorithm (3)配列解析アルゴリズム特論 渋谷 計算時間 O(n·s) （sはアルファベットサイズ） 解析はUkkonen と全く同じ

計算

辿る量が文字列長を超えることはない

Farach’s Suffix Tree Construction Algorithm[Farach '97]

配列解析アルゴリズム特論 渋谷 Integer alphabet {1,…,n} に対して線形時間
 現実的にはあまり速いアルゴリズムとはいえないインプリすること自体相当難しい しかし、これが後のsuffix array構築アルゴリズムの革命的発展の端緒となった！
 {1, ... , poly(n)}でも線形時間radix sortで {1, ..., n} の問題に持ち込めるため

 ３ステップからなる
 Step 1
半分のサイズの問題をとく（再帰的に計算）
 Steps 2 and 3
その問題から線形時間で本物を構築
 Computing time : f (n) = f (n/2) + O(n) → f (n) = O(n)証明：

f(n) < f(n/2)+c·n < f(n/4)+c·n+c·n/2 < f(const) + 2c·n

Radix Sort （復習）
配列解析アルゴリズム特論 渋谷 ラディックス（基数）・ソート
 下の位（あるいは文字）からソートして行く その桁の文字が同じものについては順番を変えないようにする バケツソートで O(n+s) (sはアルファベットサイズ)

 計算量 O((n+s)b)
ATGC
TATA
CTGC
GTTA
GGGC
GTCA
TGTG
GTGT
ATGA
GGGG
d=1

TATA
GTTA
GTCA
ATGA
ATGC
CTGC
GGGC
TGTG
GGGG
GTGT

d=2
順番は変えない(bは桁数)

GTCA
ATGA
ATGC
CTGC
GGGC
GGGG
GTGT
TATA
GTTA
TGTG

TATA
GGGC
GGGG
TGTG
GTCA
ATGA
ATGC
CTGC
GTGT
GTTA

ATGA
ATGC
CTGC
GGGC
GGGG
GTCA
GTGT
GTTA
TATA
TGTG

d=3

d=4

終了

Step 1
配列解析アルゴリズム特論 渋谷Odd Treeの作成
奇数番目の接尾辞のtrie基数ソートを行い、半分の長さの文字列を作成それに対して接尾辞木を作成

27452721...

2 3 2 1 ...
suffix tree2f(n/2) time1...

(f(n) : time for constructing suffix tree ofa string of size n)それを修正して奇数番目の接尾辞のtrieを作成（odd tree）
O(n) timeradix sort

321...
1...

odd tree321...

2
1...

7

21...

452721...

4527321...

Step 2
配列解析アルゴリズム特論 渋谷Even Treeの作成
偶数番目の接尾辞のtrie偶数番目のみの接尾辞配列を作成
奇数番目の接尾辞配列から基数ソート

偶数番目の接尾辞のtrieをそれから作成する
となり同士のLCP lengthを利用
 LCP: Longest Common Prefix これはOdd treeから計算する

O(n) time

odd tree of
3141592653

9
1
6
1
3

2653
3141592653
41592653
53
592653
Odd suffix array

Add a prefix to each odd suffix

radix sort141592653
1592653
3
653
92653

1
0
0
0
LCP length

even tree

Step 2 (cont.)
配列解析アルゴリズム特論 渋谷 となりのＬＣＰを求めるには？
 Odd tree 中の対応するLCAを求めることにより可能
これはO(n)の前処理でO(1)で可能！（後述）| lcp(l2i +1 , l2 j +1 ) | +1 if s2i = s2 j
| lcp(l2i , l2 j ) |= 0
if s2i  s2 jlowest common ancestor

一つ短いsuffix
Even Tree

Odd TreeStep 3
配列解析アルゴリズム特論 渋谷２つの木をマージするまずは枝の最初の文字だけ見てマージ
マージしすぎたものを戻す
マージした２つの文字列の本当のLCPを「うまく」計算して、マージした木と矛盾していれば、正しい状態に
修正する

33
31415

6414
427

515

merge
31
33
6414
415
427

515

O(n) time

unmerge
3
3

6414

1415
427

515

Step 3 (cont.)
配列解析アルゴリズム特論 渋谷 うまいlcpの計算法
子供にodd/even両方の葉を含むノードについてodd/evenに相当する子供をそれぞれ１つずつ選ぶ

| lcp(l2i +1 , l2 j ) | +1 if s2i = s2 j −1
| lcp(l2i , l2 j −1 ) |= 0
if s2i  s2 j −1

 擬似Suffix linkからなる木を作成◆ LCAが要◆ 正しい木ではsuffix

link と同じ◆ DFSでチェックしてい
く

s

i

p

i
pp$

issi

$
ssi

i$

ppi$

pi$

ppi$

ssippi$

i

si

ssi
ppi$
ssippi$mississippi$
ssippi$強力ツール： LCP
配列解析アルゴリズム特論 渋谷

ある接尾辞と別の接尾辞の最大の共通接頭辞(LCP=longest common prefix)長を求めることが、なんと線形時間の前処理をするだけで、O(1)でできる！
接尾辞木→LCA (lowest common ancestor)
Farachのアルゴリズムに限らず、極めて多くの組
み合わせパタンマッチングアルゴリズムに応用さ
れている
Text
されど月日は百代の過客にして行きかう人も云々?

やはり月日は百代の過客にして光陰矢のごとしとかなんとか?

LCA
配列解析アルゴリズム特論 渋谷Lowest Common Anscestor

RMQ
配列解析アルゴリズム特論 渋谷Range Maximum (Minimum) Query配列中のある領域の中で、最大（最小）の値を持つインデックスを探すji

31 14 15 92 65 35 89 79 32 38 46 26 43 38 27 95 02 88 41 97 16 93 99
Max

Min

LCA & RMQ by Bender & Farach (1)[Bender, Farach 2000]
配列解析アルゴリズム特論 渋谷

 LCA→RMQ
 Cartesian treeを作成すれば、RMQはLCAで解ける

 Cartesian tree
 数列から作成する （長さn の数列に対し、ノード数nの木を作成）
 各ノードは入力数列中の数に対応
 子ノードの値は親ノードの値以下
 数列中の左右の順番を木の中でも保存する

Cartesian
Tree

LCA

31 14 15 92 65 35 89 79 32 38 46 26 43 38 27 95 02 88 41 97 16 93

LCA & RMQ by Bender & Farach (2)配列解析アルゴリズム特論 渋谷Cartesian treeの作成方法
単純に左からgreedyに作成すれば線形時間で構築可能
木をトラバースする時間＝線形時間ですむため次の計算
枝の付け替え（O(1)）

次の枝がどこから出るかはいろいろ可能性はあるが、一度上に辿れば、下に戻ることはない！

31 14 15 92 65 35 89 79 32 38 46 26 43 38 27 95 02 88 41 97 16 93

LCA & RMQ by Bender & Farach (3)配列解析アルゴリズム特論 渋谷

±1RMQ→LCA
±1RMQとは値の変化が１のみである配列に対してRMQを求める問題

0
1

2

3

4

LCA & RMQ by Bender & Farach (4)配列解析アルゴリズム特論 渋谷O(n log n)-preprocessing for O(1) RMQ
0<k≤log2 n なる k すべてに対しサイズが 2k のすべてのウィンドウにおいて最大（小）値を管理する
これはO(n log n)で可能
前処理

0 1 2 3 1 2 3 ....

...

...
RMQ

...

0123212345434567654345678987654343210
max をとる
最大値を管理
サイズ 2kLCA & RMQ by Bender & Farach (5)配列解析アルゴリズム特論 渋谷 前処理時間O(n)の±1RMQ解法
 (log n)/2以下のサイズのブロックは n1/2 の種類しかない！
 先頭の値を引いたものを考える それぞれに対しナイーブなテーブルを作成してもo(n) 重複するものを作らないようにすれば、全体でO(n)となる。
この間のRMQを求めたい

0 + + - + - - +(log n)/2a)(log n)/2b)a) ブロック内RMQ→ 前処理はo(n)b) は2n /log n 個の数列に対するRMQ→ 前処理はO(n)先頭の値が変わっても、最大値の位置は不変

0 1
1 2
2...

[i..j]の間の最大値の位置を示すテーブルこれまでの復習： 接尾辞木とは配列解析アルゴリズム特論 渋谷 文字列 S のすべての接尾辞を表した trie
枝のラベル ⇔ S の部分文字列
ルートから葉までのラベルを連結したもの ⇔ S の接尾辞
線形サイズ・線形時間で構成可能
Suffix tree of 'mississippi$'
All thesuffixes

mississippi$
ississippi$
ssissippi$
sissippi$
issippi$ssippi$sippi$
ippi$
ppi$
pi$
i$

s

i

p

ssi

$

i$

pi$

si

i

ppi$
ppi$

issi

ppi$

ssippi$ppi$
ssippi$mississippi$
ssippi$接尾辞配列とは
配列解析アルゴリズム特論 渋谷接尾辞配列すべての接尾辞のインデックスを辞書順にソートした配列
 辞書と同様、二分探索で任意の接尾辞、あるいはその接頭辞である部分
文字列を探すことができる

接尾辞木よりも遥かにコンパクト
 接尾辞木は 14n byte
 接尾辞配列は 5n byte 整数・ポインタ等が32bit（4byte）、文字が8bit (１byte)で表現できる場合

すべての
接尾辞

0: mississippi$
1: ississippi$
2: ssissippi$
3: sissippi$
4: issippi$
5: ssippi$
6: sippi$
7: ippi$
8: ppi$9: pi$
10: i$

ソート

10: i$
7: ippi$
4: issippi$
1: ississippi$
0: mississippi$
9: pi$
8: ppi$6: sippi$
3: sissippi$
5: ssippi$
Suffix Array
2: ssissippi$

接尾辞配列と接尾辞木の関係
配列解析アルゴリズム特論 渋谷 子供がソートされた接尾辞木における葉を並べたものと同じ
 ただしそれぞれのノードの子供はアルファベット順にソートされているものとする
 したがって接尾辞配列は接尾辞木から自明に線形時間で作成可能
 実は逆も可能 （Kasai et al. 2001・後述)

 ＋αのデータ構造を用いるなどすれば、接尾辞木とほぼ同様の操作が可能となる場
合が多い 遅くなる場合もあるが、単純なデータ構造であるため、逆に速くなるアプリケーションも多い アルゴリズムを考えるときは接尾辞木で、実装は接尾辞配列で、というのがよくあるパタン

Suffix tree of 'mississippi$'
All thesuffixes

mississippi$
ississippi$
ssissippi$
sissippi$
issippi$ssippi$sippi$
ippi$
ppi$
pi$
i$

s

i
ssi

$

p
i$

pi$

si

i

ppi$
ppi$
ppi$

ssippi$ppi$
ssippi$mississippi$
ssippi$接尾辞配列を用いた検索 （１）
配列解析アルゴリズム特論 渋谷二分探索ソートされた数列を探索するのと異なり、長さ分調べる必要がある。
O(m log n) （n:テキストサイズ m:パタンサイズ）
平均的には O(m + log n)
テキスト、パタンがランダムである場合ソートされた接尾辞

パタン

接尾辞配列を用いた検索 （２）配列解析アルゴリズム特論 渋谷 パタンとのlongest common prefix length を用いた２分探索 探索順序は変わらないが、文字列比較を減らすことで、少し速くできる。
 ただし計算量は変わらない。

 追加のデータ構造を用いれば、最悪でも O(m+log n) や O(m) とすることも可能（後述） パタンを後ろから探索する方法などもある

L
真ん中
パタンと一致し
ている部分

ここの位置
から比較を
開始

R

Suffix Array例
配列解析アルゴリズム特論 渋谷“ipp”を検索③④②①“ippi”と③のＬＣＰ長は 1
10: i$
発見
7: ippi$
4: issippi$“ippi”と②のＬＣＰ長は 1
1: ississippi$
0: mississippi$
9: pi$
8: ppi$“ippi”と①のＬＣＰ長は 0
6: sippi$
3: sissippi$
5: ssippi$
2: ssissippi$“mississippi”に対する接尾辞配列②と③のチェックが終わった後は、チェックしないでも②と③の間のすべての接尾辞（ここでは④のみだが）は、その１文字目が‘i’であることがわかる！

接尾辞配列の構成アルゴリズム
配列解析アルゴリズム特論 渋谷 Naively from suffix trees
 常にO(n)だが、構築時にメモリが多く必要 （何のための接尾辞配列か？） アルゴリズムが複雑なため現実には遅い

 Ternary quick sortBentley & Sedgewick '97
一般的な辞書のソート用のアルゴリズム
ランダムな配列に対しては高速 (O(n log n))
繰り返しの多い塩基配列などでは遅く、O(n2)になるケースも多い Doubling algorithm
 Manber & Myers '92, Larsson and Sadakane '98.
 常にO(n log n) Copy-based (BWT-like) algorithm
 Itoh-Tanaka '99, Seward '00, Manzini-Ferragina '02, Schürmann and Stoye '05.
 省メモリ。最悪計算量はO(n2 log n)だが、実験には結構速い。

 Divide and merge algorithm(Farachのアルゴリズムのアイディアが源流)
 Kärkkäinen & Sanders '03, Ko & Aluru '03, Kim et al. '03, Hon et al. '03, Na '05,
Nong et al '09(←最速！）.
 常にO(n) Burkhardt & Kärkkäinen '03
 O(n log n)、作業メモリがo(n)数列のソートとの関連
配列解析アルゴリズム特論 渋谷 接尾辞配列は接尾辞のソート 数列のソートの問題の一般化ともいえる 同じ数字を含まない数列では、一般的なソートの問題と接尾辞配列を構成する問
題は同じ問題 したがって、一般的な数列に対する接尾辞配列は大小比較のみではO(n log n)より速く作ることはできない！
 O(n)を達成しているアルゴリズムは、integer alphabetを含め、アルファベットサイズ
が小さい、という事実を用いている
 一般的な数列ではalphabet sizeは（ほぼ）無限大

 数列のソートアルゴリズムを内部で利用することが多い どんなソートアルゴリズムを使っているか？
 クイックソートを使っているもの
 Bentley-Sedgewick, Larsson-Sadakane, etc.

 ラディックスソートを使っているもの
 Manber-Myers, Kärkkäinen-Sanders, Ko-Aluru, Larsson-Sadakane, etc.

 マージソートを使っているもの
 Kärkkäinen-Sanders, Ko-Aluru, etc.

大小比較による数列・接尾辞のソートの下限
配列解析アルゴリズム特論 渋谷 解の種類 （数列のソートでも接尾辞のソートでも同じ）
 n!

 大小比較
 Yes/Noの２種類の回答を得ることが可能

 大小比較に基づく、いかなる入力でも処理可能なアルゴリズムの最大ステップ数の下限
 最良の場合には、これよりも少ないステップ数で求められることはもちろんあり得る（e.g. ソート済配列に対するバブルソートは線形時間）𝑛𝑡 ≥ log 𝑛! = ෍ log 𝑘𝑛𝑘=1> න log 𝑥 𝑑𝑥
1

= Ω(𝑛 log 𝑛)

クイックソート
配列解析アルゴリズム特論 渋谷基本的な数列のソートアルゴリズム
最悪O(n2)、平均O(n log n)
1. 一つpivotを選ぶ

2. それより大きいものと小さい（あるいは同じ）ものに分ける

3. 大きいもの、小さいものに対して再帰的に同じことを行い、最終的にソートされたら終了する
3

2

3

1

3 2

3

iteration

Bentley & Sedgewick '97
配列解析アルゴリズム特論 渋谷 Ternary quick sort
 クイックソートを文字列用にチューニングしたもの
 インプリは最も簡単
 ランダムならO(n log n)だが、通常の文字列のソートの場合よりも遅いO(n2)になるケースも多い 2-wayでも計算量は変わらないが、インプリするとこちらの方が速い
 DNAなどでは、「NNNNN」とか「ATATATATA」などの繰り返しがあったりするだけ
でかなり危険 一般的な文章でも「わたし」の次には「は」が来ることが多い いずれもうまく等分割とならない原因となる

大小比較以外も使うことができればもっと計算量が下がる可能性がある
配列解析アルゴリズム特論 渋谷バケツソート最大値 c の n 個の非負整数のソートはO(c+n)で可能
数字を用意した箱に入れるだけ！

1543264135526

1

2

3

4

5

6

ラディックス・ソート
配列解析アルゴリズム特論 渋谷 ラディックス（基数）・ソート
 下の位（あるいは文字）からソートして行く その桁の文字が同じものについては順番を変えないようにする バケツソートで O(n+s) (sはアルファベットサイズ)

 計算量 O((n+s)b)
ATGC
TATA
CTGC
GTTA
GGGC
GTCA
TGTG
GTGT
ATGA
GGGG
d=1

TATA
GTTA
GTCA
ATGA
ATGC
CTGC
GGGC
TGTG
GGGG
GTGT

d=2
順番は変えない(bは桁数)

GTCA
ATGA
ATGC
CTGC
GGGC
GGGG
GTGT
TATA
GTTA
TGTG

TATA
GGGC
GGGG
TGTG
GTCA
ATGA
ATGC
CTGC
GTGT
GTTA

ATGA
ATGC
CTGC
GGGC
GGGG
GTCA
GTGT
GTTA
TATA
TGTG

d=3

d=4

終了

Manber & Myers '92 (1)
配列解析アルゴリズム特論 渋谷 Doubling algorithm
 log n 回のラディックス・ソートで計算 ソートするたびに2文字を1文字（ソートされた順番）に置き換える それぞれの段階は線形時間で可能！ -> O(n log n)
A

T

A

C G

T

A A

C G

T

A A

C

T

G

1文字をソート

2文字をソート
4文字をソート

8文字をソート

16文字をソートManber & Myers '92 (2)配列解析アルゴリズム特論 渋谷ラディックス・ソートの適用のしかた
最初の文字列（i=0）

3 0 4 1 5 9 2 3 5 2 3 1 4 5 2 3 1 2
となりあう2文字でソートした時のソート順での番号に置き換える
04 ► 012 ► 114 ► 215 ► 3
2$ ► 423 ► 530 ► 631 ► 735 ► 841 ► 945 ► a52 ► b59 ► c92 ► d

このソートは2桁の基数ソートで線
形時間で可能文字はinteger

6 0 9 3 c d 5 8 b 5 7 2 a b 5 7 1 4次はとなりあう文字ではなく２つ隣の文字とあわせて基数ソートを行う （i番目では 2i だけ隣とあわせる）
全部計算するか、アルファベットサイズと文字列長が等しくなったら終了

Larsson & Sadakane '98
配列解析アルゴリズム特論 渋谷Manber & Myersの問題点
反復の最後の方では、ほとんど順番は不変
それほど長い一致が存在するわけではないLarsson & Sadakane Algorithm
Ternary quick sortを用いてダブリングを行う1文字目が同じであるグループの中で、2文字目をTernary sort
 このような（文字列ではない）文字に対するTernary sortは Ternary
split quick sort あるいは Bently-McIlroyアルゴリズムとよばれる

ソートが終了した場所はスキップ
 これができるため、M&Mより相当速い

一見 O(n (log n)2) っぽいが、実は O(n log n) すなわちM&Mと同じ

Seward "Copy" Algorithm '00 （概略）
配列解析アルゴリズム特論 渋谷 ＳＡ中に似た並びがあることを利用！
 平均LCP長が短い場合は結構速い
 必要メモリ量が小さい
一つ前の
文字がAの
ものに関し
て順番にコ
ピー

A

C

A
C
G
T
A
C
G
T
A

G

C
G
T
A
C

T

G
T

1. まずは２文字だけでソート
2. 一番少ない文字を探す（Cだとする）3. まずはCで始まるsuffix
をすべてソートする。ただし、CCで始まるsuffixのソートはCA,CG,CTの結果を用いれば計算できる
4. ＊Cで始まるものに計算結果をコピーする
5. 次に少ないものを選ん
で、繰り返す（但し、もう計算できているものは計算しない）

Itoh-Tanaka Algorithm '99
配列解析アルゴリズム特論 渋谷 同様のCopy系アルゴリズム
 後のO(n)のKo-Aluru AlgorithmやInduced Sortingのアイディアの種となったアルゴリズム

 アルゴリズム suffix を2つにわける type 1：１文字目>２文字目 （BA....など）
 type 2：１文字目≤２文字目 （AA... やAB...など）

 Type 1を普通にソート（Ternary quick sort) その結果を用いて全体をソート

A≤
B >
B ≤
C >
C ≤
...

Copy!

復習：Merge Sort
配列解析アルゴリズム特論 渋谷 ２つのソート済配列の併合をするには？
 ２つの配列を端から順番に見て小さい方を出力
 数字の比較はO(1)でできるので全体で線形時間
ここが重要接尾辞は数字ではないので、接尾辞配列のマージは極めて難しい！

 数列のソートの場合には、マージを再帰的に適用することで（最悪でも）O(n log n)で全体をソートできる
14<19
sorted array 1

5 14 15 26 31 42 46

sorted array 2

1

merged array

4 12 13 19 22 25

1

4

5 12 13 14

Kärkkäinen & Sanders '03 (1)
配列解析アルゴリズム特論 渋谷 Farachの接尾辞木のアルゴリズムを洗練させたアルゴリズム
 接尾辞を３種類に分ける
 それぞれ3i, 3i+1, 3i+2 番目から始まる接尾辞集合をそれぞれP, Q, Rとする
 集合P+Qに含まれる接尾辞のみからなる接尾辞配列を作成する
 f(2n/3) 時間で再帰的に計算することが可能 f(n) : 全体の計算時間

 その接尾辞配列を用いて接尾辞集合Rに含まれる接尾辞のみからなる接尾辞配列を作成する
 O(n) 時間

 ２つの配列をマージする（逆接尾辞配列をうまく用いる）
 O(n) 時間

A

T

A

C G

T

A A

C G

T

A A

C

T

G
P
Q
R

Kärkkäinen & Sanders '03 (2)配列解析アルゴリズム特論 渋谷 接尾辞集合P＋Qに対する接尾辞配列の作り方
 P+Qに含まれる各接尾辞の先頭3文字の組をまずソート
基数ソートで線形時間

 ソート順の番号に３文字の組を変更したP,Qに対応する文字列
それぞれ作る２つの文字列を連結し（間に終端記号をはさむ）、それに対して接尾辞配列を計算する（このアルゴリズム全体を再帰的に適用）
結果を用いてP＋Qに対する接尾辞配列を作成（自明）

8
3
A

6
4

T

A

C G

2

1

0
T

A A

8
C

T

A

7
4

C

C G

5
T

G
P
Q

340845$86217に対する接尾辞配列を作成する

Kärkkäinen & Sanders '03 (3)配列解析アルゴリズム特論 渋谷部分接尾辞集合Rに対する接尾辞配列の作り方
Pに対する接尾辞配列から基数ソート一回で作ることができる！（線形時間）
PはP+Qの一部なので、先に作成したP+Qに対する接尾辞配列の中からPに対応するindexのみ取り出せばPに対する接尾辞配列が自明に作成可能（線形時間）

A

T

A

C G

T

A A

C G

T

A A

C

T

G
P
R

Kärkkäinen & Sanders '03 (4)配列解析アルゴリズム特論 渋谷 逆接尾辞配列
 SA−1[i] = j ↔ SA[j] = i 様々な他のアルゴリズムでも使用されるデータ構造
 線形時間で作成可能
0: mississippi$
1: ississippi$
2: ssissippi$
3: sissippi$
4: issippi$
5: ssippi$
6: sippi$
7: ippi$
8: ppi$9: pi$
10: i$
Suffixes of theText

ソート

10: i$
7: ippi$
4: issippi$
1: ississippi$
0: mississippi$
9: pi$
8: ppi$6: sippi$
3: sissippi$
5: ssippi$
2: ssissippi$
SA

逆

4
3
10
8
2
9
7
1
6
5
0
SA−1

Kärkkäinen & Sanders '03 (5)配列解析アルゴリズム特論 渋谷２つのマージをするには？
接尾辞同士の比較が O(1) でできれば、線形時間のマージができる（マージソートと同じ）
逆接尾辞配列を用いる
逆接尾辞配列を用いれば、P+Qに入っている接尾辞同士がO(1)で比較できる
 それに加えてその直前1文字または2文字を比較すれば、Ｐ，Ｒ間あ
るいはＰ，Ｑ間の比較ができる
A

T

A

C G

T

A A

C G

T

A A

C

T

G

P
Q

q

r
R

この二つを利用して比較Kärkkäinen & Sanders '03 (6)配列解析アルゴリズム特論 渋谷計算時間
f(n) = f(2n/3) + O(n)
これは O(n)一般的に f(n)=c1·f(c2·n)+O(n) (0<c2<1, 0<c=c1c2)の時、
0<c<1 ならば f(n) = O(n)c=1 ならば f(n) = O(n log n)

c>1 ならば 𝑓 𝑛 = 𝑂(𝑛−log𝑐2 𝑐1 )𝑓(𝑛) < 𝑐1 · 𝑓(𝑐2 · 𝑛) + 𝑎 · 𝑛 < 𝑐12 · 𝑓(𝑐22𝑛) + 𝑎(1 + 𝑐)𝑛 <log 𝑛··· < 𝑐1
· 𝑓 const + 𝑎 1 + 𝑐 + 𝑐2 +··· +𝑐 log 𝑛 𝑛O(n)0<c<1 ならば f(n) = O(n)原論文： Kärkkäinen, J., and Sanders, P. (2003) "Simple Linear Work Suffix Array
Construction", Proc. ICALP, LNCS 2719, pp. 943-955.

Burkhardt & Kärkkäinen '03 (1)
配列解析アルゴリズム特論 渋谷 KSの（理論的）省メモリ化
 o(n) の追加空間計算量で O(n log n) 時間としたもの

 Difference Coverというものを使う
 [0..n−1] に対し O(n1/2) の大きさのカバーを O(n1/2) 時間で求めることができる (より厳密には[Colbourn&Ling, '00])[0..99] のdifference coverの例
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50, 60, 70, 80, 90（これが簡単だがもう少しだけ賢いカバーも存在する）

0～99 を (di −dj) mod 100 で表現できる

cf. 素数ものさし577円（消費税込で623円）
＠京大生協

Burkhardt & Kärkkäinen '03 (2)配列解析アルゴリズム特論 渋谷より大きな範囲でK&Sと同様の計算を行う
②

a

b

カバー
①

に対する接尾辞配列を作成する②

に対する接尾辞配列をradix sortで作成する③

それらをマージする
たとえば、aの比較は、先頭５文字の比較＋bの比較で行えば
O(カバーのサイズ)で計算可能

Burkhardt & Kärkkäinen '03 (3)配列解析アルゴリズム特論 渋谷Difference cover に入っている剰余に対応する接尾辞だけからなる接尾辞配列を作成
入っていないものに関してはそれぞれradix sortで作成可能radix sortの回数はcoverの大きさに比例ウィンドウサイズがkならば、
この時カバーのサイズは c·k1/2
k回の比較演算で、どの違う２つの剰余に対応する接尾辞の辞書順比較が可能すなわち f(n) = f(c·n/k1/2) + O(kn)k=log n とすると f(n) = O(n log n)
K＆Sは k=3 としたアルゴリズムに相当
{0,1}は{0,1,2}のカバー

Ko and Aluru '03 (1)
配列解析アルゴリズム特論 渋谷 K&Sと同様のDivide and Merge 系アルゴリズム
 となりの接尾辞との辞書順の大小で接尾辞を「＞」と「＜」の２つのタイプに分割し、それらのうち数の少ない方に対して接尾辞配列を作成
 Itoh-Tanaka algorithmのアイディアにも類似 「うまく」ラディックスソートでランキングすることで小さい問題に変換

 その結果を利用して、計算していない接尾辞も同様の「うまい」ラディックス
ソートで計算 マージも容易 同じ文字で始まる「>」タイプの接尾辞は「<」タイプの接尾辞より必ず辞書順で小さ
い ＝ そこから先はO(1)で比較可能
m

i

s

s

i

s

s

i

p

p

i

$

< が少ない

>

<

>
2

>

<

>

>

<

>

2

再帰的な呼び出し

>
1

> *
3

①タイプの決定：辞書順でとなり同士を比較する （O(n)）② ランクに書き換え：「うまい」ラディックスソートを行ってランクに書
き換え （O(n)）

Ko and Aluru '03 (2)配列解析アルゴリズム特論 渋谷「<」タイプと「>」タイプの線形時間決定法
後ろから見ていくだけ一つ後ろの接尾辞と先頭１文字だけチェックし、先頭文字が異なる場
合 その大小で「＞」タイプか「＜」タイプかがO(1)でわかる

先頭文字が同じ場合
 一つ後ろの接尾辞と同じタイプなので、やはりそれ以上チェックする必要はない！
１文字目が同じなので、必ず同じタイプ

m i s s i s s i p p i $> < > > < > > < > > >*

Ko and Aluru '03 (3)配列解析アルゴリズム特論 渋谷「うまい」 radix sort （このルーチンを２箇所で使う）”<”文字列のソート

長さでソート：
バケツソートでO(n)最後の文字は "<" タイプなので、そこまで同じ文字列はソート列の後ろに来ることになる- 例えば "isp" > "ispi"- ">"文字列のソートでは逆

2
1
2
3

radix sort

②それから「かしこい」ラディックスソート

この幅がwならばO(w)で一文字分のソートが可能＝全体で O(N) でソートが可能①まず「かしこく」ランキング

テーブル中の全文字の順位（ランク）を決定する
ことが全体で O(n+N) のバケツソートで可能
Step 1: この表に含まれる全文字をソート
Step 2: そのランク結果を（縦の）各列に分配
さらに分配時に、その列でのランクに変換！

N （表のサイズ（表中の文字列の長さの総和）） ≤ 1.5×n (元の文字列の長さ)
ここのインプリはかなり速度を左右することに注意

Ko and Aluru '03 (4)配列解析アルゴリズム特論 渋谷マージ時のO(1)比較＜と＞の比較は１文字目のみでＯＫ！

m i s s i s s i p p i $> < > > < > > < > > >*①②①と②は、どちらも ‘i’ で始まる接尾辞だが、異なるタイプなので、どちらの接尾辞が辞書順で速いかは２文字目以降を見ずとも決定可能！

Induced Sorting (1)[Nong-Zhang-Chan '09]
配列解析アルゴリズム特論 渋谷

Ko-Aluru
Kärkkäinen-Sandersと比べて高速 KSと比べて部分問題サイズが小さいことによるInduced Sorting [Nong-Zhang-Chan ’09]
接尾辞配列アルゴリズムの決定版
Ko-Aluru のアイディアの改良
 文字列の分割方法をさらに洗練させ、再帰的に解く「小さい部分問題」をより小さくしたことにより、再帰計算の時間が大幅に減少した

（論文によれば）ＫＡより約1.5倍高速。メモリ量も2/3程度。
LMS (Left Most <)
>

<

<

<

>

>

>

<

<

>

> *

Induced Sorting (2)配列解析アルゴリズム特論 渋谷 Ko-Aluruと同様 全接尾辞を「<」 と「 >」の２つのタイプに分ける （線形時間）
 さらに連続する「<」の中で一番左のもの「<*」（ＬＭＳ）を考える。
 Induced sorting ではこの 「<*」タイプのみをまずソートする（再帰） ＬＭＳの数は全体の半分(正確には+0.5)以下
 「＜」と「＞」が交互に来る場合が一番多くなるが、その時の数
 実際にはもっと小さくなる この部分問題サイズが他のアルゴリズムに比べてかなり小さいことが、全体のアルゴリズ
ム性能の高い理由となっている

 「>」タイプのソートは「<*」から「うまい」radix sortで可能
 全「<」タイプのソートは「>」タイプから「うまい」radix sortで可能
 ここが２段階となっている、というのがInduced sortingの新しいアイディア！

 それらのマージもKo-Aluruと同様に各比較は一文字目のみで可能（すなわちO(1)で可能！）LMS (Left Most <)> <* <<>>> <* <>> *様々なアルゴリズムの計算機実験による実性能比較
配列解析アルゴリズム特論 渋谷

Itoh-Tanaka '99
Kurz '99（STとしては省メモリ）

Kärkkäinen-Sanders '03

Burkhardt-Kärkkäinen '03
Seward '00
Larsson-Sadakane '98

Manzini-Ferragina '04(Seward '00の改良）

Ko-Aluru '03
Schürmann and Stoye '05(Copy系）

Kim-Jo-Park '04(Divide and merge系）

Baron-Bresler '05(Copy系)

Maniscalco-Puglisi '06a/b(Copy 系）

Induced sorting
はこのあたりで、
最速、最小メモリ付近、でかつ理論的にもO(n)Fig. 8 from Simon J. Puglisi, W. F. Smyth & Andrew Turpin, "A taxonomy ofsuffix array construction algorithms", ACM Computing Surveys, 39-2 (2007).

接尾辞配列の最重要付加データ： 高さ配列(Height Array)
配列解析アルゴリズム特論 渋谷 Suffix Arrayにおいて、隣同士の接尾辞のLCP (longest common prefix)
lengthの配列
 ississippiとissippiのLCPは４ 接尾辞配列から線形時間で計算可能 [Kasai et al. 2001]
 様々な応用
 RMQと組み合わせれば任意の接尾辞間でＬＣＰが求められる
 検索は O(m+log n) にできる 接尾辞木を線形時間で作成できる
10: i$
1
7: ippi$
1
4: issippi$
4
1: ississippi$
00: mississippi$
0
高さ配列
Suffix Array 9: pi$
1
8: ppi$0
6: sippi$
2
3: sissippi$
1
5: ssippi$
3
2: ssissippi$

高さ配列の作成法
配列解析アルゴリズム特論 渋谷 線形時間アルゴリズムが存在 （しかも、アルファベットサイズに関係ない！） 元の文字列の位置の順番で高さ配列を作成するだけ！
 逆接尾辞配列を用いる

 ナイーブに作成するとO(n2)必要hi
Ti

一つ前の接尾辞に対応する高さ配列の値
より１小さい位置から調べる↓
どう頑張っても2n以上チェックすることはな
い！

Ti+1

Suffix ArrayThi

同じ部分文字列が必ず他にも存在する（辞書順にも注意）

Ti
Ti+1接尾辞配列→接尾辞木
配列解析アルゴリズム特論 渋谷Height Array さえあれば、O(n) で接尾辞木を構成
可能
左から順に作っていけばよいだけ
RMQの時のCartesian Treeの作成方法と似たアルゴリズム

7

12

12
12

7
12

12

4

16
16
12

12

16

7
下からチェック
していけばよい1216

ＬＣＰの計算
配列解析アルゴリズム特論 渋谷

LCP = Height Array + RMQHeight Array の該当する範囲内で最も最小値を求めるだけでよい

Suffix Array

応用１： 接尾辞木の最も基本的な応用： Exact matching
配列解析アルゴリズム特論 渋谷 作成して上から辿るだけ（接尾辞木） 二分探索、逆方向探索等で探索（接尾辞配列）

Suffix tree of 'mississippi$'
All thesuffixes

mississippi$
ississippi$
ssissippi$
sissippi$
issippi$ssippi$sippi$
ippi$
ppi$
pi$
i$

s

i

ppi$

ppi$

$
ssi

p

i$

pi$

issi
ppi$

ssippi$

i

si

ppi$

mississippi$
ssippi$ssippi$高さ配列を用いた検索
配列解析アルゴリズム特論 渋谷RMQと組み合わせれば、ＬＣＰの長さがO(1)でわかるので、O(m+log n) で検索可能但し効率はよいとは言えない（実際には、最初に紹介した、「賢い検索」でも十分）
ＲとＬＣＰの長さが十分ある場
合には、この位置から比較を開始する
十分でなければ、
さらに二分探索を続行

L真ん中

パタンと一致している部分

R

Suffix ArrayLCP Arrayによる検索[Manber and Myers '92]
配列解析アルゴリズム特論 渋谷 O(m + log n) を直接可能にするデータ
 二分探索の枝分けは固定なので、必要なＬＣＰ長はO(n)個 作成時間はO(n) （高さ配列から計算）
 MMのオリジナルの論文では O(n log n) 当時は高さ配列を O(n) で作成する方法が知られていなかった

LCP配列の計算順
覚えていないといけないＬＣＰは高々2n個二分
探索

最初に調べるpivot

Suffix Array

逆方向検索 （→ FM-Indexにつながっていく）
配列解析アルゴリズム特論 渋谷 なんと検索は逆方向にもできる！
 Weiner Algorithmの逆suffix linkを辿ることに相当する
 cf. ＢＷ変換（→圧縮アルゴリズムの紹介の中で紹介予定）
１文字前に着目＝ＢＷ変換

文字列 Aα

Aで始まる接尾辞「Aがいくつあるか？」（を計算できるデータ
構造を別に持っておく必要がある）

Cで始まる接尾辞

文字列 αGで始まる接尾辞

Tで始まる接尾辞
Suffix Array

応用２： Set Matching Problem
配列解析アルゴリズム特論 渋谷 Aho-Corasick algorithm （復習） Knuth-Morris-Pratt のマルチパタン化 O(n+m+k) (n: テキストサイズ、m: パタンサイズの和、k: 出現数）

 接尾辞木を用いたSet matching 接尾辞木では普通に検索するだけでもO(n+m+k)が実現可能 テキストとパタンのどちらを前処理するか、の違い
 どちらが変化するのかによってＡＣかＳＴのどちらを使うかを決める パタンセットのサイズ＞テキストサイズならばＳＴの方が省メモリ

 Matching Statistics
 これもパタン側の接尾辞木を用いる
 これでもO(n+m+k)が可能
 他の応用も多い

T
C
T
A

 Boyer-Mooreをマルチプル・パタン化 パタン側の接尾辞木を用いる

Failure Link

T

C

C
T

G

T

T

G

Aho-Corasick Automaton

Matching Statistics (1)配列解析アルゴリズム特論 渋谷Matching Statistics とはテキスト文字列のすべての位置に関して、その位置から始まる最長のパタン文字列との共通の部分文字列長を計算したもの
パタン文字列に対する接尾辞木を用いれば線形時間で可能
位置 i から始まるPatternにも存在する最長の部分文字列
Text

Pattern
接尾辞木
Pattern側の位置はどこでもよいMatching Statistics (2)配列解析アルゴリズム特論 渋谷パタン側の接尾辞木を用いる
Suffix Linkを用いる
text
まずはナイーブに計算

suffix linkαSuffixLink

ここの葉を見ればパタンのどこにあるかもわかる。

α

この部分については、各辺のラベルの最初の１文字のみのチェックでOKα

次はsuffix linkを辿り、その下をチェック

パタンに対する接尾辞木Matching Statistics (3)配列解析アルゴリズム特論 渋谷計算時間は O(n)
辿るノード数が最大でも n であるため
UkkonenのアルゴリズムがO(n)である理由と同じ

Suffix ArrayでMatching Statisticsはできるか？
配列解析アルゴリズム特論 渋谷プサイΨ配列 (接尾辞配列上のSuffix Link)を用いればある程度可能 逆接尾辞配列から線形時間で作成可能

Ψ配列は接尾辞配列を圧縮するのにも用いられることがある

 二分探索は必要→ O(n log n)そのオーバーヘッドをなくすには、さらなる付加データ構造が必要
Index / All suffixes
0: mississippi$
1: ississippi$
2: ssissippi$
3: sissippi$
4: issippi$
5: ssippi$
6: sippi$
7: ippi$
8: ppi$9: pi$
10: i$
11: $ソート

Index / Suffix array / suffixesΨ

0:11: $
1:10: i$2: 7: ippi$
3: 4: issippi$
4: 1: ississippi$
5: 0: mississippi$
6: 9: pi$
7: 8: ppi$
8: 6: sippi$
9: 3: sissippi$
10:5: ssippi$
11:2: ssissippi$

0
7
10
11
4
1
6
2
3
8
9

たとえばssi (SA[10..11])のsuffix link先のsiはSA[8..9]sissi

Matching Statisticsの応用１：プライマー設計 （１）
配列解析アルゴリズム特論 渋谷 プライマー あるＤＮＡ試料に対して、ある短い配列が存在するかどうかを実験的に検査する際の、その短いＤＮＡ配列のこと

 プライマー決定問題
 入力
 配列 A と配列集合 S
 Aを他(S)の配列と実験的に区別できる部分配列を求めたい

 出力
 配列 A のすべての位置iについて、その位置から始まる部分文字列で S に存在しない一番短い文字列 （＝ AにはマッチするがSの配列にはマッチしない）

 意味
 その場所から始まる断片（あるいは遺伝子）が資料の中に含まれるかどうかを調べたい アルゴリズム Matching statisticsで求めた値 +1
プライマー

Matching Statisticsの応用１：プライマー設計 （２）
配列解析アルゴリズム特論 渋谷 問題を少し難しくして、次の問題を考える S のどの部分文字列ともedit distanceが k 以上である最小の部分文字列（ただし長さ l 以下）を、Aのすべての位置について求める
この長さが l 以下のものは確実に使える！
（ただし、それより短くても該当するものはあるかもしれないことに注意）Amatching statisticsk=3 ただし実際には、更に多くの条件がある◆ プライマーとして使えるためには、複雑な条件がある
 ＧＣ含量が５０％前後、回文禁止◆ プライマーは２つ一組で用いられることが多い 組み合わせを考える必要 ２つで囲んだ領域の長さが異なるものも判別可能 （電気泳動）

S

Matching Statisticsの応用２： Longest Common Substring
配列解析アルゴリズム特論 渋谷Matching Statistics で最大値をとるものを探す当然だが線形時間で見つけられる

最大
A

B

注：ただしMatching Statisticsを使わなくてもよい→次の話題（おまけ） Multi-pattern Boyer-Moore というのもある (1)
配列解析アルゴリズム特論 渋谷 Boyer-Moore （復習） 不一致ルール (bad character rule) チェックした文字がxであれば、パタンの中のxという文字のうち最後の位置までずらせる 接尾辞一致ルール (strong good suffix rule) 後ろk文字が一致した場合、パタン中のそれ以外の場所にそのk文字が存在する（いくつかある場合は最後のもの）時、そこを一致させるようにずらす KMPより速いことが多い これをマルチプル・パタン化することを考える
不一致

一致

不一致

異なる = strong一致Multi-pattern Boyer-Moore (2)配列解析アルゴリズム特論 渋谷不一致ルールの拡張 （簡単）
一番後ろにある不一致文字に一致する文字に着目
一番短いパタンの長さに注意

最終的な移動量

text

x

check

x
x

調べたいパタンの集合「一番短いパタンの長さ」も考慮する必要あり

Multi-pattern Boyer-Moore (3)配列解析アルゴリズム特論 渋谷接尾辞一致ルール （これを接尾辞木を使って計算）
逆順でのパタン集合のキーワード木を作成
後ろからパタンのマッチングを検査するため
この木は↓の一般化接尾辞木に含まれる

各ノードでの移動量を計算
逆順でのパタン集合の一般化接尾辞木を利用
 一般化接尾辞木(generalized suffix tree) ：複数の文字列に対する接尾辞木Multi-pattern Boyer-Moore (4)配列解析アルゴリズム特論 渋谷

接尾辞木において
各パタンに相当する枝とそれ以外を区別
相当する枝＝keyword treeそれぞれのノードまで探索した時の移動量を計算
探索はkeywordに相当する枝のみ
①

②

この部分を
重ねるよう
に移動

$

途中から生えている
non-keywordな＄枝があれば、それを考慮して移動（頭の部分が一致している場合）$

non-keyword

x
失敗

失敗

ノード以外の地点で失敗した場合

keywords

複数あれば、それらのうち最も移動の短いものを選ぶ
途中から生えているnon-keyword
な＄枝があればそれを考慮して移動（頭の部分が一致している場合）
失敗した場所にある文字xに相当するnon-keywordな分岐があればそれを考慮して次の位置に移動（通常の「強い」接尾辞一致
ルール）
non-keywords

ノードの次で失敗した場合

Multi-pattern Boyer-Moore (4)配列解析アルゴリズム特論 渋谷

①

x
¬x

text

$
ここで失敗

②

x
¬x
x

text

応用３： Multiple Common Substrings (1)配列解析アルゴリズム特論 渋谷 複数の文字列の間で共通に持つ文字列を求める問題
 Longest ～はその中から最長のものを選ぶ問題

 Generalized Suffix Treeを作る あるノードがいくつの文字列を葉として持つかを計算する
 ナイーブにやるとO(kn) (k: #patterns, n: sum of lengths)

4

3

$1

$2

text 1text 2
$1

2

$3

$4

$2
text3
$2

$3

Multiple Common Substrings (2)配列解析アルゴリズム特論 渋谷LCAを用いれば線形時間にできる！
Lowest Common Ancestor

葉

全種類の文字列の葉を含むminimal区間

尺取虫のように動かしていく

1 3 2 1 1
それぞれの文字列をいくつ含むかのベクトルを持っておく

Multiple Common Substrings (3)配列解析アルゴリズム特論 渋谷尺取り虫の例$1 $1 $3 $2 $2 $3 $2 $5 $4 $5 $3 $1 $2 $5 $1 $2 $1 $1 $1 $3 $2 $1 $4$1～$5が存在する5本の文字列の場合例

Multiple Common Substrings (4)配列解析アルゴリズム特論 渋谷 必要なLCAの計算
 実は単にTraverse するだけで線形時間で計算可能
 よって複雑な O(1) のLCA Query Algorithmは不要
Lowest Common Ancestorof A and C

Lowest Common Ancestorof A and B

葉
A

B

C

応用４： Maximal Repeats & Supermaximal Repeats
配列解析アルゴリズム特論 渋谷Maximal repeat
identicalな二つ以上の部分文字列の組で、左右どちらでも１文字増やしたらrepeat数が変わるもの

Supermaximal repeat
他のmaximal な部分文字列の部分文字列にはなっていない
ようなmaximal repeat

xyzabcyxdabcdfklmabcdywml
maximalsupermaximal

Maximal Repeats (1)配列解析アルゴリズム特論 渋谷 右側条件は「内部ノード」であること、でOK
 左側条件はMultiple Common Substringsと状況が似ている
 が実はもっと簡単（次ページ）ab

一文字前が違う文字である必要がある
どれが子孫にあるかのフラグ表（実際には持たない）

4
3

2
２つ以上にマーク

a

b

c

d

b

それぞれの葉に対応する各接尾辞の１文字前の文字（BW変換という）Maximal Repeats (2)配列解析アルゴリズム特論 渋谷1種類しかない区間を除外するだけでよい→線形時間！
LCA

maximal(これより上もmaximal）

LCA

maximalではない

葉
a

c

c

c

c

全部同じ

c

c

f

b

a

a

それぞれの葉に対応する各接尾辞の１文字前の文字（BW変換）

Supermaximal repeat
配列解析アルゴリズム特論 渋谷条件
右側条件： 子供はすべて葉である左側条件： 子供に対応する接尾辞の一文字前の文字がすべて異なる計算時間
アルファベットサイズが固定の場合線形時間
アルファベットサイズが固定でない場合
O(n log s) (s: アルファベットサイズ）
ハッシュを用いれば、計算時間の期待値は線形時間

直前の文字はすべて異なる必要

a

b

c

応用５： （ＬＣＡの応用２） k-Mismatch Problem
配列解析アルゴリズム特論 渋谷ギャップを考えないミスマッチを k 個許すマッチング
O(kn+m) (n: テキスト、 m: パタン)
一般化接尾辞木を作成し、LCPを用いる

text
pattern

ここから始まる共通な最長部分文字列の長さをLCPで一発で求めることができる

応用６： （ＬＣＡの応用３） 回文(palindrome)をみつけるには
配列解析アルゴリズム特論 渋谷逆順の文字列との一般化接尾辞木を作り、各位置に対応するＬＣＰの長さを求めればよい線形時間で可能DNA,RNAでの相補配列を考える場合でもやることは同じ
ATCCTGCAGGAT など （これも生物学的にpalindromeと呼ぶ）
間に最大 i 文字の隙間をいれるのを許す場合はO(i·n)

k-mismatchを許す場合はO(k·n)

やとうはかんせつぜいははいぜつせんかとつめよった
たっよめつとかんせつぜいははいぜつせんかはうとや

応用７： （ＬＣＡの応用４） Tandem Repeat (1)
配列解析アルゴリズム特論 渋谷 タンデムリピート 同じ（類似した）文字列の連続した繰り返し 様々な関連現象
類似遺伝子の生成
 視覚における赤と緑を知覚する遺伝子は互いに類似、連続して並んでいる。（進化の過程でコピーされて分化した）

個人の特定 基本単位の短いリピートの繰り返しの数が個人によって異なることがあり、しかも検出が簡単 → 犯罪捜査

がん細胞DNAの解析
 Copy number variation (CNV)DNA修飾・エンハンサー等への影響？
寿命を決定？
 テロメア （ＤＮＡ端にある、ＤＮＡを保護するため（？）の繰り返し）

その他さまざまな機能既知・未知の繰り返しが存在
DNA

Tandem Repeat (2)超ナイーブ法
配列解析アルゴリズム特論 渋谷 すべての位置i (1≤i≤n-1)とすべての長さ j (1≤i≤(n-i)/2)に対して
 位置iから始まる長さjの部分列を繰り返し単位とする繰り返し区間があるか？ あればその長さはどれくらいか？

を計算する
 計算時間は一つのi, jの組に対しO(n)の計算時間がかかるため、全体ではO(n3)となる
 ただし、入力がランダムな場合、一つのi, jの組に対する計算時間の期待値は 1+1/2+1/4+1/8+....→2 回の比較ですむので、O(1)である。よって平均計算量は O(n2)ATCGCGTA...

Tandem Repeat (3)分割統治法
配列解析アルゴリズム特論 渋谷

繰り返し区間を３つに分類する （ m = n / 2 ）

A)
B)
C)



A)に関しては、W[m]から左右に繰り返し列があるかをチェックする

ナイーブに計算して、O(n2)
入力がランダムの場合の平均は O(n)B)及びC)に関しては再帰的に計算する


区間がW[m]を含むもの
区間がW[1..m-1]に完全に含まれるもの
区間がW[m+1..n]に完全に含まれるもの

すでに見つかっている繰り返し区間よりも短くなると終了

全体の計算時間は O(n2)

この場合、O(n2 log n)とならないことに注意 ←漸化式から計算入力がランダムの場合の平均計算時間は O(n log n)

j

j
ここは固定

j はすべての長さを検査

Tandem Repeat (4)ＬＣＰを用いる
配列解析アルゴリズム特論 渋谷

 ＬＣＰを用いると、
 i 番目から繰り返し長 k のタンデムリピートがどれくらいの長さ続いているかをO(1) で計算することが可能！

 ２つのテクニックの組み合わせると、最悪でも O(n log n)
 分割統治に加えてＬＣＰ

 実は、
 線形時間で計算する方法もある (Kolpakov & Kucherov '99)

 ただし、実際の実応用（生物学）では、
 完全一致以外の類似繰り返しを考慮する必要がある
アルゴリズム

最悪計算量

平均計算量

1

超ナイーブ法

O(n3)

O(n2)

2

分割統治法

O(n2)

O(n log n)

3

ＬＣＰ＋超ナイーブ法

O(n2)

O(n2)

4

LCP+分割統治法

O(n log n)O(n log n)

5

LCP + factorization

O(n)

O(n)

類似アルゴリズム：２次元平面上の最近点ペアの探索 （1/2）
配列解析アルゴリズム特論 渋谷２次元平面上の最近点ペアの探索ナイーブに全２点間を計算するとO(n2)分割統治でO(n log n)
事前に x 軸に沿ってソートしておく
yx
片側のみをまず計算（再帰的に計算）
その後、間のものを計算（線形時間）

２次元平面上の最近点ペアの探索 （2/2）
配列解析アルゴリズム特論 渋谷両側の間の最近点ペア計算
左側の最近点ペア間距離よりも小さいもののみ計算する事前にy軸に沿ってソートしておく （ x軸のソートとは別に）長さ l 以下のものはこの８つの正方形に入る。
各正方形には高々１つしか点は存在しない。
（ユークリッド空間版鳩の巣原理）→線形時間サーチが可能

y

l
l
l/2
右側で左との境界から l 以上離れて
いないもの

l/2
x

2
𝑙
2

応用 8: (All-pairs) Suffix-Prefix Matching (1)
配列解析アルゴリズム特論 渋谷ある２つ（以上）の文字列がどれくらい前後でオー
バーラップしているかを知りたいDNAアセンブリなどで必要になる

仮想テキスト（未知）どれほど長く一致させることができるか？

(All-pairs) Suffix-Prefix Matching (2)配列解析アルゴリズム特論 渋谷 一般化接尾辞木を作成する
 O(n + #pairs_to_solve) で計算可能
 全対全の比較が一度に可能 現実にはエラーを考慮する必要がある$2$1
同じ文字列の$記号があれば深い方を選ぶ＝よりオーバーラップが大きい$2ある文字列全体に相当する葉（接尾辞ではなく）

は$記号のみからな
る枝で分かれている葉接尾辞配列・接尾辞木の拡張・一般化
配列解析アルゴリズム特論 渋谷 簡単な拡張(簡略化） STのDAG化 SAの間引き 接尾辞木は非常に強力なので、文字列以外のデータに対しても同様の探索法を作りたいことがある
 Circular Stringに対するST, SA
 文字の入れ替えを許すもの
 p-suffix tree
 s-suffix tree

 木構造に対するsuffix tree
 木構造に対するsuffix tree その２
BSuffix tree

 行列に対するsuffix tree
LSuffix tree

 空間上の点列に対するsuffix tree
Geometric suffix tree

拡張 １： Suffix Link の応用： Suffix TreeのDAG化
配列解析アルゴリズム特論 渋谷

接尾辞木の中を見ると、類似構造がある
それをまとめてsuffix treeを小さくできるSuffix Linkをたどって、子供の数が同じであればまとめる
Suffix Link Treeを辿るだけでできるので、O(n)Suffix tree of 'mississippi$'
All thesuffixes

mississippi$
ississippi$
ssissippi$
sissippi$
issippi$ssippi$sippi$
ippi$
ppi$
pi$
i$

s

i
ppi$

$
ssi

p
i$

ppi$

pi$

ppi$

ssippi$

i

si

ppi$

mississippi$
ssippi$ssippi$拡張 2： ： Suffix Tree/Arrayの間引き
配列解析アルゴリズム特論 渋谷通常のテキストで区切りがしっかりしている場合はすべての接尾辞を扱う必要はない
全部を作成して、間引きする一部の接尾辞集合からBentley-Sedgewick等の文字列用のアルゴリズムを用いる（接尾辞配列）
単語を一つの文字だと思ってハッシュあるいは単純なテーブル（あるいはキーワード木）で数値に変換し、変換した数列に対し接尾辞木・接尾辞配列を作成する
Not every suffix has to be indexed as many of them will never be searched...

注） 他にも（もっと高度な）接尾辞木・接尾辞配列を圧縮する手法が多く開発されている

拡張 3： Circular String に対する接尾辞木・配列
配列解析アルゴリズム特論 渋谷バクテリアのＤＮＡなどは環状
環状の文字列に対する接尾辞木・接尾辞配列が必要（仮想的に）二回繰り返した文字列を考えるだけ適当に切断コピーを作ってつなげる

[Baker ’92]

Parameterized Matching

配列解析アルゴリズム特論 渋谷 ２種類のアルファベット
 通常のアルファベット
 パラメータ permutation

p-match
AxyzByz = AyzxBzx (x = {x, y, z}

y, y

z, z

x)

 = { A, B} Encoding for p-Strings (p-Encoding)◆ 前出の同一パラメータまでの距離に変換
 0 for left-most parametersprev(AxyzByz) = A000B33◆ このコーディングが同じであればp-match 効能◆ 学生のレポートが他人のレポートのコードの変数を改変しただけのコードだった時にそのチェックに使うことができる。
◆ ソフトウェアを発注した時に、行数でお金を払うが、単なるコピーはもちろん、変数だけを改変したコードにはお金を払いたくない、という
ときのチェックができる。
◆ RNA構造解析

拡張４： Parameterized Suffix Tree
配列解析アルゴリズム特論 渋谷 p-stringに対する接尾辞木 通常の接尾辞木とは異なり、p-suffix のsuffixはp-suffixとは限らない 構成アルゴリズム O(n(log |  | + log |  |))[Kosaraju ’95, Shibuya '04]

0

p-Suffix tree of ‘AxyzByxzBxy$’
B00
A000B354B35$

Encoded000B354B35$
suffixes 00B304B35$
0B004B35$
B000B35$000B35$00B05$
0B00$
B00$
00$
0$

A000B354B35$

0

B00

$

$
$

B

0B35
$

0B35$
4B35$

304B35$

$

05$
4B35$

RNA 構造比較
配列解析アルゴリズム特論 渋谷ＲＮＡ構造の部分構造で全く同じ部分を探したい

Some RNA structure

exists?

query

RNA構造をp-stringで表現
配列解析アルゴリズム特論 渋谷 i 番目と j 番目が結合していたら pi = i - j (ただしj<i).
それ以外の場合 pi = 0.

j 15

i

pi = 15
p-Encoding

0, 0, 0, .... , 9, 11, 13, 15, 0, 0, ......

RNA Structure

Then...
配列解析アルゴリズム特論 渋谷あとはp-suffix treeを作成するだけ

0, 0, 0, ... , 9, 11, 13, 15, ...
0, 0, ... , 9, 11, 13, 15, ...
...
... , 9, 11, 13, 15, ...
... , 9, 11, 13, 0, ...
... , 9, 11, 0, 0, ...
... , 9, 0, 0, 0, ...
... , 0, 0, 0, 0, ...
All the suffixes...
0, 0, 0, ...
0, 0, ...
...

0に変わるところがあることに注意拡張5： RNAのマッチング その２
配列解析アルゴリズム特論 渋谷あるＲＮＡ配列がとりえる構造の集合が同じであるような部分文字列を探したい

CAUGCAUG
sequence
structure set

例
配列解析アルゴリズム特論 渋谷

AUGUACGUAAUCGGCGUGUCCCGUUAUCCGUGAGUCGGACUUAUAAUAUCGUAUGGCCGAGCCUGCCUCAUGUGCCACGUACGCCGUAGUGACACAUCCGCG
UCCGCGUAGCGAAUUACAUUGUCUAAUCGAUAGCGACUAACCGCUGACUGUAAGCGCUCCGCGGUCAA

substring 1: AUAUCGUAUGGCCGAGCC
substring 2: CGCGUAGCGAAUUACAUUOne of the structures

Structural String (s-String)[Shibuya '04]
配列解析アルゴリズム特論 渋谷 p-stringのパーミュテーションに制限をつける
 直前の相補文字への距離も用いる

RNA sequence : AUAUCGUAUGGCCGAGCC
prev(i) : 002200352417137541
cmpl(i) : 011101411561216312

AxyBzwyzwx = AzwByxwyxz ( x → z , z → y )s-match = {A, B},  = {x, y, z , w}
Complementary pairs: {x,y}, {z,w}x → y  complement( x) → complement( y )s-Suffix Tree
配列解析アルゴリズム特論 渋谷 s-suffix tree
◆ 同じようにs-suffixに対する接尾辞木◆ O(n (log p + log q))で作成可能 （p, q: アルファベットサイズ）

s-Suffix tree of ‘AUAUCGU$’
s-Encoded
suffixes

0022003$0111014$002003$011014$00003$
01014$
0003$
0010$
000$
010$
00$
00$
0$
0$

0
0
0
0

$
0
1

$
03$
10$

0
0
03$
14$

2
1

$

2003$
1014$
003$
014$

拡張6： 木に対する接尾辞木
配列解析アルゴリズム特論 渋谷 Target Tree
 枝は文字を持つ 葉からルートへの文字列を考える
 表せる文字列のサイズはO(n2)(n: size of the tree) 木に対する接尾辞木 表されている文字列に対する一般化接尾辞木に相当するもの O(n) algorithm [Breslauer '98, Shibuya '03]
 より小さく保持したデータ構造としてxbw [Ferragina, Manzini, 2009]がある FM-indexの技術を用いて簡潔構造として表現

 効能
 木の部分マッチングのアルゴリズムの（理論的な）サブルーチンとして使う
 その後、よりよいアルゴリズムが出てきて今は使われていない

 オートマトンの最小化
 Tree kernel [Kimura et al. 2011]
 木構造の中から頻出パスを探せる
1

A tree representing
7 strings
Size: 13
Sum of the represented
string sizes : 33

4
5

9

5

1

3

6
3

2
5

8

$

1313$
5413$
913$
56213$
3213$
5213$
83$

拡張7： 木に対する接尾辞木 （２）： BSuffix Tree
配列解析アルゴリズム特論 渋谷順序付二分木の中の完全二分木である部分木を表したtrie木の中から完全二分木である部分木を探す
1

v1

2 v2
3

v4

4

v3
v6
v5

3 v8

2
4

1

O(n)

1

21

v7 1
v9

3421
$1

3
4
v 10 v 11

34
$7

3434
$3

3434
$6

2
34
$2

34
$8
$
$4 $10 12

134exist in

1
3

4

3

v4

4

$15

$5 $11

$13

v1

2 v2

1
2

34
$9

$14

3
4
3
4
v 12 v 13 v 14 v 15

Does

4

3

v6
v5

3 v8

v3

1

2

v7 1

4

v9

3
4
v 10 v 11

34
34
v 12 v 13 v 14 v 15?

拡張8： LSuffix Trees (ISuffix Trees)[Giancarlo '93]
配列解析アルゴリズム特論 渋谷n×m行列上の部分正方行列をすべてtrieで表したものFarachのアルゴリズムの応用でO(nm) [Kim & Park '99]

画像処理への応用もトリミング画像検索

k次元への拡張も
さらにp-suffix treeと組み合わせた一般化もあり
mn拡張9： Geometric Suffix Tree

[Shibuya J.ACM 2010]
配列解析アルゴリズム特論 渋谷Suffix treeを3次元構造検索へ拡張
RMSDがincrementalに計算できることを利用
p2
p4

p9

q2

p3

q1
P[1..7],R1, v1

q3

p5

q4

p7

RMSD ≤
b/sqrt(7)

p6
p8

p1

p11
p10

q5
q6

q8

P[8..11],
R1, v1

q9

q7
q10

q11

Q[8..11],
R2, v2

P[1..7]+Q[8..11] issimilar to Q[1.11]

Block Sorting 圧縮 [Burrows, Wheeler '94]
配列解析アルゴリズム特論 渋谷 BWT (Burrows-Wheeler Transform) Suffix Array と極めて関連が深い （FM-Index）

 MTF（move to front） coding ここまでは全く圧縮されていない状態

 これらを行った後、通常のハフマン符号・算術符号等を用いてさらに圧縮
 処理するのに巨大すぎる場合はブロック化→ブロックソーティング BW変換するためのメモリ・計算時間に限界

cf.

10: i$
0: mississippi$
7: ippi$
1: ississippi$
4: issippi$
2: ssissippi$
1: ississippi$
3: sissippi$
0: mississippi$
4: issippi$
9: pi$
5: ssippi$
8: ppi$6: sippi$
ソート
6: sippi$
7: ippi$
3: sissippi$
8: ppi$5: ssippi$
9: pi$
10: i$
接尾辞配列 2: ssissippi$

BWT (Burrows-Wheeler Transform)
配列解析アルゴリズム特論 渋谷 接尾辞配列：SA[0..n] ただし、文字列はサイクル化したものを考える
 文字列の最後に$を入れておけば、通常のSAと特に違いはない

 BWT[i] = T[SA[i]−1]サイクル化した全接尾辞

BWT

0: mississippi$
1: ississippi$m
2: ssissippi$mi
3: sissippi$mis
4: issippi$miss
5: ssippi$missi
6: sippi$missis
7: ippi$mississ
8: ppi$mississi
9: pi$mississip
10: i$mississipp
11: $mississippi

10: i 11: $mississippi
9: p 10: i$mississipp
6: s 7: ippi$mississ
3: s 4: issippi$miss
0: m 1: ississippi$m
11: $ 0: mississippi$
8: p 9: pi$mississip
7: i 8: ppi$mississi
5: s 6: sippi$missis
2: s 3: sissippi$mis
4: i 5: ssippi$missi
1: i 2: ssissippi$mi

ソート

接尾辞配列

同じ

ＢＷＴの性質
配列解析アルゴリズム特論 渋谷 似た文字がかたまって出現する
 似た文字列の前は同じ文字が出現しやすいから！
 この性質を利用して圧縮するとかなり小さくできる MTF変換＋算術符号等

 この文字列からもとの文字列を復元できる！
BWT

mississippi$
復元

接尾辞配列

10: i 11: $mississippi
9: p 10: i$mississipp
6: s 7: ippi$mississ
3: s 4: issippi$miss
0: m 1: ississippi$m
11: $ 0: mississippi$
8: p 9: pi$mississip
7: i 8: ppi$mississi
5: s 6: sippi$missis
2: s 3: sissippi$mis
4: i 5: ssippi$missi
1: i 2: ssissippi$mi

ＢＷＴの復元
配列解析アルゴリズム特論 渋谷n 桁のRadix Sortを行うだけただし、そのまままともにやると計算量が O(n2)実はO(n)にできる！
BWT
i
p
s
s
m
$
p
i Sort
s
s
i
i

$
i
i
i
i
m
p
p BWTを
s 頭に加
s えて
s
s

１文字目が
得られる

i$
pi
si
si
mi
$m
pp
ip Radix
ss Sort
ss
is
is

$m
i$
ip
is
is
mi
pi
pp BWTをsi 頭に加
si えて
ss
ss

２文字目が
得られる

i$m
pi$
sip
sis
mis
$mi
ppi
ipp
ssi
ssi
iss
iss

$mississippi
i$mississipp
ippi$mississ
issippi$missississippi$m
mississippi$
pi$mississip
Radix Sortを
ppi$mississi
繰り返して、
sippi$missis
最終的にはsissippi$mis
ssippi$missi
ssissippi$mi
すべてを得ることができる

ＢＷＴの線形時間復元
配列解析アルゴリズム特論 渋谷 （一桁分の）ソートの動きを逆に辿っていく 最初の文字がどれに相当するか覚えておく ただし、覚えてなくても $ を探してそこから始めればＯＫ最初の文字からスタート→を辿りながら、BWT側の文字を出力

BWT
i
p
s
s
m
$
p
i
s
s
i
i

ソートされた文字（接尾辞配列の最初の文字）

$
i
i
i
i
m
p
p
s
s
s
s
Bucket Sort
（同じ文字ならば順番は変えない＝ Radix sortの基本）

MTF(move to front) Coding
配列解析アルゴリズム特論 渋谷 同じ文字が前回出現してから、何種類の他の文字が出現したか？
 初出の文字は適当に処理
 BWT後の文字列を変換すれば偏りのある数字列になる
 小さい数字が多く現れる
 算術符号その他の適当なアルゴリズムで圧縮すれば、かなり小さくできる デコードは簡単
 計算量
 バランス木で表現すればO(n log s)

テキスト
変換した数字
変換表

0
1
2
3

adbdbaabacdadc
03211201133212
aadbdbaabacdadc
bbadbdbbabacdad
ccbaaaddddbacca
ddccccccccdbbbb
出来の悪いウィンドウズのメニューみたいな

適当BW変換による索引： FM-Index
配列解析アルゴリズム特論 渋谷 ＢＷ変換を用いて検索もできる！

[Ferragina Manzini, 2000]

 逆方向検索： 接尾辞木のWeiner Algorithmの逆suffix linkを辿ることに相当する
１文字前に着目！
BW変換した
文字列にAがいくつあるかがわかれば、
α の接尾辞配列
上の場所から、Aαの接尾辞配列
上の場所が
計算できる

文字列 Aα

Aで始まる接尾辞

Cで始まる接尾辞

文字列 αGで始まる接尾辞

Tで始まる接尾辞
Suffix Array例 (1/4)
配列解析アルゴリズム特論 渋谷 後ろから検索する！
 “ssis” の最後の１文字 “s” は？
 これは覚えておいたものをそのまま使う
BWTs

この情報は覚えておく

接尾辞配列

10: i 11: $mississippi
9: p 10: i$mississipp
6: s 7: ippi$mississ
3: s 4: issippi$miss
0: m 1: ississippi$m
11: $ 0: mississippi$
8: p 9: pi$mississip
7: i 8: ppi$mississi
5: s 6: sippi$missis
2: s 3: sissippi$mis
4: i 5: ssippi$missi
1: i 2: ssissippi$mi$で始まる接尾辞iで始まる接尾辞mで始まる接尾辞pで始まる接尾辞sで始まる接尾辞“mississippi$” に対するBW変換

例 (2/4)
配列解析アルゴリズム特論 渋谷“ssis” の後ろ2文字 “is” は？
BW変換中で “i” の数を数える
実際にはwavelet treeを用いる
BWT

2

2個

s
4個

計算

4

接尾辞配列

10: i 11: $mississippi
9: p 10: i$mississipp
6: s 7: ippi$mississ
s 4: issippi$miss
is 3:
0: m 1: ississippi$m
11: $ 0: mississippi$
8: p 9: pi$mississip
7: i 8: ppi$mississi
5: s 6: sippi$missis
2: s 3: sissippi$mis
4: i 5: ssippi$missi
1: i 2: ssissippi$mi$で始まる接尾辞iで始まる接尾辞mで始まる接尾辞pで始まる接尾辞sで始まる接尾辞“mississippi$” に対するBW変換例 (3/4)
配列解析アルゴリズム特論 渋谷“ssis” の後ろ3文字 “sis” は？
BW変換中で “s” の数を数える
BWT

1個

is

2個

1

2

sis

計算

接尾辞配列

10: i 11: $mississippi
9: p 10: i$mississipp
6: s 7: ippi$mississ
3: s 4: issippi$miss
0: m 1: ississippi$m
11: $ 0: mississippi$
8: p 9: pi$mississip
7: i 8: ppi$mississi
5: s 6: sippi$missis
2: s 3: sissippi$mis
4: i 5: ssippi$missi
1: i 2: ssissippi$mi$で始まる接尾辞iで始まる接尾辞mで始まる接尾辞pで始まる接尾辞sで始まる接尾辞“mississippi$” に対するBW変換

例 (4/4)
配列解析アルゴリズム特論 渋谷“ssis” は？ （これが求めるもの）
BW変換中で “s” の数を数える
BWT

10: i 11: $mississippi
9: p 10: i$mississipp
6: s 7: ippi$mississ
3: s 4: issippi$miss
0: m 1: ississippi$m
11: $ 0: mississippi$
8: p 9: pi$mississip
7: i 8: ppi$mississi
5: s 6: sippi$missis
2: s 3: sissippi$mis
4: i 5: ssippi$missi
1: i 2: ssissippi$mi

3個
3

sis

接尾辞配列

4

4個

$で始まる接尾辞iで始まる接尾辞mで始まる接尾辞pで始まる接尾辞sで始まる接尾辞ssis
計算“mississippi$” に対するBW変換

FM-Index (3)配列解析アルゴリズム特論 渋谷位置を知るには？
BW-変換されたテキストの上のある
位置が元のどの位置に対応するのか（＝すなわちsuffix arrayの値）は、そこからdecodeを行えばよい
BWTの復元の要領で
接尾辞が復元される（＝その長さがわ
かる＝位置がわかる）
ただし、それでは O(n) の時間がかかる

間引きされたsuffix arrayを持っておくとよい z ごとに間引くと、 z 倍のオーバーヘッ
ドがかかる

BWT
i
p
s
s
① m
$
p
i
④ s
③ s
i
② i

$
i
i
i
i
m
p
p
s
s
s
s

矢印を逆にたどっていくFM-Index (4) : WeinerのPrefix Linkと検索
配列解析アルゴリズム特論 渋谷 葉のSuffix link（群）を逆にたどる（すなわちPrefix linkを辿る）と逆順の部分文字列になる、ということと対応している
Suffix tree of 'mississippi$'
mississippi$
ississippi$
ssissippi$
sissippi$
issippi$ssippi$sippi$
ippi$
ppi$
pi$
i$

All thesuffixes

これに注目していることと
同じ

$
i

pp$

i$

ssi

ppi$

s

p

$

pi$

i
ssippi$‘s’で始まる葉

ppi$

i

s

si

ppi$
ssippi$mississippi$

i

ひとつ前が ‘i’ のものは２つssippi$s‘s’の前が’i’である葉‘s’ の前が ‘i’ であるものを探す

FM-Index (5) : 検索に必要なデータ構造
配列解析アルゴリズム特論 渋谷この時、ＢＷ変換した文字列以外に必要なもの：なんと、接尾辞配列、元の文字列は保持しなくてよい！！！
すなわち、以下の補助データ構造のサイズが十分小さければ、これは極めてコンパクトな索引構造として利用することができる！
さらに、（遅さを気にしなければ）BW変換した文字列は圧縮可能！
 ただし、任意の i に対し i 文字目に、（圧縮率のために速さを犠牲にしたとしても）何らかの方法でアクセス可能な圧縮方法でないといけない各文字が何文字ずつあるかを覚えておくことで、
次のindexを計算できる
逆に、indexからそれに対応する文字が何か計算できる

ＢＷ変換した文字列BW[0..n]上で（多少遅くてもよいので）
BW[0..i]に文字xがいくつあるかが計算可能な（なるべく小さな）データ構造（Rank/Select データ構造）

Rank / Select データ構造
配列解析アルゴリズム特論 渋谷３つの操作access(A, i) = A[i]rankc(A, i) = #j s.t., A[j]=c, j<iselectc (A, i) = j s.t., rankc(A, j) = i

ナイーブに表を持つと
access
元の文字列を持っているだけでＯＫrankselect

a
b
c
b
c
c

a

b

c

1

0

0

1

1

0

1

1

1

1

2

1

1

2

2

1

2

3

A

ナイーブなrank表いずれも、（文字の種類数）×（文字列長）×（整数のサイズ）のサイ
ズの表で、constant timeを（線形時間の前処理で）実現できる
片方がconstant timeでできれば、他方は二分探索でO(log n)が可能

が、これではＢＷ変換の補助データ構造のサイズが通常の接尾辞配列のアルファベットサイズ倍、という巨大なものになってしまう！（それではほとんど意味がない）小さくする方法： ブロック化による間引き
配列解析アルゴリズム特論 渋谷０１列の場合
wビットずつに分割して、wビットずつの間引きされたrank結果
は覚えておく2w種類のすべてに関してrankの結果を計算し、保管する
RMQのアルゴリズムと少し類似

すると必要なメモリは𝑛𝑤

( ) · log 𝑛 + 2𝑤 log 𝑤 bit
𝑤 = log 𝑛 とすると これは 𝑛 + 𝑛 log log 𝑛 bit 接尾辞配列（𝑛 log 𝑛 bit）よりは小さそう が、BW変換後の文字列 (𝑛 bit）よりは大きいrankの計算時間は constant timeで可能
0110101110101100010101100001110100110

ブロック化による間引き その２
配列解析アルゴリズム特論 渋谷 先ほどのブロック化では、間引いたrankはすべての桁を保持していた（＝大きな数字を覚えていて無駄） ２段階ブロック化
 l ビットごとにブロック化（大ブロック）
 先頭のrankはすべて記憶 途中については、大ブロック先頭からの差分で記憶する それぞれのブロックをwビットごとにブロック化
 この中は先ほど（その１）と同様の計算を行う

 すると、それだけで𝑛𝑤 log 𝑤 bitで格納できる
log
𝑙
+
2
𝑤
 これは𝑙 = log 2 𝑛、𝑤 = (log 𝑛)/2 の時、o(n)ビット𝑛𝑙log 𝑛 +

→ 無視できる！

0110101110101100010101100001110100110- select も同様のことが可能だが、通常は２分探索で実現することが多い- アルファベットサイズが大きい場合も同様のことは可能だが、大きくなってしまう。

Wavelet 木Wavelet 木（概要）
配列解析アルゴリズム特論 渋谷 文字列に対するrank/selectをアルファベットに関する２分
探索的に行うデータ構造
 それぞれの01列に対し先ほどのデータ構造を作成すれば、bit列の場合のlog(アルファベットサイズ）倍＝文字列サイズですむ

ACのみ抽出ATGCGCGATACTGAT
011010101001101

GTのみ抽出A

1

0

ACCAACA
0110010
A/Cで分類

AC/GT で分類

0

1

0

1

C

TGGGTTGT
10001101

GT

G/Tで分類
様々な応用があるYet Another 圧縮索引： 圧縮接尾辞配列
配列解析アルゴリズム特論 渋谷接尾辞配列を（もう少しストレートに）圧縮するには？
Ψ（プサイ、接尾辞配列上のSuffix Link）を用いることが可能すなわち、FM-Indexとは完全に逆の考え方！

エントロピーに比例した圧縮が可能順方向の検索がメインとなる
0: mississippi$
1: ississippi$
2: ssissippi$
3: sissippi$
4: issippi$
5: ssippi$
6: sippi$
7: ippi$
8: ppi$9: pi$
10: i$

ソート

接尾辞配列

10: i$
7: ippi$
4: issippi$
1: ississippi$
0: mississippi$
9: pi$
8: ppi$6: sippi$
3: sissippi$
5: ssippi$
2: ssissippi$

Suffix Array 上の Suffix Link
配列解析アルゴリズム特論 渋谷プサイ Ψ (接尾辞配列上のSuffix Link) 逆接尾辞配列から簡単に作成可能

 Textは記憶しなくてよい
 必要ならばΨ（とアルファベットリスト）から計算可能なためIndex / All suffixes

0: mississippi$
1: ississippi$
2: ssissippi$
3: sissippi$
4: issippi$
5: ssippi$
6: sippi$
7: ippi$
8: ppi$9: pi$
10: i$
11: $ソート

Index / Suffix array / suffixesΨ

0:11: $
1:10: i$2: 7: ippi$
3: 4: issippi$
4: 1: ississippi$
5: 0: mississippi$
6: 9: pi$
7: 8: ppi$
8: 6: sippi$
9: 3: sissippi$
10:5: ssippi$
11:2: ssissippi$

0
7
10
11
4
1
6
2
3
8
9

Ψからのテキストの復元
配列解析アルゴリズム特論 渋谷一番長い接尾辞がどこにあるかを覚えておいて、そこからΨを辿っていくだけで、復元できる
アルファベットがそれぞれ何個あるかは覚えておく
Index / Suffix array / suffixesΨ

0:11: $
1:10: i$2: 7: ippi$
3: 4: issippi$
4: 1: ississippi$
5: 0: mississippi$
6: 9: pi$
7: 8: ppi$
8: 6: sippi$
9: 3: sissippi$
10:5: ssippi$
11:2: ssissippi$

0
7
10
11
4
1
6
2
3
8
9

i
m
p
s

ここから開始Ψの圧縮
配列解析アルゴリズム特論 渋谷 アルファベットごとに区切ると単調増加
 差分で覚える
すると、小さい値が非常に多くなり、圧縮しやすくなる しかも、似たもののsuffix link先も似ているため類似部分列も多い→ 圧縮効率も良い！
 cf. 接尾辞木のDAG化
Index / Suffix array / suffixesΨΨi - Ψi-1

0:11: $
1:10: i$2: 7: ippi$
3: 4: issippi$
4: 1: ississippi$
5: 0: mississippi$
6: 9: pi$
7: 8: ppi$
8: 6: sippi$
9: 3: sissippi$
10:5: ssippi$
11:2: ssissippi$

0
7
10
11
4
1
6
2
3
8
9

7
3
1
5
1
5
1

i

m
p
s

Ψの圧縮
配列解析アルゴリズム特論 渋谷しかし、差分で覚えると、実際の値を計算するのに時間がかかってしまう間引いて途中の値を適当に覚えておけばよい
O(n/log n)程度のサイズに間引けば、O(log n)時間で計算できる、といったかんじ
スピード⇔圧縮率 のトレードオフあり

元の数列： 3 4 7 8 13 24 26 32 37 45 54 61 70 ...
差分：- 1 4 1 5 9 2 6 5 8 9 7 9 ...

Ψを用いた検索
配列解析アルゴリズム特論 渋谷SA上のある位置のsuffixはΨから簡単に復元可能
これを利用して二分探索が普通にできるO(m log n)
Index / Suffix array / suffixesΨ

0:11: $
1:10: i$2: 7: ippi$
3: 4: issippi$
4: 1: ississippi$
5: 0: mississippi$
6: 9: pi$
7: 8: ppi$
8: 6: sippi$
9: 3: sissippi$
10:5: ssippi$
11:2: ssissippi$

0
7
10
11
4
1
6
2
3
8
9

i
m
p
s

ippi$
Ψ（suffix link）をたどっていき、それ
ぞれどのアルファベットの領域にあるかをチェックしていく検索結果の位置を知るには？
配列解析アルゴリズム特論 渋谷 SA[i]の値がわかればよい テキスト全体の復元と同様にΨを辿っていけば、計算でき
Index / Suffix array / suffixesる
0:11: $
1:10: i$ ただそれだとO(n)時間かかってしまうため、間引いた接尾 i 2: 7: ippi$
3: 4: issippi$
辞配列をもっておけば、その4: 1: ississippi$
計算時間を短縮できる。
 たとえばO(n / log n)サイズ mにまで間引いておけば大幅 pに時間が短縮できる上に、さほどサイズは大きくなくてすs
む。
 こうしておけば、テキストを部分的に復元することもできる
ようになる。

5: 0: mississippi$
6: 9: pi$
7: 8: ppi$
8: 6: sippi$
9: 3: sissippi$
10:5: ssippi$
11:2: ssissippi$

Ψ
0
7
10
11
4
1
6
2
3
8
9

あいまい検索： Inexact Matching Problem
配列解析アルゴリズム特論 渋谷

問題
テキストの中からクエリーとのedit distanceがk以下のsubstringを「すべて」見つけるテキストに対して前処理を行ってもよい2種類の攻略法
接尾辞木、接尾辞配列等を利用する
kに関して指数的な計算量となる小さなsubstringを用いてexact matchingによる検索を行うこと
でフィルタリングを行う
実際にはその中間的な手法も存在

接尾辞木、接尾辞配列の利用
配列解析アルゴリズム特論 渋谷

接尾辞木上で単に深さ優先探索でerrorが k を超えない地点まで探索する
あるいはそれを接尾辞配列（等）でシミュレート
探索時には通常のＤＰによる比較を行う
isi (k=1)の検索
s

i

ppi$

p

$

i$

ssi

ppi$

pi$

i

ppi$

ppi$

ssippi$si

mississippi$
ssippi$

Suffix tree of 'mississippi$'ssippi$接尾辞木上でのEdit Distance比較
配列解析アルゴリズム特論 渋谷動的計画法格子状のグラフで最長路を求める
編集距離に上限kがあるので O(km)m: クエリーの文字列の長さkノードごとにＤＰ情報を保存する
A

T

G

C

A
C

T

ATGCA--CT

たとえばここで
枝分かれ

接
尾
辞
木
上
の
ル
ー
ト
か
ら
の
パ
ス
クエリー文字列