ALG2015-11

算法数理工学
第11回
定兼邦彦
局所探索法とメタヒューリスティックス
• 発見的解法で得られた近似解に対して，さらに
部分的な修正を繰り返し加えることにより，より
良い近似解が得られる場合が多い
• そのための基本的な戦略を一般にメタヒューリステ
ィックスと呼ぶ
• 局所探索法：様々なメタヒューリスティックスの基礎
• 任意の実行可能解 x に対して，その一部分を修正
して得られる解の集合を N(x) で表し，x の近傍と
呼ぶ
2
• 最小化する目的関数を f とする
局所探索法の一般的な計算手順
(0) 初期解 x を選ぶ
(1) 現在の解 x の近傍 N(x) から f(y) < f(x) を満たす
解 y を選ぶ．そのような解 y が N(x) 内に存在し
なければ計算終了
(2) x を y で置き換えてステップ(1)へ戻る
局所探索法が終了した時点で得られている解 x は，
その近傍 N(x) 内で目的関数が最小である．つまり
局所的最適解になっている．
初期解
局所的最適解
3
• 局所探索法を用いて実際に問題を解くには，近傍
の定義と近傍の探索法が重要
• 一般に，大きい近傍を用いれば現在の解よりも
良い解が見つかる可能性が大きいが，遅くなる
• 近傍の探索法
– 即時移動：近傍内の解を1つずつ順番に調べていき，x
より良い解 y が見つかれば直ちに x を y で置き換える
– 最良移動：近傍内の全ての解を調べて最良の解 y を
見つけ，それを x と置き換える
• 即時移動の方が早いが，最良移動の方が良い解
が出る場合が多い (常に良いとは限らない)
• 探索時間と解精度のトレードオフ
4
TSPでの局所探索法
• 2-opt近傍: 隣り合わない2本の枝を巡回路 x から
取り去り，別の2本の枝を付け加えて得られる
巡回路全体を N(x) と定義する．
• 節点数が n のとき，N(x) に含まれる解の数は
n(n3)/2 = O(n2)
• ユークリッド平面の場合，交差している2つの枝を
つけかえると解は必ず良くなる
5
メタヒューリスティックス
• 発見的解法によって得られた近似解を改良する
ための枠組み
• 局所的最適解から抜け出すことができる
• 焼きなまし法 (simulated annealing)
• タブー探索法 (tabu search)
• 遺伝的アルゴリズム (genetic algorithm)
• ニューラルネットワーク (neural networks)
6
焼きなまし法
• 現在の解の近傍からランダムに解を選ぶ
– それが改良になっていれば新しい解とする
– 改悪になる場合でも，目的関数値の差の大きさに応じ
てある確率で新しい解として採用する
7
f(x) を最小化する場合
(0) 凍結温度 Tfreeze > 0 を定める．
初期温度 T > Tfreeze と初期解 x を選ぶ．
(1) 現在の解の近傍 N(x) からランダムに解 y を選び
，
 := f(y) – f(x) とおく．
(2)  < 0 ならば x を y で置き換える．
(3)   0 ならば，区間 [0,1] から実数  をランダムに
選び，  < e/T ならば x を y で置き換える．
(4) T  Tfreeze ならば終了．
そうでなければ，温度 T を更新して (1) へ戻る． 8
• ステップ(3)では，近傍 N(x) から選ばれた解 y が
改悪となる場合でも，確率 e/T で解を入れ替える
•  > 0 のとき
'
0T T 0 e
'
 /T
e
 /T
