簡潔データ構造 国立情報学研究所 定兼　邦彦.

Presentation on theme: "簡潔データ構造 国立情報学研究所 定兼　邦彦."— Presentation transcript:

1 簡潔データ構造 国立情報学研究所 定兼　邦彦

2 目次 0. 基礎 1. ビットベクトル 2. 木構造1 3. 木構造2 4. 接尾辞配列 5. 接尾辞木 6. 動的なデータ構造 7. 配列

3 2. 木構造の簡潔データ構造 根付き木のみ扱う 順序木/非順序木 枝にラベルがある/ない 子ノード間に順序がある/ない
非順序木では，子を並び替えて同じになる木は 同一の木とみなす 枝にラベルがある/ない ノードのラベルは，その親への枝のラベルで代用

4 順序木とは ordered tree / ordinal tree 根付き木 子に順序がついている ラベルなし
枝ラベル→cardinal tree 2 6 8 1 7 3 5 4

5 順序木の簡潔表現 LOUDS (level order unary degree sequence)
BP (balanced parentheses) DFUDS (depth first unary degree sequence)

6 LOUDS表現 [1,2] 10110111011000000 節点の次数を幅優先順に1進数で符号化
次数 d → 1d0 n 節点で 2n+1 bits (下限に一致) i 番目の節点は i 番目の 1 で表す 2 3 8 1 7 4 6 5 L 1 2 3 4 5 6 7 8 LOUDS

7 木の巡回操作 (1) 10110111011000000 i 番目のノード: select1(L, i) (i  1)
firstchild(x) y := select0(rank1(L,x))+1 if L[y] = 0 then 1 else y lastchild(x) y := select0(rank1(L,x)+1)1 2 3 8 1 7 4 6 5 1 2 3 4 5 6 7 8 LOUDS L

