簡潔4 - Researchmap

簡潔データ構造
国立情報学研究所
定兼邦彦
目次
0. 基礎
1. ビットベクトル
2. 木構造1
3. 木構造2
4. 接尾辞配列
5. 接尾辞木
6. 動的なデータ構造
7. 配列
2
4. 接尾辞配列
3
文字列用の標準的データ構造
• 操作
– パタンの出現回数，場所
– 共通部分文字列，極大パタン
– アラインメント
• 代表的データ構造
– 接尾辞木 [1,2]
– 接尾辞配列 [3]
• サイズ：文字列 + O(n log n) bits
– ヒトのDNA配列：30億文字 (750MB)
– 接尾辞木：40GB
4
接尾辞 (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
5
接尾辞配列 [3]
• 接尾辞のポインタを
辞書順にソートした配列
• サイズ
n log n + n log |A| bits
• パタン P の検索
O(|P| log n) time
SA
6
10
4
8
15
17
19
1
12
21
3
7
14
11
5
9
16
18
20
2
13
いかいないかいるかいるいるいるか
いかいるかいるいるいるか
いないかいないかいるかいるいるいるか
いないかいるかいるいるいるか
いるいるいるか
いるいるか
いるか
いるかいないかいないかいるかいるいるいるか
いるかいるいるいるか
か
かいないかいないかいるかいるいるいるか
かいないかいるかいるいるいるか
かいるいるいるか
かいるかいるいるいるか
ないかいないかいるかいるいるいるか
ないかいるかいるいるいるか
るいるいるか
るいるか
るか
るかいないかいないかいるかいるいるいるか
るかいるいるいるか
6
圧縮接尾辞配列 (CSA) [4,5]
• 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$ 7
の計算法
1. 接尾辞配列 SA を作る
2. i を (T[SA[i]-1], i) の順に基数ソート
1. T中の各文字の頻度を数える  i SA
0 1 7$
2. i=1,2,...,n に対し,
c=T[SA[i]-1] を求める
5 2 1 ababac$
6 3 3 abac$
3. で c に対応する範囲に
7 4 5 ac$
i を書く
3 5 2 babac$
4 6 4 bac$
1 7 6 c$ 8
なぜ圧縮できるのか
• 接尾辞は辞書順に
格納される
• 先頭の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
いかいないかいるかいるいるいるか
いかいるかいるいるいるか
いないかいないかいるかいるいるいるか
いないかいるかいるいるいるか
いるいるいるか
いるいるか
いるか
いるかいないかいないかいるかいるいるいるか
いるかいるいるいるか
か
かいないかいないかいるかいるいるいるか
かいないかいるかいるいるいるか
かいるいるいるか
かいるかいるいるいるか
ないかいないかいるかいるいるいるか
ないかいるかいるいるいるか
るいるいるか
るいるか
るか
るかいないかいないかいるかいるいるいるか
るかいるいるいるか
9
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$
10
の符号化法
• ’[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
11
’の符号化法
• ’[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 12
’の復号
• 上位桁： 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 13
の圧縮
• [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
14
要素 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$
15
1
[i]  SA [SA[i]  1]
• B[i]=1  SA[i] が log n の倍数
• SA[i]が log n の倍数のものを SA2 に格納
 10
1
B 1
T E
SA 8
8
2
0
B
14
9 11 13 15
3 4 5 6
0 0 1 1
D E B D
5 2 12 16
1 6
7 8
0 0
D A
7 15
7 12 14 16 2 3 4 5
9 10 11 12 13 14 15 16
0 0 0 0 0 1 0 0
D D E B E B D C
6 9 3 10 13 4 1 11
SA2 2 3 4 1
k = 0; w = log n;
while (B[i] != 0)
i = [i]; k++;
return SA2[rank (B,i)]w  k;
B : n+o(n) ビット
アクセス時間: O(log n) 時間
16
の階層的表現
• レベル i では
– T 中の連続する 2i 文字を1つの文字とみなす
– 文字列のエントロピーは増えない
B 1 1
T E B
SA 8 14
0
D
5
1 1 1
E B D
2 12 16
0 0
D A
7 15
1
D
6
0
D
9
0 1 0
E B E
3 10 13
1
B
4
0 0
D C
1 11
BD EB DD AD DE BE BD C$
SA1 4 7 1 6 8 3 5 2
BDEB DDAD DEBE BDC$
2
3
4
1
SA2
17
データ構造のサイズ
レベル数が 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

時間
18
部分文字列の検索
二分探索時に実際の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
3
C
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
4 5
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
19
後方検索
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$ 20
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
21
テキストの部分的な復元
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
22
圧縮接尾辞配列の機能
•
•
•
•
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で求まる)
23
CSAの問題点
• サイズが n(H0(S)+O(1)) bits
• nHk(S)+o(n) にしたい
24
ブロックソート圧縮法
•
•
•
•
Burrows, Wheeler 1994 [6]
gzipよりも高圧縮率, PPM [7] に迫る
圧縮がPPMよりも高速
伸張はさらに高速
– データの配布に適する
25
ブロックソート圧縮法
ababac$
接尾辞ソート
BW変換
c$bbaaa
MTF変換
3441411
ハフマン符号
算術符号
δ符号 011
1
1
2
0 10
3
0 11
4
00 100
5
00 101
00100 00100 1 00100 1 1
26
接尾辞配列
T = acagcagg$
接尾辞配列
SA
1
2
3
4
5
6
7
8
9
acagcagg$
cagcagg$
agcagg$
gcagg$
cagg$
agg$
gg$
g$
$
辞書順に
ソート
9
1
3
6
2
5
8
4
7
$
acagcagg$
agcagg$
agg$
cagcagg$
cagg$
g$
gcagg$
gg$
27
BW変換
T = acagcagg$
• BW[i] = T[SA[i]1]
• ソートした各接尾辞の1つ
前の文字を並べたもの
• T の並び替えになる
• BWから T を復元可能
• BWは圧縮しやすい
BW = g$ccaggaa
SA
9
1
3
6
2
5
8
4
7
g$
$ acagcagg
c agcagg$
c agg$
a cagcagg$
g cagg$
g g$
a gcagg$
a gg$
28
逆BW変換
• T は BW から復元できる
• SA も復元できる [8]
g
$
c
c
a
g
g
a
a
$
acagcagg$
agcagg$
agg$
cagcagg$
cagg$
g$
gcagg$
gg$
29
FM-index [9]
BWだけでパタン検索が可能
1
2
3
4
5
6
7
8
9
g
$
c
c
a
g
g
a
a
$
a
a
a
c
c
g
g
g
P=P[1, p] を検索
c = P[p]
l = C[c]+1, r = C[c+1]
while (--p  0) {
c = P[p]
l = C[c]+rankc(BW,l1)+1
r = C[c]+rankc(BW,r)
}
[l,r] は P の辞書順
C
$: 0
a: 1
c: 4
g: 6
30
LF mapping
LF [i]  SA1[ SA[i]  1]
 C[c]  rank c ( BW , i)
LF[5]=C[a]+ranka(BW,5)
=1+1
=2
SA[5]=2
SA[2]=2-1
1つ前の接尾辞の辞書順を表す
C$abc
0146
(c  BW [i])
1
2
3
4
5
6
7
8
9
g
$
c
c
a
g
g
a
a
$
a
a
a
c
c
g
g
g
31
• BW をウェーブレット木で格納すれば，rankを
O(log /log log n) 時間で計算できる
• パタン検索が O(|P| log /log log n) 時間
• BWのサイズ: nH0(BW) + O(n log /log log n) bits
• lookup/inverseの索引を d 個おきにすると
– サイズ: O(n log n/d) bits
– 時間: O(d log /log log n)
• サイズを o(n) にするために d = log1+ n とする
32
文字列の高次圧縮
• BW変換後の文字列では，同じ文脈を持つ文字
が集まっている
文脈 = $ g $
• 各文脈ごとに H0 まで圧縮
$ acagcagg
⇒全体では Hk を達成
文脈 = a c agcagg$
c agg$
a cagcagg$
文脈 = c
g cagg$
g g$
文脈 = g a gcagg$
a gg$ 33
まとめ: FM-index
•
•
•
•
•
 = polylog(n) とする
索引サイズ: nHk(S) + o(n) bits
パタンの検索: O(|P|) time
lookup/inverse: O(log1+ n) time
長さ l の部分文字列の復元: O(l + log1+ n) time
34
CSAとFM-indexの関係
• 両者は同じものを表している
1
[i ]  SA [ SA[i ]  1]
LF [i ]  SA1[ SA[i ]  1]
[ LF [i ]]  LF [[i]]  i
• 片方でもう一方を模倣できる

$: 010000000 (2)
a: 000010011 (5, 8, 9)
c: 001100000 (3, 4)
g: 100001100 (1, 6, 7)
BW: g$ccaggaa
35
•
•
•
•
•
 は BW 上のselectで求まる
LF, BW は  回の  の後方探索で求まる
t:  を求める時間
tLF: LF を求める時間
ts: BW でのselectを求める時間
t   t s  O(log  )
t LF  O log n 
36
参考文献
[1] P. Weiner. Linear Pattern Matching Algorithms. In Proceedings of the
14th IEEE Symposium on Switching and Automata Theory, pages 1–
11, 1973.
[2] E. M. McCreight. A Space-economical Suffix Tree Construction
Algorithm. Journal of the ACM, 23(12):262–272, 1976.
[3] Udi Manber, Gene Myers. Suffix arrays: a new method for on-line
string searches, Proc. SODA, 1990.
[4] R. Grossi and J. S. Vitter. Compressed Suffix Arrays and Suffix Trees
with Applications to Text Indexing and String Matching. SIAM
Journal on Computing, 35(2):378–407, 2005.
[5] Kunihiko Sadakane: New text indexing functionalities of the
compressed suffix arrays. J. Algorithms 48(2): 294-313 (2003).
[6] M. Burrows, D. Wheeler. A block sorting lossless data compression
algorithm, Technical Report 124, Digital Equipment Corporation,
37
1994.
[7] John G. Cleary, Ian H. Witten: A comparison of enumerative and
adaptive codes. IEEE Transactions on Information Theory 30(2): 306315 (1984)
[8] Kunihiko Sadakane: A Modified Burrows-Wheeler Transformation
for Case-Insensitive Search with Application to Suffix Array
Compression. Data Compression Conference 1999: 548
[9] P. Ferragina and G. Manzini. Indexing compressed texts. Journal of
the ACM, 52(4):552–581, 2005.
38

Download Report