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

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

区間最小値問題 Range Minimum Query 問題 (RMQ) 入力: 配列 A[1,n] (前処理可), 区間 [i,j]  [1,n] 出力: 部分配列 A[i,j] 中の最小値の添字 143504537 A 123456789 RMQA(3,6) = 5 RMQA(6,8) = 8

RMQのデータ構造 補題: 長さ n の配列に対するデータ構造のサイズを s(n), 問い合わせ時間を t(n) とするとき，以下の式を満たすデータ構造は O(n) 時間で作成可 [1]. 注: 元の配列は不要

Cartesian Tree [2] 配列A[1,n]に対するCartesian tree (デカルト木) とは 根ノード: A[1,n] の最小値 A[i] を格納 左部分木: A[1,i1] に対するCartesian tree 右部分木: A[i+1,n] に対するCartesian tree 143504537 A 1 3 3 4 4 5 5 7

Cartesian TreeとRMQの関係 RMQA(i,j) = lca(i,j) 143504537 A 1 3 3 4 4 5 5 7

問題 (lca, lowest common ancestor) 入力: 根付木 T, T の2節点 x, y 出力: x, y の最近共通祖先 よく知られた結果 lcaは線形時間の前処理の後，定数時間で求まる [Harel, Tarjan SICOMP84] [Schieber, Vishkin SICOMP88] [Bender, Farach-Colton 00]

Cartesian Treeの性質 補題: A[1,n1] に対する木に A[n] を追加したとき， 左の子にはならない． 5 3 4 1 4 3 1 5 5 3 4 1 2 5 3 4 1 6 1 2 4 6 3 4 5

Cartesian Treeの作成 A[1,n1] に対する木に A[n] を追加するとき A[n] より小さい要素 x が現れたら，そこに挿入 x の右の子は A[n] の左の子にする 4 3 1 5 5 3 4 1

計算量 補題: Cartesian treeは O(n) 時間で構成可 証明: A[i] を挿入するときの比較回数を ci とすると，全体の計算量は Cartesian treeの最右パス上の各ノードは， A[i] の 挿入後にその左の子になるため，一度しか A[i] と 比較されない．よって，比較回数の和は n 以下． つまり計算量は O(n)．

Cartesian Treeの括弧列表現 P’ 123234543434543212123434543232343210 P 143504537 A 1 3 3 4 5 4 5 7 P’ 123234543434543212123434543232343210 P ((()((())()(())))()((()(()))()(()))) 1 4 3 5 4 5 3 7

RMQのアルゴリズム [3] 配列 A[1,n] をCartesian treeに変換 Cartesian treeを括弧列 P, 深さ列 P’ に変換 A[i,j] の最小値の位置 m を求めるとき i’ = select()(P,i), j’ = select()(P,j) P’[i’, j’] の最小値の位置を m’ とすると， m = rank()(P,m’)+1 P’ 123234543434543212123434543232343210 P ((()((())()(())))()((()(()))()(()))) 1 4 3 5 4 5 3 7

P’でのRMQ P’ を長さ w = (lg n)/2 のブロックに分割 各ブロック中の最小値を配列 B で表す P’[i’, j’] の最小値は以下の３つのどれか i’ を含むブロック中の最小値 j’ を含むブロック中の最小値 これらのブロックの間での最小値 P (()((()())())(()())()) 1212343432321232321210 P’ B 1 3 2 1 1

計算量 P の長さ: 4n B の長さ: 4n/w = 8n/lg n ブロック内のRMQは表引きで定数時間 表のサイズ 計算量

Sparse Tableアルゴリズム [2] 配列 B[1,m] の各区間[i,i+2k1]について 最小値を求めM[i,k] に格納する. ( i = 1 ,...,m , k = 1 ,2, ･･･ ,lg m ) 問い合わせ区間 [s,b] が与えられたとき k = lg(bs) とする M[s, k] と M[b2k+1, k] を比較し,小さいほうを解として出力する. O(1) 時間，O(m lg2 m) bit 領域 3 143504537 B

前述の再帰データ構造で，B の長さが O(n/lg3 n) のときに用いる 　⇒o(n) bit領域 定理: RMQは 4n+o(n) ビットのデータ構造を用いて 定数時間で計算できる

RMQの 2n bits データ構造 [4] 配列 A[1..n] の 2d-Min-Heap とはノード v0,…,vn からなる木で，vi の親 vj は以下を満たす j < i A[j] < A[i] A[k]  A[i] for all j < k < i 親の値は子より小さい 子の値は大きい順 7 3 5 4 1 143504537 A 

l  i のとき，RMQA(i,j) は l の子で，l から j への パス上にあるもの 補題: l = lca(i,j) とする． l = i のとき，RMQA(i,j) = i l  i のとき，RMQA(i,j) は l の子で，l から j への パス上にあるもの 証明: l = i のとき，i+1,…, j は i の子孫．木の定義より， それらは A[i] より大きい． l  i のとき，l < i. l の子は値の大きい順に並んで いるので，一番右のものが最小 7 3 5 4 1 143504537 A  i1 = l1= r1 l2 r2 j1 i2 j2

2d-Min-Heapを表すDFUDS U を用いて，RMQは 次のように計算できる x = select)(U, i+1) y = select)(U, j) w = RMQE(x, y) if rank)(U, findopen(U, w)) = i return i else return rank)(U, w) i = 3, j = 9 7 3 5 4 1 143504537 A  l r i x w y U ((()(())())(()())()) 12323432321232321210 E j

