簡潔2 - Researchmap

簡潔データ構造
国立情報学研究所
定兼邦彦
目次
0. 基礎
1. ビットベクトル
2. 木構造1
3. 木構造2
4. 接尾辞配列
5. 接尾辞木
6. 動的なデータ構造
7. 配列
2
2. 木構造の簡潔データ構造
• 根付き木のみ扱う
• 順序木/非順序木
– 子ノード間に順序がある/ない
– 非順序木では，子を並び替えて同じになる木は
同一の木とみなす
• 枝にラベルがある/ない
– ノードのラベルは，その親への枝のラベルで代用
3
順序木とは
•
•
•
•
ordered tree / ordinal tree
根付き木
子に順序がついている
ラベルなし
– 枝ラベル→cardinal tree
1
2
3
4
6
5
7
8
4
順序木の簡潔表現
• LOUDS (level order unary degree sequence)
• BP (balanced parentheses)
• DFUDS (depth first unary degree sequence)
5
LOUDS表現 [1,2]
• 節点の次数を幅優先順に1進数で符号化
– 次数 d → 1d0
• n 節点で 2n+1 bits (下限に一致)
1  2n  1

  2n  log n  bits
log
2n  1  n  1 
1
• i 番目の節点は i 番目の
1 で表す
2
4
5
1
LOUDS
L
2 3
4 5 6
3
6
7
8
7 8
10110111011000000
6
木の巡回操作 (1)
• i 番目のノード: select1(L, i)
• firstchild(x)
(i  1)
– y := select0(rank1(L,x))+1
– if L[y] = 0 then 1 else y
1
• lastchild(x)
– y := select0(rank1(L,x)+1)1
– if L[y] = 0 then 1 else y
4
1
LOUDS
L
2 3
2
3
5
4 5 6
6
7
8
7 8
10110111011000000
7
木の巡回操作 (2)
• sibling(x)
– if L[x+1] = 0 then 1 else x+1
•
•
•
•
parent(x) = select1(rank0(L,x))
degree(x) = lastchild(x)  firstchild(x) + 1
長所: rank/selectだけで求まる
短所: 部分木のサイズが求まらない 1
2
4
1
LOUDS
L
2 3
4 5 6
5
3
6
7
8
7 8
10110111011000000
8
BP表現 [3]
• 各節点を対応する括弧のペアで表現
• n 節点で 2n bits
• サイズの下限と一致
1
2
3
6
4
5
7
8
1
2
6
3
BP
P
4
5
7
8
((()()())(()()))
9
BPでの基本操作
• ノードは( の位置で表す
• findclose(P,i): P[i] の( と対応する )の位置を返す
• enclose(P,i): P[i] の( を囲む括弧の位置を返す
enclose
1
3
2
4
5 6
11
8
7
9
findclose
1 2 3 4 5 6
7
8 9 10
11
P(()((()())())(()())())
10
10
木の巡回操作
•
•
•
•
parent(v) = enclose(P,v)
firstchild(v) = v + 1
sibling(v) = findclose(P,v) + 1
lastchild(v) = findopen(P, findclose(P,v)1)
1
enclose
3
2
4
5 6
11
8
7
9
findclose
1 2 3 4 5 6
7
8 9 10
11
(()((()())())(()())())
10
11
子孫の数 (部分木の大きさ)
• v を根とする部分木の大きさは
subtreesize(v) = (findclose(P,v)v+1)/2
• degree (子の数) は findclose の繰り返しで求まるが
子の数に比例する時間がかかる
1
3
2
4
5 6
11
8
7
9
1 2 3 4 5 6
7
8 9 10
11
P (()((()())())(()())())
10
12
findcloseのデータ構造 [4]
• 括弧列を長さ B = ½ log n のブロックに分割
– b(p): p のブロックの番号
– (p): p とマッチする括弧の位置
– 括弧 p が far ⇔ b(p)  b((p))
• far 開括弧 p が opening pioneer
⇔ p の直前の far 開括弧 q に対し b((p))  b((q))
• opening pioneerと対応する括弧の位置を0,1ベクト
ルで表現
r
(
q p
( (
(p) (q) (r)
)
)
)
13
補題: ブロックの数を  とすると，opening
pioneerの数は 23 以下．
証明: 各ブロックをノード，(b(p), b((p)) を枝
とするグラフは外平面グラフ
opening/closing pioneerは再びBPになる
 = n/B = 2n/log n ⇒ BPの長さは O(n/log n)
14
再帰構造の表現
• opening pioneerと対応する括弧の位置を
0,1ベクトル B で表現
  p  select B, findcloseP1, rank B, p
• B は長さ 2n, 1の数 O(n/log n) の疎なベクトル
– O(n log log n/log n) bits で表現できる
P
r
(
(p) (q) (r)
q p
( (
)
)
)
B 0100 0101 0000 0000 0010 1001
P1((()))
15
• n 節点の木のBP表現のサイズを S(n) とすると
– S(n) = 2n + O(n log log n/log n) + S(O(n/log n))
• 節点数が O(n/log2 n) になったら，答えを全部
格納しても O(n/log n) bits
• よって S(n) = 2n + O(n log log n/log n)
16
findcloseのアルゴリズム
•
•
•
•
•
•
(p) = findclose(P,p) を求めるとき
p が far でないなら (p) はテーブルから求まる
p の直前の pioneer p* を求める
pioneer の括弧列を用いて(p*) を求める
p が pioneer でないなら， b((p))  b((p*))
p と p* の深さの差から，(p) の位置が決まる
p* p
( (
(p) (p*)
)
)
17
enclose
• (p) = enclose(P,p) とする
• b((p)) = b(p) ならば (p) は表引きで求まる
• b((p))  b(p) ならばそれらの括弧の位置を記憶
– 対応する括弧の位置も記憶
– 括弧が複数ある場合は一番外側だけ記憶
• 括弧を抜き出して再帰
(
(
(()))(
)
)
)
18
BPでの基本操作2
• rankp(P,i): P[1..i] 中のパタン p の数を返す
• selectp(P,i): P 中の i 番目の p の位置を返す
• p の長さが定数なら，rank/selectは定数時間
1
3
2
4
5 6
11
8
7
9
10
1 2 3 4 5 6
7
8 9 10
11
P(()((()())())(()())())
rank()(P,10) = 3
19
葉に関する操作 [5]
• 葉はBP中の () で表される
• i 番目の葉の位置 = select()(P, i)
• 部分木中の葉の数，部分木中の最左葉，最右葉
も求まる
1
3
2
4
5 6
11
8
7
9
10
1 2 3 4 5 6
7
8 9 10
11
P(()((()())())(()())())
3 を根とする部分木
20
ノードの深さ
• 超過配列 E[i] = rank((P,i)  rank)(P,i) とすると
depth(v) = E[v]
• E は格納せず P と rank 計算用索引を格納
1
3
2
4
11
8
7
9
10
1 2 3 4 5 6
7
8 9 10
11
P (()((()())())(()())())
E 1212343432321232321210
5 6
21
最近共通祖先 (lca) の計算
• lca = lowest common ancestor
• u = lca(v,w): v と w の共通の祖先
で最も根から遠いもの
• 定数時間で計算可
u
v
w
22
• u = parent(RMQE(v,w)+1)
– E は超過配列. ノードの深さを表す
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
23
DFUDS表現 [6]
• ノードの次数を深さ優先順に1進数で符号化
• 次数 d ⇒ d 個の ( と 1つの )
• 先頭に(をつける
1
• 2n ビット
2
3
DFUDS
4
6
5
7
8
U ((()((())))(()))
1
2
3 4 5
6
7 8
24
補題: n ノードの順序木のDFUDSは長さ 2n のバランス
した括弧列になる
証明: n = 1 のとき，ルートは子を持たない (次数 0).
DFUDSは ().
ノード数が n1 以下のときに成り立つとする．
p 個の木に対するDFUDSを U1, U2,..., Up とする
(ノード数が合計 n1, DFUDSの長さの合計 2n2)
ルートがこれらの木を子に持つような木を考える.
その木に対するDFUDS U は
(( p )U1*U1* U *p
となる.
ルートの次数 p
先頭のダミー括弧
Ui の先頭のダミー
括弧を除いたもの
25
帰納法の仮定より，Ui はバランスしている.
先頭の括弧を取り除くため，( が1つ足りない.
Uの先頭のダミー括弧と，ルートに対応する括弧列
((p) では ( が p 個余っている.
よって U はバランスしている.
ノード数は n，括弧列の長さは 2n となり成り立つ.
p
*
1
*
1
(( )U U U
*
p
Ui の先頭のダミー
括弧を除いたもの
ルートの次数 p
先頭のダミー括弧
26
DFUDSでの各種操作
• ノード (次数d) は，その括弧列 (d) の先頭位置で
表現
– 括弧列での位置 v とノードの preorder i の変換は
v  preorder-select i   select ) i  1  1
i  preorder-rank v   rank ) v  1  1
• 次数:
degree(v)  select ) (rank ) (v)  1)  v
27
i-th child
child (v, i )  findclose select ) rank ) (v)  1  i   1
v
U1
U2 U3
(((()(())))((())))
v
1
2
6
5
3
4
7
8
9
28
Parent
parent (v)  select ) rank )  findopen(v  1)   1
p
2
5 6
(((()(())))((())))
1 p
2
6
5
3
4
7
8
9
29
子孫の数 (部分木の大きさ)
• v を根とする部分木の大きさは
subtreesize(v) = (findclose(enclose(v))v)/2+1
p
2
5 6
(((()(())))((())))
1 p
2
6
5
3
4
7
8
9
30
DFUDS上でのLCA [7]
• BP上とほぼ同じ演算でlcaを計算可
• lca(x,y) = parent(RMQE(x,y1)+1)
• 最小値は最左のものを使う
1
2
3
DFUDS
5
7
8
E 1232345432123210
U ((()((())))(()))
1
BP
4
6
P
E
2
3 4 5
6
7 8
((()()())(()()))
1232323212323210
31
E[i] = rank((U,i)  rank)(U,i) とする.
v の子の部分木を T1, T2,...,Tk,
v のDFUDSを U[l0..r0], E[r0] = d,
Ti のDFUDSを U[li..ri] とする.
命題: E[ri] = E[ri-1]1 = di (1  i  k)
E[j] > E[ri] (li  j < ri)
v
r0
r1 r 2
r3
U (((()(())))((())))
E 123434543212343210
d
2
1
v
6
5
3
4
7
8
932
証明: 各部分木のDFUDS U[li..ri] は先頭に
( をつけるとバランスする
⇒ E[ri] = E[ri-1]1 = di
E[j] > E[ri] (li  j < ri)
v
r0
r1 r 2
r3
U (((()(())))((())))
E 123434543212343210
d
2
1
v
6
5
3
4
7
8
33
9
補題: lca(x,y) = parent(RMQE(x,y1)+1)
証明: v = lca(x,y) とする．v の部分木 T1, T2,...,Tk で
x, y を含むものを T, T とする． E[r] = d とする．
Case 1: y < r (y がT の最右葉ではないとき)
E[y]  d+1, E[y1]  d+2 より RMQE(x,y1) = r1
T
E
T
d+1
> d+1
d
d1
34
Case 2: y = r のとき
E[y1] = d+1 より， RMQE(x,y1) は r1 と y1 で
最小値 d+1 をとる．
RMQでは最左のものをとるので r1 が求まる．
いずれの場合も RMQE(x,y1)+1 = l となり,
parent(l) = lca(x,y) となる．
35
その他の演算1
•
•
•
•
leaf-rank(v) = rank))(v)
leaf-select(i) = select))(i)
preorder-rank(v) = (rank)(v1))+1
preorder-select(i) = (select)(i1))+1
1
2
34 5 6
7 8 9
U (((()(())))((())))
E 123434543212343210
1
2
6
5
3
4
7
8
36
9
その他の演算2
•
•
•
•
inorder-rank(v) = leaf-rank(child(v,2)1)
inorder-select(i) = parent(leaf-select(i)+1)
leftmost-leaf(v) = leaf-select(leaf-rank(v1)+1)
rightmost-leaf(v) = findclose(enclose(v))
1
2
34 5 6
7 8 9
U (((()(())))((())))
E 123434543212343210
1
2
6
5
3
4
7
8
37
9
DFUDSの圧縮 [7]
• LOUDS, BP, DFUDS 表現は n ノードの順序木を
常に 2n bits で表現でき，下限と一致している
• しかし，順序木がある制約を満たすときは 2n より
少ないビット数で表現可能
– 例: 全ての内部ノードの次数が 2 であるような木は
n bits で表現可能
1
• サイズの下限は何か
2
3
5
4
6
7
1100100
1 2 3 4 5 6 7
38
サイズの(1つの)下限
• 次数 i のノード数が ni である順序木の数は
n

