ALG2014-13

算法数理工学
第13回
定兼邦彦
文字列検索
• 情報検索で必須の処理
– サーチエンジン
– ゲノム情報処理
• データ量が莫大
– Web: >20億ページ, 数テラバイト
– DNA配列: ヒト=28億文字, 総計>150億文字
2
文字列検索問題
• 文字列 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 の部分文字列となっている場所, つまり
3
P = T[i..j] となる i を全て見つける問題
文字列検索アルゴリズム
• 逐次検索
– P と T が与えられてから問題を解く
– 絶対に O(|P|+|T|) 時間かかる
– KMP法，BM法，Z法など
• 索引検索
– T が予め与えられたとき，何らかのデータ構造 D を
作っておく．P が与えられたときに D を用いて問題
を高速に解く
– 転置ファイル，接尾辞木，接尾辞配列など
4
逐次検索アルゴリズム
• 文字列マッチングを簡単に解こうと思ったら,
各 i について P = T[i..i+|P|1] となるかどうかを
調べればよい
• O( |T|  |P| ) 時間のアルゴリズムができる
• もう一工夫して速くする方法を考える
• Z アルゴリズム
– 最も単純な線形時間 (O(|T|+|P|)) アルゴリズム
5
• 定義: 文字列 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
6
• 定義: 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|) 時間で計算したい
7
• 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
8
• 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
q
9
定理: 全ての Zi は O(|S|) 時間で求まる
証明: ループの回数は |S| 回．
文字列の比較は必ずミスマッチで終わる
⇒ミスマッチの回数はループの回数以下
マッチの回数を見積もる．
1回の文字列比較で q 文字マッチしたとすると，
r は少なくとも q 増加する．また，r は減少しない．
r  |S| よりマッチの回数は |S| 以下．
10
Z アルゴリズム
• S = P$T とする．(|P|  |T| とする)
– $ は P, T に現れない文字
• Zi(S) を計算する
– O(|P|+|S|) 時間
• Zi(S) = |P| ならば P は S の部分文字列
i は必ず T の中になる (P は $ を含まないから)
⇒ P は T の部分文字列
• そのままだと O(|P|+|S|) 領域だが，O(|P|) にできる
– Zi(S)  |P| なので，参照される Zi はO(|P|)領域で格納可
11
索引検索
• Web検索のように，決まった文字列に対して
何度も検索を行う場合は，索引検索の方が高速
• 単語索引
– 決まった単語のみを検索できる
– 索引のサイズが小さい
– 転置ファイル
• 全文検索
– 任意の部分文字列を検索できる
– 索引が大きくなる
– 接尾辞木，接尾辞配列
12
転置ファイル
• 文字列を単語(形態素)に分解
• 単語ごとに出現位置(出現文書)を列挙
• 出現回数も記憶
1
4
8
12
15
19
いるかいないかいないかいるかいるいるいるか
T = いるか|いないか|いないか|いるか|いるいる|いるか
いるか: 3回 (1, 12, 19)
いないか: 2回 (4, 8)
いるいる: 1回 (15)
13
文字列検索の問題点
• 任意の文字列を検索したい
• 部分文字列の数 = nC2 = O(n2)
• 全ての部分文字列を索引に格納
⇒索引サイズ: O(n2)
14
接尾辞 (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
15
接尾辞木 [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
いかいないかいるかいるいるいるか
いかいるかいるいるいるか
いないかいないかいるかいるいるいるか
いないかいるかいるいるいるか
いるいるいるか
いるいるか
いるか
いるかいないかいないかいるかいるいるいるか
いるかいるいるいるか
か
かいないかいないかいるかいるいるいるか
かいないかいるかいるいるいるか
かいるいるいるか
かいるかいるいるいるか
ないかいないかいるかいるいるいるか
ないかいるかいるいるいるか
るいるいるか
るいるか
るか
るかいないかいないかいるかいるいるいるか
16
るかいるいるいるか
接尾辞配列 [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
いかいないかいるかいるいるいるか
いかいるかいるいるいるか
いないかいないかいるかいるいるいるか
いないかいるかいるいるいるか
いるいるいるか
いるいるか
いるか
いるかいないかいないかいるかいるいるいるか
いるかいるいるいるか
か
かいないかいないかいるかいるいるいるか
かいないかいるかいるいるいるか
かいるいるいるか
かいるかいるいるいるか
ないかいないかいるかいるいるいるか
ないかいるかいるいるいるか
るいるいるか
るいるか
るか
るかいないかいないかいるかいるいるいるか
17
るかいるいるいるか
接尾辞配列を用いた文字列検索
•
•
•
•
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 回繰り返す
18
• O(m log n) 時間
接尾辞配列を用いた検索
• 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
いかいないかいるかいるいるいるか
いかいるかいるいるいるか
いないかいないかいるかいるいるいるか
いないかいるかいるいるいるか
いるいるいるか
いるいるか
いるか
いるかいないかいないかいるかいるいるいるか
いるかいるいるいるか
か
かいないかいないかいるかいるいるいるか
かいないかいるかいるいるいるか
かいるいるいるか
かいるかいるいるいるか
ないかいないかいるかいるいるいるか
ないかいるかいるいるいるか
るいるいるか
るいるか
るか
るかいないかいないかいるかいるいるいるか
19
るかいるいるいるか
• P に対応する接尾辞配列の区間 [s,t] が求まっ
たら，P の出現位置を求めるのは容易
• P の出現回数 occ に比例した時間で列挙できる
• 検索全体の時間計算量は O(m log n + occ)
20
索引のサイズと検索時間
サイズ
転置ファイル
接尾辞配列
接尾辞木
< n bytes
頻度問い合わせ時間
O(m)
4n bytes + |T|
O(m log n)
>10n bytes + |T|
O(m)
注: 転置ファイルは文書が単語に分かれている場合
21
接尾辞配列の構築アルゴリズム
• 一番簡単な方法
– クイックソートを用いて 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/
22
文字列の辞書順
• 接尾辞 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
23
圧縮接尾辞配列 (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$ 24
なぜ圧縮できるのか
• 接尾辞は辞書順に
格納される
• 先頭の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
いかいないかいるかいるいるいるか
いかいるかいるいるいるか
いないかいないかいるかいるいるいるか
いないかいるかいるいるいるか
いるいるいるか
いるいるか
いるか
いるかいないかいないかいるかいるいるいるか
いるかいるいるいるか
か
かいないかいないかいるかいるいるいるか
かいないかいるかいるいるいるか
かいるいるいるか
かいるかいるいるいるか
ないかいないかいるかいるいるいるか
ないかいるかいるいるいるか
るいるいるか
るいるか
るか
るかいないかいないかいるかいるいるいるか
るかいるいるいるか
25
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$
26
の符号化法
• ’[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
27
’の符号化法
• ’[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 28
’の復号
• 上位桁： 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 29
の圧縮
• [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
30
要素 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$ 31
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) 時間
32
の階層的表現
• レベル 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
33
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

時間
34
部分文字列の検索
二分探索時に実際の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
35
後方検索
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$ 36
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
37
テキストの部分的な復元
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
38
圧縮接尾辞配列の機能
•
•
•
•
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で求まる)
39

Download Report