Presentation is loading. Please wait.

Presentation is loading. Please wait.

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

Similar presentations


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

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

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

3 5. 接尾辞木

4 接尾辞木 [1,2] ababac$ 1234567 枝のラベル ノードの深さ 葉の添え字 子ノードへのポインタ Suffix link
$ a c b a 7 1 6 枝のラベル ノードの深さ 葉の添え字 子ノードへのポインタ Suffix link 文字列 T c b a 2 3 b c 5 b c 2 4 1 3 ababac$

5 接尾辞木での操作 root(): 根ノードを返す isleaf(v): v が葉なら Yes を返す
child(v,c): v の子 w を返す (vw 間の枝ラベルは文字 c から始まる) firstchild(v): v の最初の子を返す sibling(v): v の次の弟を返す parent(v): v の親を返す

6 edge(v,d): v への枝のラベルの d 文字目を返す depth(v): v の文字列深さを返す
lca(v,w): v, w のlowest common ancestorを返す sl(v): v のsuffix linkで指されているノードを返す $ a b c 7 1 3 5 2 4 6

7 接尾辞木の構成要素 [3] テキスト: n lg |A| bits 木構造: O(n lg n) bits
suffix link: n lg n bits

8 木構造の表現 木をBP列で表現 最大 4n+o(n) bits ノードは( の位置で表現 (()((()())())(()())())
1 3 5 2 7 4 6 7 1 3 5 2 4 6 (()((()())())(()())())

9 ノードの表現 v: 括弧列中の( の位置 j: ノードの preorder i: ノードの inorder preorder
j = rank((P,v) v = select((P,j) i: ノードの inorder preorder 1 3 8 4 2 5 6 7 9 10 11 1 2 3 4 5 6 7 8 9 10 11 (()((()())())(()())())

10 ノードの inorder 内部ノードのみに定義 根から深さ優先探索を行ったときに v を下から訪れるまでの内部ノードの数
(子が3つ以上の場合) 146 x 3 x 5 2 x x x x x

11 inorder の計算 v とその最小のinorder i は定数時間で変換可 (()((()())())(()())()) v
i = rank()(P,findclose(P,v+1)) v = enclose(P,select)( (P,i)+1) 146 3 5 2 x 1 7 3 2 1 3 5 5 2 4 6 (()((()())())(()())()) v

12 証明: i = rank()(P,findclose(P,v+1)) v+1 は v の最初の子 w
u = findclose(P,v+1) は w を根とする部分木の最後の位置 inorder は葉から葉へのパス上で1回定義される. よって葉と inorder には1対1対応がある. inorder の値は根から v までの巡回中の葉の数. つまり i = rank()(P,u) 146 3 5 2 x v w v w u (()((()())())(()())())

13 証明: v = enclose(P,select)( (P,i)+1)
i は深さ優先探索において,下からノード w を訪れ次に w の別の子を訪れた回数である. この動作は P 中では 「)(」 で表される. x = select)( (P,i)+1 は v の子を表す. 146 3 5 2 x v v x (()((()())())(()())())

14 ノードの文字列深さ ababac$ $ a b c 7 1 3 5 2 4 6 1 2 3 Hgt 0 3 1 0 2 0 0
$ a b c 7 1 3 5 2 4 6 1 2 3 ababac$ Hgt 文字列深さは隣り合ったleaf間の共通接頭辞の長さ(Hgt)で表せる

15 Hgt 配列 Hgt[i]= lcp(SA[i], SA[i+1]) サイズ: n log n bits 0 7 $ 3 1 ababac$

16 Hgt[i]は inorder で i 番目の内部ノードの深さに等しい
2 3 5 $ a b c 7 1 4 6 Hgt    0 (()((()())())(()())()) Hgt[i]は inorder で i 番目の内部ノードの深さに等しい 内部ノードと葉に1対1対応 が存在し定数時間で求まる i = rank()(findclose(v+1)) depth(v) = Hgt[i]

17 枝ラベルの計算 ノード v の inorder を i とする i 番目の葉は v の子孫 i 番目の葉は SA[i] を表す
v に入る枝は SA[i] の部分文字列 v parent(v) SA[i] d1 d2 b a c d 枝の長さ = d2  d1

18 Hgt 配列の圧縮 i と SA[i] が与えられたとき, Hgt[i]は 2n +o(n) bits の索引を用いて定数時間で求まる

19 Hgt 配列の並び替え SA+Hgt の値はSAに従ってソートすると単調 Hgt[i]= lcp(SA[i], SA[i+1])
Hgt SA SA+Hgt SA+Hgt の値はSAに従ってソートすると単調 SA+Hgt SA [1,n]の範囲の長さ n の単調な数列は 2n bitsで表せる

20 補題: SA[i]=p, SA[j]=p+1 とすると Hgt[j]  Hgt[i]  1
d p ababac$ q abac$ d-1 p+1 babac$ q+1 bac$ SA Hgt i j d p ababac$ q abac$ d-1 p+1 babac$ bab.. q+1 bac$ SA Hgt i j Hgt[SA-1[p+1]]  Hgt[SA-1[p]]-1

21 Hgt[SA-1[k]]+k (k = 1,2,...,n) は単調増加で

22 Hgt[i] の計算法 k = SA[i] を求める 単調増加列の k 番目の要素 v を復号 Hgt[i] = v - k
接尾辞配列で定数時間 圧縮接尾辞配列で O(log n) 時間 (0<<2) 単調増加列の k 番目の要素 v を復号 selectで定数時間 Hgt[i] = v - k

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

24 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 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

25 Suffix linkの表現 sl(node(c)) = node() 圧縮接尾辞配列の関数を用いる  c sl(v) b 2 5
3 6 x y x’ y’ v w sl(node(c)) = node() 圧縮接尾辞配列の関数を用いる

26 証明: 葉は () で表され,対応する接尾辞の辞書順に 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] を表す.

27 l = lcp(x,y) とすると,l は v の文字列深さと等しい lcp(x’,y’) = l1 となる
lca(x’,y’) は v より1つ短い文字列を表す つまり sl(v) v y x SA[y] SA[x]

28 子ノードへの移動 w = child(v,c): v の子ノード w で文字 c から始まる枝ラベルを持つもの v の子ノードを列挙する場合
firstchildとsiblingを用いて子ノード u を列挙 edge(u,1) = c である u を探す v の子を2分探索 v の i 番目の子を求める演算を用いる SAの2分探索を用いる場合 v の最左葉と最右葉の辞書順 l, r を求める SA[l..r] を d +1 文字目で2分探索 (d = depth(v))

29 圧縮接尾辞木のデータ構造 以下の要素から成る 圧縮接尾辞木のサイズは |CSA|+6n+o(n) bits 圧縮接尾辞配列: |CSA|
Hgt配列: 2n+o(n) bits 圧縮接尾辞木のサイズは |CSA|+6n+o(n) bits

30 各操作の計算量 root, isleaf, firstchild, sibling, parent, lca: 定数時間
depth, edge: O(tSA) 時間 sl: O(t) 時間 child: O(tSA log |A|) 時間 tSA: SA[i] を計算する時間 t: [i] を計算する時間

31 参考文献 [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): (2007)


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

Similar presentations


Ads by Google