1
なので，目的関数の改悪量  が同じでも，温度が
高いときの方が改悪となる解を採用する確率が
大きい
• 計算の最初の段階では温度を高く設定して局所最
適解に捕捉されることを避ける
• 温度を次第に低下していき，改悪が起こる確率を
下げ，安定した探索が行えるようにする
9
• よく用いられる方法：2つのパラメタを用いる
– 0 <  < 1：温度の減少率
– 1 <  < 2: 反復回数
• ある温度 T で r 回の探索を行った後，
– 温度を T に下げる
– 新しい温度での反復回数を r にする
• 時間はかかるが良い解を得ることが期待できる
10
タブー探索法
• 局所探索法では，現在の解 x の近傍 N(x) 内で
f(y) < f(x) を満たす解 y へ移動する
• そのような解がなければ x は局所的最適解なので
計算を終了する
• さらに連続して探索を行えるようにするため，N(x)
において x を除いた中での最良の解 y を見つけ，
f(y)  f(x) であっても y に移動する
• しかし，y に移動したあとで局所探索を続けると
また x に戻ってしまう
11
• 同じ解の再探索を避けるようにしたい
• タブー探索法では，過去の反復で現れた解や移動
のパタン (2-optで入れ替えた枝など) をタブーリスト
と呼ばれる集合として記憶しておく
• 新しい解に移動するときは，タブーリストに含まれ
ない解の中で最良のものに移動する
• タブーリストが長くなるとメモリを多く消費し，探索も
遅くなるので，リストの長さは上限を決めておく
• リストの古い情報は捨てる
12
タブー探索法
(0) 初期解 x を選ぶ．タブーリストの最大長 l を定め,
初期タブーリストを L :=  とする
(1) 現在の解 x の近傍 N(x) において，x 自身と
タブーリスト L に含まれる解を除く最良の解 y を
見つけ，x を y で置き換える
(2) タブーリスト L に新しい解 x を追加する．もし L の
大きさが l を越えれば，最も古い要素を L から
取り除く
(3) 停止条件が満たされれば計算終了．
13
そうでなければステップ(1)へ戻る．
• メタヒューリスティックスは，複雑な組合せ最適化
問題に対する実際的なアルゴリズムを構築する
ための柔軟な枠組み
• 計算を効率的に行うにはアルゴリズムに含まれる
パラメタや近傍を適切に設定する必要がある
• 計算実験などによって得られる知識を利用するこ
とが重要
14
文字列検索
• 情報検索で必須の処理
– サーチエンジン
– ゲノム情報処理
• データ量が莫大
– Web: >20億ページ, 数テラバイト
– DNA配列: ヒト=28億文字, 総計>150億文字
15
文字列検索問題
• 文字列 T の i 番目の文字を T[i], i 番目から j 番
目の文字からなる文字列を T[i..j] と表記する
• 文字列 T の長さを |T| と書く
• 文字列 P が, ある i と j に対して P = T[i..j] となっ
ているとき, P は T の部分文字列であるという.
また, T の i 文字目は P とマッチするという
• 文字列検索問題は，文字列 P と文字列 T を入力
し, P が T の部分文字列となっている場所, つまり
16
P = T[i..j] となる i を全て見つける問題
文字列検索アルゴリズム
• 逐次検索
– P と T が与えられてから問題を解く
– 絶対に O(|P|+|T|) 時間かかる
– KMP法，BM法，Z法など
• 索引検索
– T が予め与えられたとき，何らかのデータ構造 D を
作っておく．P が与えられたときに D を用いて問題
を高速に解く
– 転置ファイル，接尾辞木，接尾辞配列など
17
逐次検索アルゴリズム
• 文字列マッチングを簡単に解こうと思ったら,
各 i について P = T[i..i+|P|1] となるかどうかを
調べればよい
• O( |T|  |P| ) 時間のアルゴリズムができる
• もう一工夫して速くする方法を考える
• Z アルゴリズム
– 最も単純な線形時間 (O(|T|+|P|)) アルゴリズム
18
• 定義: 文字列 S と位置 i > 1 に対し，Zi(S) を
S の i 文字目から始まる部分文字列で, S の
接頭辞と一致するものの中で最長のものの
長さと定義する．
• 例： S = aabcaabxaaz のとき
–
–
–
–
–
–
Z2(S) = 1 (aa…ab)
Z5(S) = 3 (aabc…aabx)
Z6(S) = 1 (aa…ab)
Z9(S) = 2 (aab…aaz)
Z10(S) = 1 (aa…az)
それ以外は Zi(S) = 0
19
• 定義: i > 1 かつ Zi(S) > 0 のとき，i でのZ-boxを
区間 [i, i+Zi(S)1] と定義する
• 定義: i > 1 に対し，ri を 1< j  i でのZ-boxの
右端点の最大値と定義する．また，li をそのとき
の j と定義する．(j が複数ある時はどれでも可)
1 2 3 4 5 6 7 8 9 10 11
• 例： S = a a b c a a b x a a z のとき
Zi
ri
li
1 0 0 3 1 0 0 2 1 0
2 2 2 7 7 7 7 10 10 10
2 2 2 5 5 5 5 9 10 10
• Z は O(|S|2) 時間で計算できる
• O(|S|) 時間で計算したい
20
• Zi, ri, li が 1 < i  k1 に対して計算済みのとき，
Zk を計算する
• r = rk1, l = lk1 とする
• k > r のとき (k がZ-boxに含まれないとき)
– S[k..n] と S[1..n] を1文字ずつ比較して Zk を求める
– Zk > 0 ならば r = k+Zk1, l = k
• k  r のとき (k があるZ-boxに含まれるとき)
– S[k]  S[l..r]
– S[l..r] = S[1..rl+1] より， S[k] = S[kl+1]
– 同様に S[k..r] = S[kl+1.. rl+1]
1
kl+1
rl+1
l
k
r
21
• 2つの場合が考えられる
– case 2a: Zkl+1 が S[k..r] の長さより小さいとき
Zk = Zkl+1