1

L  
n  n0 n1  nn1 
• サイズの下限
n
log L   ni log
ni
i
• 定義: 木次数エントロピー
ni
n
H T    log
ni
i n
*
• 目標: 順序木を nH*(T) bits に圧縮し，各種操作
39
を O(1) 時間で実現
定理長さ n の文字列(アルファベットサイズ)
⇒ nH k  Onk log   log log n  / log  n  ビット
任意箇所の log n ビットを定数時間で復元
• DFUDS列 U をこの方法で圧縮すると，U の
ビット列のエントロピーまで圧縮できる
• ただし，それは木次数エントロピーは関係ない
40
新しい表現
• S: 次数列 (c.f. DFUDSでは1進数で表現)
• S を圧縮して格納し，そこから U を復元
– U の任意位置の log n bitsを定数時間で復元できれば，
既存の索引がそのまま使える
•  = n なので，そのままだと圧縮できない
⇒S を次数が log n 以上とそれ以外に分割
DFUDS
U ((()((())))(()))
1
New
S
2
3 4 5
6
7 8
2 3 0 0 0 2 0 0
41
大きい次数の圧縮
• DFUDSでの符号の開始・終了位置を保存
• 次数が log n 以上の頂点は n/log n 個以下
⇒ O(n log log n/log n) ビットで表現できる
9
3
0 0 0 10
00
((((((((()((())))(((((((((()))
42
小さい次数の圧縮
•  = log n
2
⇒ nH 0 S   O nlog log n / log n
• nH0(S) = nH*(T)
• 2つの列を併合するのは簡単


– log n ビット内に大きい次数は高々2個
43
まとめ: 括弧列で行える木の操作
• 判定操作
– 葉かどうか，先祖/子孫関係
• 順序操作
– 前行順/後行順/中央順で i 番目の節点/葉
• 巡回操作
– 親，長男，次の弟，i 番目の弟, d 代上の祖先
– 最近共通祖先，深さ最大節点
• サイズに関する操作
– 深さ，部分木サイズ，次数 (子の数)，部分木の葉数
44
参考文献
[1] G. Jacobson. Space-efficient Static Trees and Graphs. In Proc. IEEE
FOCS, pages 549–554, 1989.
[2] O'Neil Delpratt, Naila Rahman, Rajeev Raman: Engineering the
LOUDS Succinct Tree Representation. WEA 2006: 134-145.
[3] J. I. Munro and V. Raman. Succinct Representation of Balanced
Parentheses and Static Trees. SIAM Journal on Computing,
31(3):762–776, 2001.
[4] R. F. Geary, N. Rahman, R. Raman, and V. Raman. A simple optimal
representation for balanced parentheses. Theoretical Computer Science,
368:231–246, December 2006.
[5] J. Ian Munro, Venkatesh Raman, and S. Srinivasa Rao. Space
efficient suffix trees. Journal of Algorithms, 39:205–222, 2001.
[6] D. Benoit, E. D. Demaine, J. I. Munro, R. Raman, V. Raman, and S. S.
Rao. Representing Trees of Higher Degree. Algorithmica, 43(4):275–
45
292, 2005.
[7] J. Jansson, K. Sadakane, and W.-K. Sung. Ultra-succinct
Representation of Ordered Trees. In Proc. ACM-SIAM SODA, pages
575–584, 2007.
[8] A. Farzan and J. I. Munro. A Uniform Approach Towards Succinct
Representation of Trees. In Proc. SWAT, LNCS 5124, pages 173–184,
2008.
[9] A. Farzan, R. Raman, and S. S. Rao. Universal Succinct
Representations of Trees? In Proc. ICALP, LNCS 5555, pages 451–
462, 2009.
[10] P. Ferragina, F. Luccio, G. Manzini, and S. Muthukrishnan.
Compressing and indexing labeled trees, with applications. Journal of
the ACM, 57(1):4:1–4:33, 2009.
[11] R. F. Geary, R. Raman, and V. Raman. Succinct ordinal trees with
levelancestor queries. ACM Trans. Algorithms, 2:510–534, 2006.
[12] H.-I. Lu and C.-C. Yeh. Balanced parentheses strike back. ACM
Transactions on Algorithms (TALG), 4(3):No. 28, 2008.
46

Download Report