簡潔5 - Researchmap

簡潔データ構造
国立情報学研究所
定兼邦彦
目次
0. 基礎
1. ビットベクトル
2. 木構造1
3. 木構造2
4. 接尾辞配列
5. 接尾辞木
6. 動的なデータ構造
7. 配列
2
5. 接尾辞木
3
接尾辞木 [1,2]
0
$
•
•
•
•
•
•
枝のラベル
ノードの深さ
葉の添え字
子ノードへのポインタ
Suffix link
文字列 T
a
2
3
b
6
c
b
a
1
a
1
7
c
b
b
c
2
4
5
c
3
1234567
ababac$
4
接尾辞木での操作
1. root(): 根ノードを返す
2. isleaf(v): v が葉なら Yes を返す
3. child(v,c): v の子 w を返す (vw 間の枝ラベルは
文字 c から始まる)
4. firstchild(v): v の最初の子を返す
5. sibling(v): v の次の弟を返す
6. parent(v): v の親を返す
5
7. edge(v,d): v への枝のラベルの d 文字目を返す
8. depth(v): v の文字列深さを返す
9. lca(v,w): v, w のlowest common ancestorを返す
10. sl(v): v のsuffix linkで指されているノードを返す
0
$
a
a
1
7
6
c
b
a
2
3
b
1
c
b
b
c
2
4
5
c
3
6
接尾辞木の構成要素 [3]
1.
2.
3.
4.
5.
テキスト: n lg |A| bits
木構造: O(n lg n) bits
ノードの文字列深さ: n lg n bits
枝ラベル: n lg n bits
suffix link: n lg n bits
7
木構造の表現
• 木をBP列で表現
1
– 内部節点: (...)n-1 個
– 葉:() n 個
7
3
• 最大 4n+o(n) bits
• ノードは( の位置で表現
6
5
2
5
2
4
1 3
1 7 3 2 1 3
5
5 2
4
6
(()((()())())(()())())
8
ノードの表現
1. v: 括弧列中の( の位置
2. j: ノードの preorder
•
•
j = rank((P,v)
v = select((P,j)
3. i: ノードの inorder
1
preorder
3
2
4
5 6
11 1 2 3 4 5 6
8
7
7
8 9 10
11
(()((()())())(()())())
9
10
9
ノードの inorder
• 内部ノードのみに定義
• 根から深さ優先探索を行ったときに v を下から
訪れるまでの内部ノードの数
• 1つの内部ノードが複数のinorderを持つ
(子が3つ以上の場合)
146
3
x
2
x x
x
5
x
x
x
10
inorder の計算
• v とその最小のinorder i は定数時間で変換可
– i = rank()(P,findclose(P,v+1))
– v = enclose(P,select)( (P,i)+1)
146
3
x
2
x x
x
5
x
x
x
1 7 3 2 1 3
5
5 2
4
6
(()((()())())(()())())
v
11
証明: i = rank()(P,findclose(P,v+1))
v+1 は v の最初の子 w
u = findclose(P,v+1) は w を根とする部分木の最
後の位置
inorder は葉から葉へのパス上で1回定義される．
よって葉と inorder には1対1対応がある．
inorder の値は根から v までの巡回中の葉の数．
146
つまり i = rank()(P,u)
3 v
x
w2
v w
u
(()((()())())(()())())
x x
x
5
x
x
x
12
証明: v = enclose(P,select)( (P,i)+1)
i は深さ優先探索において，下からノード w を訪れ次
に w の別の子を訪れた回数である．
この動作は P 中では「)(」で表される．
x = select)( (P,i)+1 は v の子を表す．
146
3 v
x
2
v
x
(()((()())())(()())())
x x
x
5
x
x
x
13
ノードの文字列深さ
0
$
a
a
1
7
6
c
b
a
2
3
b
c
2
4
5
b
c
1
Hgt 0
c
b
ababac$
3
3
1
0
2
0
0
文字列深さは隣り合ったleaf間の共通接頭辞の長さ(Hgt)で表せる
14
Hgt 配列
• Hgt[i]= lcp(SA[i], SA[i+1])
• サイズ: n log n bits
Hgt SA
0 7 $
3 1 ababac$
1 3 abac$
0 5 ac$
2 2 babac$
0 4 bac$
0 6 c$
15
14 6
Hgt[i]は inorder で
i 番目の内部ノード
の深さに等しい
$
a
a
7
6
3
c
b
a
5
2
内部ノードと葉に1対1対応
が存在し定数時間で求まる b
c
i = rank()(findclose(v+1))
1
Hgt 0
depth(v) = Hgt[i]
c
b
b
c
2
4
5
3
3
1 7 3 2 1
1
3
0
5
2
5 2 4
0
0
6
(()((()())())(()())())
16
枝ラベルの計算
•
•
•
•
ノード v の inorder を i とする
i 番目の葉は v の子孫
i 番目の葉は SA[i] を表す
d1
v に入る枝は SA[i] の部分文字列
i  inorder (v)
d1  Hgt[inorder ( parent (v))]
d 2  Hgt[i]
edge(v, d )  T [SA[i]  d1  d 1]
枝の長さ = d2  d1
parent(v)
b
a
d
c
d2
v
SA[i]
17
Hgt 配列の圧縮
• i と SA[i] が与えられたとき, Hgt[i]は 2n +o(n)
bits の索引を用いて定数時間で求まる
18
Hgt 配列の並び替え
Hgt[i]= lcp(SA[i], SA[i+1])
Hgt
0
3
1
0
2
0
0
SA
7
1
3
5
2
4
6
SA+Hgt 7
4
4
5
4
4
6
1
2
3
4
5
6
7
SA+Hgt 4
4
4
4
5
6
7
SA
SA+Hgt の値はSAに従ってソートすると単調
[1,n]の範囲の長さ n の単調な数列は 2n bitsで表せる
00001 1
1
1
01
01 01
19
補題: SA[i]=p, SA[j]=p+1 とすると
Hgt[j]  Hgt[i]  1
Hgt
SA
p
q
ababac$
abac$
i
d
j
d-1 p+1 babac$
d-1
q+1 bac$
bab..
q+1 bac$
Hgt[SA-1[p+1]]  Hgt[SA-1[p]]-1
20
1
1  Hgt [ SA [1]]  1
1
 Hgt [ SA [2]]  2
1
 Hgt [ SA [ p]]  p
1
 Hgt [ SA [n]]  n
 0n  n
Hgt[SA-1[k]]+k (k = 1,2,...,n) は単調増加で
[1, n] の範囲に収まる
21
Hgt[i] の計算法
• k = SA[i] を求める
– 接尾辞配列で定数時間
– 圧縮接尾辞配列で O(log n) 時間 (0<<2)
• 単調増加列の k 番目の要素 v を復号
– selectで定数時間
• Hgt[i] = v - k
22
lcaの計算
• lca = lowest common ancestor
• u = lca(v,w): v と w の共通の祖先
で最も根から遠いもの
• 定数時間で計算可
u
v
w
23
• E[i] = rank((P,i)  rank)(P,i) とすると
u = parent(RMQE(v,w)+1)
m = RMQE(v,w): E[v..w] 中の最小値の添字
(RMQ = Range Minimum Query)
u
146
w5
3
7
v2
1 3
5
2
6
4
1 7 3 2 1 3
5
5 2
4
6
P (()((()())())(()())())
E 1212343432321232321210
u
v
mw
24
Suffix linkの表現
• sl(node(c)) = node()
• 圧縮接尾辞配列の関数
を用いる
x  rank () ( P, v  1)  1

w
b
c
c

sl(v)
v
b
x’ 3
y’ 6
y  rank () ( P, findclose ( P, v))
x  [ x]
y  [ y ]
w  lca ( select () ( P, x), select () ( P, y))
c
2 x
5 y


25
証明: 葉は () で表され，対応する接尾辞の辞書順に
P 中に現れる．よって
x = rank()(P,v1)+1 は v の子孫の葉で最も辞書順の
小さいもの
y = rank()(P,findclose(P,v)) は v の子孫の葉で最も
辞書順の大きいもの
x, y は接尾辞 T[SA[x]..n], T[SA[y]..n] を表す．
x’, y’ は接尾辞 T[SA[x]+1..n], T[SA[y]+1..n] を表す．
26
• x は最左葉，y は最右葉
• l = lcp(x,y) とすると，l は v の文字列深さと等しい
• lcp(x’,y’) = l1 となる
• lca(x’,y’) は v より1つ短い文字列を表す v
つまり sl(v)
x SA[x]
y SA[y]
27
子ノードへの移動
w = child(v,c): v の子ノード w で文字 c から始まる
枝ラベルを持つもの
1. v の子ノードを列挙する場合
•
•
firstchildとsiblingを用いて子ノード u を列挙
edge(u,1) = c である u を探す
2. v の子を2分探索
•
v の i 番目の子を求める演算を用いる
3. SAの2分探索を用いる場合
•
•
v の最左葉と最右葉の辞書順 l, r を求める
SA[l..r] を d +1 文字目で2分探索 (d = depth(v))
28
圧縮接尾辞木のデータ構造
• 以下の要素から成る
– 圧縮接尾辞配列: |CSA|
– 接尾辞木の括弧列: 4n+o(n) bits
– Hgt配列: 2n+o(n) bits
• 圧縮接尾辞木のサイズは |CSA|+6n+o(n) bits
29
各操作の計算量
•
•
•
•
root, isleaf, firstchild, sibling, parent, lca: 定数時間
depth, edge: O(tSA) 時間
sl: O(t) 時間
child: O(tSA log |A|) 時間
• tSA: SA[i] を計算する時間
• t: [i] を計算する時間
30
参考文献
[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] Kunihiko Sadakane: Compressed Suffix Trees with Full Functionality.
Theory Comput. Syst. 41(4): 589-607 (2007)
31

Download Report