1


kl+1
rl+1
l
k
r
– case 2b: Zkl+1 が S[k..r] の長さ以上のとき
S[r+1..n] と S[rl+1+1..n] を比較 (q 文字一致)
Zk = (rk+1)+q
r=r+q
l=k

1


kl+1
rl+1
l
k
?
r
r+q
22
定理: 全ての Zi は O(|S|) 時間で求まる
証明: ループの回数は |S| 回．
文字列の比較は必ずミスマッチで終わる
⇒ミスマッチの回数はループの回数以下
マッチの回数を見積もる．
1回の文字列比較で q 文字マッチしたとすると，
r は少なくとも q 増加する．また，r は減少しない．
r  |S| よりマッチの回数は |S| 以下．
23
Z アルゴリズム
• S = P$T とする．(|P|  |T| とする)
– $ は P, T に現れない文字
• Zi(S) を計算する
– O(|P|+|T|) 時間
• Zi(S) = |P| ならば P は S の部分文字列
i は必ず T の中になる (P は $ を含まないから)
⇒ P は T の部分文字列
• そのままだと O(|P|+|S|) 領域だが，O(|P|) にできる
– Zi(S)  |P| なので，参照される Zi はO(|P|)領域で格納可
24
索引検索
• Web検索のように，決まった文字列に対して
何度も検索を行う場合は，索引検索の方が高速
• 単語索引
– 決まった単語のみを検索できる
– 索引のサイズが小さい
– 転置ファイル
• 全文検索
– 任意の部分文字列を検索できる
– 索引が大きくなる
– 接尾辞木，接尾辞配列
25
転置ファイル
• 文字列を単語(形態素)に分解
• 単語ごとに出現位置(出現文書)を列挙
• 出現回数も記憶
1
4
8
12
15
19
いるかいないかいないかいるかいるいるいるか
T = いるか|いないか|いないか|いるか|いるいる|いるか
いるか: 3回 (1, 12, 19)
いないか: 2回 (4, 8)
いるいる: 1回 (15)
26
文字列検索の問題点
• 任意の文字列を検索したい
• 部分文字列の数 = nC2 = O(n2)
• 全ての部分文字列を索引に格納
⇒索引サイズ: O(n2)
27
接尾辞 (suffix)
• 文字列 T の先頭の何文字を除いたもの (n 種類)
• T の任意の部分文字列は，ある接尾辞の接頭辞
1 いるかいないかいないかいるかいるいるいるか
2 るかいないかいないかいるかいるいるいるか
3 かいないかいないかいるかいるいるいるか
4 いないかいないかいるかいるいるいるか
5 ないかいないかいるかいるいるいるか
6 いかいないかいるかいるいるいるか
7 かいないかいるかいるいるいるか
8 いないかいるかいるいるいるか
9 ないかいるかいるいるいるか
10 いかいるかいるいるいるか
11 かいるかいるいるいるか
12 いるかいるいるいるか
13 るかいるいるいるか
14 かいるいるいるか
15 いるいるいるか
16 るいるいるか
17 いるいるか
18 るいるか
19 いるか
20 るか
21 か
=T
28
接尾辞木 [Weiner 73]
• 全ての接尾辞を格納したcompacted trie
か
な
る
い
い
か
か
な
い
な
る
る
い
か
い
い
6
10
4
8
15
17
19
1
12
21
3
7
14
11
5
9
16
18
20
2
13
いかいないかいるかいるいるいるか
いかいるかいるいるいるか
いないかいないかいるかいるいるいるか
いないかいるかいるいるいるか
いるいるいるか
いるいるか
いるか
いるかいないかいないかいるかいるいるいるか
いるかいるいるいるか
か
かいないかいないかいるかいるいるいるか
かいないかいるかいるいるいるか
かいるいるいるか
かいるかいるいるいるか
ないかいないかいるかいるいるいるか
ないかいるかいるいるいるか
るいるいるか
るいるか
るか
るかいないかいないかいるかいるいるいるか
29
るかいるいるいるか
接尾辞配列 [Manber, Myers 93]
• 接尾辞のポインタを辞書順にソートした配列
SA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
いるかいないかいないかいるかいるいるいるか
るかいないかいないかいるかいるいるいるか
かいないかいないかいるかいるいるいるか
いないかいないかいるかいるいるいるか
ないかいないかいるかいるいるいるか
いかいないかいるかいるいるいるか
かいないかいるかいるいるいるか
いないかいるかいるいるいるか
ないかいるかいるいるいるか
いかいるかいるいるいるか
かいるかいるいるいるか
いるかいるいるいるか
るかいるいるいるか
かいるいるいるか
いるいるいるか
るいるいるか
いるいるか
るいるか
いるか
るか
か
6
10
4
8
15
17
19
1
12
21
3
7
14
11
5
9
16
18
20
2
13
いかいないかいるかいるいるいるか
いかいるかいるいるいるか
いないかいないかいるかいるいるいるか
いないかいるかいるいるいるか
いるいるいるか
いるいるか
いるか
いるかいないかいないかいるかいるいるいるか
いるかいるいるいるか
か
かいないかいないかいるかいるいるいるか
かいないかいるかいるいるいるか
かいるいるいるか
かいるかいるいるいるか
ないかいないかいるかいるいるいるか
ないかいるかいるいるいるか
るいるいるか
るいるか
るか
るかいないかいないかいるかいるいるいるか
30
るかいるいるいるか
接尾辞配列を用いた文字列検索1
•
•
•
•
P[1..m] を探すことを考える
まず, P[1]から始まる接尾辞の範囲 [s,t] を求める
全ての i  [s,t] に対し，T[SA[i]] = P[1] である
全ての i  [s,t] に対し，接尾辞の2文字目
T[SA[i]+1] はアルファベット順に並んでいる
• [s,t] の範囲で T[SA[i]+1] に従って2分探索し，
2文字目が P[2] である接尾辞の範囲 [s’,t’] を
求める
• m 回繰り返す
31
• O(m log n) 時間
接尾辞配列を用いた文字列検索2
• 整数の配列での2分探索と同様に行う
• ただし，1回の比較は文字列同士の比較
– 長さ m の文字列の比較なので O(m) 時間
• O(log n) 回の文字列比較なので
全体で O(m log n) 時間
32
接尾辞配列を用いた検索
• SA の上で二分探索
P = いるか
3回 (1, 12, 19)
SA
6
10
4
8
15
17
19
1
12
21
3
7
14
11
5
9
16
18
20
2
13
いかいないかいるかいるいるいるか
いかいるかいるいるいるか
いないかいないかいるかいるいるいるか
いないかいるかいるいるいるか
いるいるいるか
いるいるか
いるか
いるかいないかいないかいるかいるいるいるか
いるかいるいるいるか
か
かいないかいないかいるかいるいるいるか
かいないかいるかいるいるいるか
かいるいるいるか
かいるかいるいるいるか
ないかいないかいるかいるいるいるか
ないかいるかいるいるいるか
るいるいるか
るいるか
るか
るかいないかいないかいるかいるいるいるか
33
るかいるいるいるか
• P に対応する接尾辞配列の区間 [s,t] が求まっ
たら，P の出現位置を求めるのは容易
• P の出現回数 occ に比例した時間で列挙できる
• 検索全体の時間計算量は O(m log n + occ)
34
索引のサイズと検索時間
サイズ
転置ファイル
接尾辞配列
接尾辞木
< n bytes
頻度問い合わせ時間
O(m)
4n bytes + |T|
O(m log n)
>10n bytes + |T|
O(m)
注: 転置ファイルは文書が単語に分かれている場合
35
接尾辞配列の構築アルゴリズム
• 一番簡単な方法
– クイックソートを用いて n 個の接尾辞をソート
– 整数の比較ではなく，文字列の比較に変更
– 1回の文字列比較が O(n) 時間なので，全体で
(平均) O(n2 log n) 時間
• O(n log n) 時間や O(n) 時間のアルゴリズムも
存在するが，やや複雑
– 参考:
http://homepage3.nifty.com/DO/suffix_array.htm
http://www.cs.sysu.edu.cn/nong/
36
文字列の辞書順
• 接尾辞 Ti = T[i] T[i+1]...T[n] = T[i..n]
• Ti < Tj とは
– T[i] < T[j] または
– T[i] = T[j] かつ Ti+1 < Tj+1
37
圧縮接尾辞配列 (CSA)
• SA の代わりに [i] = SA-1[SA[i]+1] を格納
• サイズ: O(n log |A|) bits
 i SA