区間最大最小木 [5] (Range Min-Max Trees) これまでの木構造の簡潔データ構造では， 実現したい問合せ毎に索引を追加していた 塵 (o(n) bits) も積もれば山 再帰に基づく手法 [6] では，findopen, findclose のみで 3.73n bits 様々な問合せを1つの索引で実現したい

諸定義 ベクトル P[0..2n-1] と関数 g に対し RMQ, RMQi も同様に定義 (区間最大値)

括弧列での操作の実現法 補題 関数  を (()=1, ())=1 とすると (()((()())())(()())()) 補題　関数  を (()=1, ())=1 とすると (()((()())())(()())()) 1212343432321232321210 P E findclose enclose

rank/select の実現 関数 ,  を  (0)=0,  (1)=1,  (0)=1,  (1)=0 とすると 関数 ,  を  (0)=0,  (1)=1,  (0)=1,  (1)=0 とすると rank/select と括弧列の操作を統一的に扱う

区間最大最小木 超過配列 E を長さ s のブロックに分割 木の葉は1つのブロックに対応し，ブロック中の 最小値と最大値を格納 内部節点は l 個の子を持ち，子の最大/最小値を格納 1212343432321232321210 (()((()())())(()())()) E 1/2 2/4 3/4 2/3 1/3 0/0 m/M 1/4 0/2 0/4 s = l = 3

区間最大最小木の性質 各節点は配列のある区間に対応 配列の任意の区間は，節点に対応する O(lh) 個の区間と2つの葉の部分区間の和集合で表される (h は木の高さ) 1212343432321232321210 (()((()())())(()())()) E 1/2 2/4 3/4 2/3 1/3 0/0 m/M 1/4 0/2 0/4 s = l = 3

超過配列の性質 全ての i に対し，E[i+1] = E[i]1 またはE[i]+1 区間 E[u,v] の最小値が a, 最大値が b のとき， 区間内には a  e  b の全ての整数 e が存在し， それ以外は存在しない (中間値の定理) 長さ l の区間の最大値と最小値の差は l1 以下 　　　　　　　　　　　⇒ 値を少ないビットで表現可能 (()((()())())(()())()) 1212343432321232321210 P E 2 1 3 8 4 5 6 7 9 10 11

fwd_search(E,i,d)の計算 区間 E[i+1,N1] を前述のように分割 (N: 配列長) O(lh+s) 時間 1212343432321232321210 (()((()())())(()())()) E 1/2 2/4 3/4 2/3 1/3 0/0 m/M 1/4 0/2 0/4

配列が短い (polylog) 場合 計算機の語長を w bits とする 補題 N < wc のとき，fwd_searchは O(c2)時間で計算可能 データ構造のサイズは N + O(Nc/w) + exp(w) bits 証明 　excessの値は wc から wc ⇒ O(c log w) bits 　1度に w/(c log w) 個の値を読める 　区間最大最小木の分岐数 l を w/log w にする 　⇒木の高さは O(c) 　　　子の探索は O(c) 時間

最近共通祖先等の計算 lca(v,w) = parent(RMQ(v,w)+1) 区間最大最小木で定数時間 深さ最大節点も同様 RMQ: 超過配列の区間 E[v,w] の最小値の位置 区間最大最小木で定数時間 深さ最大節点も同様 1212343432321232321210 (()((()())())(()())()) E 1/2 2/4 3/4 2/3 1/3 0/0 m/M 1/4 0/2 0/4

次数の計算 節点 v に対応する E の区間を [v,w] とする deg(v) = (E[v+1,w1] 内の最小値の数) 区間最大最小木の各区間に，その区間内の最小値の数を格納する i 番目の子も求まる 1212343432321232321210 (()((()())())(()())()) E 2 1

配列が長い場合 括弧列を長さ wc のブロックに分割 それらのexcessの最大/最小値を M1,…, Mt, m1,…, mt とする fwd_search(E,i,d) を求めるとき，i を含むブロックに 答えがなく，E[i]+d < (そのブロックの最小値) の時， 答えを含むブロック j は，mj < E[i]+d となる 最初のブロック

その他の問い合わせ RMQは従来のデータ構造を使用 その他問い合わせも同様 ブロック数は少ない (n/wc) ので問題なし その他問い合わせも同様 定理: 順序木の既知の全演算を定数時間で行える 2n + O(n/log n) bitsのデータ構造が存在

サイズの更なる削減 “Succincter” [7] を利用 augmented B-tree 配列 A[1..n] に対するB-tree 各節点は値が付加してある 値は子節点の値と部分木のサイズから決まる 区間最大最小木はaugmented B-tree 定理: 2n + O(n/logc n) bits (c > 0 は任意の定数)

参考文献 [1] 定兼邦彦, 渡邉大輔. 文書列挙問題に対する実用的なデータ構造. 日本データベース学会Letters Vol.2, No.1, pp.103-106. [2] Michael A. Bender, Martin Farach-Colton: The LCA Problem Revisited. LATIN 2000: 88-94 [3] Kunihiko Sadakane: Succinct data structures for flexible text retrieval systems. J. Discrete Algorithms 5(1): 12-22 (2007) [4] Johannes Fischer: Optimal Succinctness for Range Minimum Queries. LATIN 2010: 158-169 [5] Kunihiko Sadakane, Gonzalo Navarro: Fully-Functional Succinct Trees. SODA 2010: 134-149. [6] 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. [7] Mihai Pătraşcu. Succincter, Proc. FOCS, 2008.