簡潔データ構造 国立情報学研究所 定兼 邦彦 目次 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 0n 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,v1)+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’) = l1 となる • 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
© Copyright 2025 ExpyDoc