• パタン P の検索: O(|P| log n) time 0 1 7 $
5 2 1 ababac$
6 3 3 abac$
7 4 5 ac$
3 5 2 babac$
4 6 4 bac$
1 7 6 c$ 38
なぜ圧縮できるのか
• 接尾辞は辞書順に
格納される
• 先頭の1文字を消し
ても辞書順は同じ
 SA
12
14
15
16
17
18
19
20
21
0
3
4
5
9
1
2
6
7
10
11
13
6
10
4
8
15
17
19
1
12
21
3
7
14
11
5
9
16
18
20
2
13
いかいないかいるかいるいるいるか
いかいるかいるいるいるか
いないかいないかいるかいるいるいるか
いないかいるかいるいるいるか
いるいるいるか
いるいるか
いるか
いるかいないかいないかいるかいるいるいるか
いるかいるいるいるか
か
かいないかいないかいるかいるいるいるか
かいないかいるかいるいるいるか
かいるいるいるか
かいるかいるいるいるか
ないかいないかいるかいるいるいるか
ないかいるかいるいるいるか
るいるいるか
るいるか
るか
るかいないかいないかいるかいるいるいるか
るかいるいるいるか
39
CSA の性質
• i < j のとき T[SA[i]]  T[SA[j]]
• i < j かつ T[SA[i]] = T[SA[j]] のとき 
0
[i] < [j]
証明：T[SA[i]] = T[SA[j]] のとき, この 5
6
接尾辞の辞書順は2文字目以降で
7
決まる.
3
i < j より T[SA[i]+1..n] < T[SA[j]+1..n]
4
SA[i’] = SA[i]+1, SA[j’] = SA[j]+1 とす 1
ると, i’ < j’
つまり i’ =SA-1[SA[i]+1]=[i]<[j]=j’
i SA
1
2
3
4
5
6
7
7$
1 ababac$
3 abac$
5 ac$
2 babac$
4 bac$
6 c$
40
の符号化法
• ’[i] = T[SA[i]]  n + [i] を格納
– [i] = ’[i] mod n
– T[SA[i]] = ’[i] div n
• ’[i] (i = 1,2,...,n) は単調増加列になる
– n(2+log )
$: 2
a: 5, 8, 9
c: 3, 4
g: 1, 6, 7
$: 000010
a: 010101, 011000, 011001
c: 100011, 100100
g: 110001, 110110, 110111
41
’の符号化法
• ’[i] の2進表現の上位 log n ビット
– 直前の値からの差分を1進数で符号化
– 最大 2n ビット (1の数 = n，0の数  n)
• ’[i] の下位 log  ビットはそのまま格納
– n log  bits
$: 2
a: 5, 8, 9
c: 3, 4
g: 1, 6, 7
$: 000010
a: 010101, 011000, 011001
c: 100011, 100100
g: 110001, 110110, 110111
1, 000001, 01, 1, 001, 01, 0001, 01, 1
10, 01, 00, 01, 11, 00, 01, 10, 11 42
’の復号
• 上位桁： x = select(H,i)  i
• 下位桁： y = L[i]
• ’[i] = x   + y
• 時間計算量： O(1)
• 領域計算量： n(2+log ) + O(n log log n/log n)
$: 2
a: 5, 8, 9
c: 3, 4
g: 1, 6, 7
H: 1, 000001, 01, 1, 001, 01, 0001, 01, 1
L: 10, 01, 00, 01, 11, 00, 01, 10, 11 43
の圧縮
• [i] を T[SA[i]] で分割
S c   i | T [SA[i]]  c, nc  S (c)
• 各 S(c) を符号化： nc  2  log n   bits


