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

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

5. 接尾辞木

接尾辞木 [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 1234567 ababac$

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

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

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

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

ノードの表現 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 (()((()())())(()())())

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

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

証明: 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 (()((()())())(()())())

証明: 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 (()((()())())(()())())

ノードの文字列深さ 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 0 3 1 0 2 0 0 文字列深さは隣り合ったleaf間の共通接頭辞の長さ(Hgt)で表せる

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

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

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

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

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

補題: 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

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

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

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

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 (()((()())())(()())()) 1212343432321232321210 E u v m w

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

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

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]

子ノードへの移動 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))

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

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

参考文献 [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)