8 木の巡回操作 (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だけで求まる 短所: 部分木のサイズが求まらない 2 3 8 1 7 4 6 5 1 2 3 4 5 6 7 8 LOUDS L

9 BP表現 [3] ((()()())(()())) 各節点を対応する括弧のペアで表現 n 節点で 2n bits サイズの下限と一致 P
6 8 1 7 3 5 4 P ((()()())(()())) BP

10 BPでの基本操作 ノードは( の位置で表す findclose(P,i): P[i] の( と対応する )の位置を返す
enclose(P,i): P[i] の( を囲む括弧の位置を返す enclose findclose 1 1 2 3 4 5 6 7 8 9 10 11 2 3 11 8 P (()((()())())(()())()) 4 7 9 10 5 6

11 木の巡回操作 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 findclose 2 3 8 11 1 2 3 4 5 6 7 8 9 10 11 4 (()((()())())(()())()) 7 9 10 5 6

12 子孫の数 (部分木の大きさ) v を根とする部分木の大きさは subtreesize(v) = (findclose(P,v)v+1)/2
degree (子の数) は findclose の繰り返しで求まるが 子の数に比例する時間がかかる 1 2 3 11 1 2 3 4 5 6 7 8 9 10 11 8 P (()((()())())(()())()) 4 7 9 10 5 6

13 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ベクトルで表現 ( ( ) ) ) p (p) (q) q r ( (r)

14 補題: ブロックの数を  とすると，opening pioneerの数は 23 以下．
証明: 各ブロックをノード，(b(p), b((p)) を枝とするグラフは外平面グラフ opening/closing pioneerは再びBPになる  = n/B = 2n/log n ⇒ BPの長さは O(n/log n)

15 再帰構造の表現 opening pioneerと対応する括弧の位置を 0,1ベクトル B で表現
B は長さ 2n, 1の数 O(n/log n) の疎なベクトル O(n log log n/log n) bits で表現できる ( ( ) ) ) p (p) (q) q r ( (r) P B 0100 0101 0000 0000 0010 1001 P1 ((()))

16 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)

17 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*) ( ( ) )

18 enclose (p) = enclose(P,p) とする b((p)) = b(p) ならば (p) は表引きで求まる
対応する括弧の位置も記憶 括弧が複数ある場合は一番外側だけ記憶 括弧を抜き出して再帰 ( ( (()))( ) ) )

19 BPでの基本操作2 rankp(P,i): P[1..i] 中のパタン p の数を返す
selectp(P,i): P 中の i 番目の p の位置を返す p の長さが定数なら，rank/selectは定数時間 1 1 2 3 4 5 6 7 8 9 10 11 2 3 11 8 P (()((()())())(()())()) 4 7 9 10 rank()(P,10) = 3 5 6

20 葉に関する操作 [5] 葉はBP中の () で表される i 番目の葉の位置 = select()(P, i)
部分木中の葉の数，部分木中の最左葉，最右葉 も求まる 1 1 2 3 4 5 6 7 8 9 10 11 2 3 11 8 P (()((()())())(()())()) 4 7 3 を根とする部分木 9 10 5 6

21 ノードの深さ 超過配列 E[i] = rank((P,i)  rank)(P,i) とすると depth(v) = E[v]
E は格納せず P と rank 計算用索引を格納 (()((()())())(()())()) P E 2 1 3 8 4 5 6 7 9 10 11

22 最近共通祖先 (lca) の計算 lca = lowest common ancestor
u = lca(v,w): v と w の共通の祖先で最も根から遠いもの 定数時間で計算可 v w u

23 m = RMQE(v,w): E[v..w] 中の最小値の添字 (RMQ = Range Minimum Query)
u = parent(RMQE(v,w)+1) E は超過配列. ノードの深さを表す m = RMQE(v,w): E[v..w] 中の最小値の添字 (RMQ = Range Minimum Query) u 146 3 5 2 7 1 4 6 w 1 7 3 2 1 3 5 5 2 4 6 v P (()((()())())(()())()) E u v m w

24 DFUDS表現 [6] ((()((())))(())) ノードの次数を深さ優先順に1進数で符号化
次数 d ⇒ d 個の ( と 1つの ) 先頭に(をつける 2n ビット 1 2 6 3 4 5 7 8 DFUDS U ((()((())))(())) 1 2 3 4 5 6 7 8

25 補題: n ノードの順序木のDFUDSは長さ 2n のバランス した括弧列になる
p 個の木に対するDFUDSを U1, U2,..., Up とする (ノード数が合計 n1, DFUDSの長さの合計 2n2) ルートがこれらの木を子に持つような木を考える. その木に対するDFUDS U は となる. Ui の先頭のダミー 括弧を除いたもの ルートの次数 p 先頭のダミー括弧

26 帰納法の仮定より，Ui はバランスしている. 先頭の括弧を取り除くため，( が1つ足りない. Uの先頭のダミー括弧と，ルートに対応する括弧列
((p) では ( が p 個余っている. よって U はバランスしている. ノード数は n，括弧列の長さは 2n となり成り立つ. Ui の先頭のダミー 括弧を除いたもの ルートの次数 p 先頭のダミー括弧

27 DFUDSでの各種操作 ノード (次数d) は，その括弧列 (d) の先頭位置で表現 次数:
括弧列での位置 v とノードの preorder i の変換は 次数:

28 i-th child v U1 U2 U3 (((()(())))((()))) v 1 2 6 5 3 4 7 8 9

29 Parent p 2 5 6 (((()(())))((()))) p 1 2 6 5 3 4 7 8 9

30 子孫の数 (部分木の大きさ) v を根とする部分木の大きさは
subtreesize(v) = (findclose(enclose(v))v)/2+1 p 2 5 6 (((()(())))((()))) p 1 2 6 5 3 4 7 8 9

31 DFUDS上でのLCA [7] 1232345432123210 ((()((())))(())) ((()()())(()()))
BP上とほぼ同じ演算でlcaを計算可 lca(x,y) = parent(RMQE(x,y1)+1) 最小値は最左のものを使う 1 2 6 3 4 5 7 8 E DFUDS U ((()((())))(())) 1 2 3 4 5 6 7 8 BP P ((()()())(()())) E

32 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 r2 r3 (((()(())))((()))) U E v 1 d 2 6 5 3 4 7 8 9

33 証明: 各部分木のDFUDS U[li..ri] は先頭に ( をつけるとバランスする ⇒ E[ri] = E[ri-1]1 = di
E[j] > E[ri] (li  j < ri) v r0 r1 r2 r3 (((()(())))((()))) U E v 1 d 2 6 5 3 4 7 8 9

34 補題: 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 T E d+1 d d1 > d+1

35 E[y1] = d+1 より， RMQE(x,y1) は r1 と y1 で 最小値 d+1 をとる．
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) となる．

36 その他の演算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 (((()(())))((()))) U E 1 2 3 4 5 6 7 8 9 6 2 4 1 3 7 9 8 5

37 その他の演算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 3 4 5 6 7 8 9 (((()(())))((()))) U E 1 2 6 5 3 4 7 8 9

38 DFUDSの圧縮 [7] LOUDS, BP, DFUDS 表現は n ノードの順序木を 常に 2n bits で表現でき，下限と一致している しかし，順序木がある制約を満たすときは 2n より 少ないビット数で表現可能 例: 全ての内部ノードの次数が 2 であるような木は n bits で表現可能 サイズの下限は何か 2 5 7 1 6 3 4 1 2 3 4 5 6 7

39 サイズの(1つの)下限 次数 i のノード数が ni である順序木の数は サイズの下限 定義: 木次数エントロピー
目標: 順序木を nH*(T) bits に圧縮し，各種操作 を O(1) 時間で実現

40 定理 長さ n の文字列(アルファベットサイズ)
　　⇒ ビット 　 任意箇所の log n ビットを定数時間で復元 DFUDS列 U をこの方法で圧縮すると，U の ビット列のエントロピーまで圧縮できる ただし，それは木次数エントロピーは関係ない

41 新しい表現 ((()((())))(())) S: 次数列 (c.f. DFUDSでは1進数で表現)
S を圧縮して格納し，そこから U を復元 U の任意位置の log n bitsを定数時間で復元できれば， 既存の索引がそのまま使える  = n なので，そのままだと圧縮できない ⇒S を次数が log n 以上とそれ以外に分割 S 1 U ((()((())))(())) 2 3 4 5 6 7 8 DFUDS New

42 大きい次数の圧縮 ((((((((()((())))(((((((((())) DFUDSでの符号の開始・終了位置を保存
次数が log n 以上の頂点は n/log n 個以下 ⇒ O(n log log n/log n) ビットで表現できる 9 3 10 ((((((((()((())))(((((((((()))

43 小さい次数の圧縮  = log n ⇒ nH0(S) = nH*(T) 2つの列を併合するのは簡単

44 まとめ: 括弧列で行える木の操作 判定操作 順序操作 巡回操作 サイズに関する操作 葉かどうか，先祖/子孫関係
前行順/後行順/中央順で i 番目の節点/葉 巡回操作 親，長男，次の弟，i 番目の弟, d 代上の祖先 最近共通祖先，深さ最大節点 サイズに関する操作 深さ，部分木サイズ，次数 (子の数)，部分木の葉数

45 参考文献 [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: [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–292, 2005.

46 [7] J. Jansson, K. Sadakane, and W. -K. Sung
[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.