n
c 


• 全体で



n
c nc  2  log n    nH 0  3
c 


1
H 0   pc log
pc
c A
nc
( pc  :文字 c の出現確率)
n
• H0  log  (等号は p1 = p2 = … のとき)
1
1
H 0   pc log
 log  pc
 log 
pc
pc
c A
c A
44
要素 SA[i]のアクセス方法
• i が log n の倍数のときに
SA[i] を格納
• k = 0; w = log n;
• while (i % w != 0)
– i = [i]; k++;
SA2
• return SA2[i / w] - k;
08
13
24
アクセス時間: 平均 O(log n) 時間
n=8
w=3
 i SA
0 8
0 1 7$
5 2 1 ababac$
6 3 3 abac$
7 4 5 ac$
3 5 2 babac$
4 6 4 bac$
1 7 6 c$ 45
1
[i]  SA [SA[i]  1]
• B[i]=1  SA[i] が log n の倍数
• SA[i]が log n の倍数のものを SA2 に格納
10
B
T
SA
8
9 11 13 15
1
2
1 0 0
E B D
8
14
3
0
E
5
1
6
4
5
1 1 0
B D D
6
0
A
2
12
7 12 14 16
7
8
0
D
16
0
D
7
SA2
0
E
15
2
k = 0; w = log n;
while (B[i] == 0)
i = [i]; k++;
return SA2[rank (B,i)]w  k;
3
2
3
4
5
9 10 11 12 13
0 0 1 0 0
B E B D C
6
4
9
3
10
13
14
15
16
4
1
11
1
B : n+o(n) ビット
アクセス時間: O(log n) 時間
46
の階層的表現
• レベル i では
– T 中の連続する 2i 文字を1つの文字とみなす
– 文字列のエントロピーは増えない
B 1 1 0
T E B D
SA 8 14
1
E
5
1
B
1
D
2
12
0
D
0
A
16
SA1
BD
4
EB
7
SA2
BDEB
2
1
D
0
D
7
DD
1
15
AD
6
DDAD
3
0
E
1
B
0
E
6
DE
8
1
B
9
BE
3
DEBE
4
0
D
3
BD
5
BDC$
1
0
C
10
13
4
1
C$
2
47
11
データ構造のサイズ
レベル数が 1/ のとき
• : 1/  n(3+H0) bits
• SA1/ : n/log n  log n = n bits
• B:  n + n/2 + n/4 + ...  2n bits
n



O
H
1
合計:   0  bits
SA[i] の計算: O 1 log 


n

時間
48
部分文字列の検索
二分探索時に実際のSAの値は必要ない
T

E
1
10
B
2
8
r 1 2
D 1 1
SA 8 14
A B
D D
C
1 2
C A B
D E B D
3 4 5 6
9 11 13 15
D
7
1
2
0
5
B
D
D
4 4
1 0
7 15
D D
A C
2 2 3
0 0 1
2 12 16
B B C
D E
E
3 4 5
C D E
A
8
6
D D E B E B D C
9 10 11 12 13 14 15 16
7 12 14 16 2 3 4 5
4
0
6
D
D
A
4
0
9
D
D
E
4 4 5
0 0 1
3 10 13
D D E
E E B
B B D
D E C
5
0
4
E
B
D
D
5 5
0 0
1 11
E E
B B
D E
E
49
後方検索
C[$]=[1,1]
C[a]=[2,4]
C[b]=[5,6]
C[c]=[7,7]
P=P[1..p] の検索
l  1; r  n
for (k = p; k >=1; k--)
l  arg min [ j ]  l
jC [ P[ k ]]
r  arg max [ j ]  r
jC [ P[ k ]]
O(p log n) time

0
5
6
7
3
4
1
i SA
1
2
3
4
5
6
7
7$
1 ababac$
3 abac$
5 ac$
2 babac$
4 bac$
6 c$ 50
l  arg min [ j ]  l
jC [ P[ k ]]
r  arg max [ j ]  r
jC [ P[ k ]]
• の値で二分探索: O(log n) time
• P の検索に O(|P| log n) time
51
テキストの部分的な復元
T[9..13] = DDEBEを復元する場合
1. i=SA-1[9]=10 を求める
2. 辞書順で i 番目の接尾辞の先頭の文字を求める
1 2 3
3. i=10からをたどる
C A B C
1
T E
A
 10
2
B
B
8
1 2
SA 8 14
3
D
B
4
E
B
5
B
B
6
D
C
9 11 13 15
3 4 5 6
5 2 12 16
7
D
D
4
D
5
E
8
A
D
9 10 11 12 13 14 15 16
D D E B E B D C
D D D D E E E E
1 6
7 8
7 15
7 12 14 16 2 3 4 5
9 10 11 12 13 14 15 16
6 9 3 10 13 4 1 11
52
圧縮接尾辞配列の機能
•
•
•
•
lookup(i): SA[i] を返す (O(log n) 時間)
inverse(i): SA-1[i] を返す (O(log n) 時間)
[i]: SA-1[SA[i]+1] を返す(O(1) 時間)
substring(i,l): T[SA[i]..SA[i]+l-1]を返す
– O(l) 時間
– (i からT[SA[i] は長さ n のベクトルのrankで求まる)
53

Download Report