簡潔3 - Researchmap

簡潔データ構造
国立情報学研究所
定兼邦彦
目次
0. 基礎
1. ビットベクトル
2. 木構造1
3. 木構造2
4. 接尾辞配列
5. 接尾辞木
6. 動的なデータ構造
7. 配列
2
区間最小値問題
Range Minimum Query
問題 (RMQ)
• 入力: 配列 A[1,n] (前処理可), 区間 [i,j]  [1,n]
• 出力: 部分配列 A[i,j] 中の最小値の添字
RMQA(3,6) = 5
RMQA(6,8) = 8
123456789
A 143504537
3
RMQのデータ構造
補題: 長さ n の配列に対するデータ構造のサイズを
s(n), 問い合わせ時間を t(n) とするとき，以下の式
を満たすデータ構造は O(n) 時間で作成可 [1].
 8n 

t (n)  O(1)  t 
 lg n 
 8n 
  o(n) (bits)
s(n)  4n  s
 lg n 
注: 元の配列は不要
4
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
A 143504537
0
1
3
3
4
4
5
5
7
5
Cartesian TreeとRMQの関係
• RMQA(i,j) = lca(i,j)
A 143504537
0
1
3
3
4
4
5
5
7
6
問題 (lca, lowest common ancestor)
• 入力: 根付木 T, T の2節点 x, y
• 出力: x, y の最近共通祖先
よく知られた結果
• lcaは線形時間の前処理の後，定数時間で求まる
[Harel, Tarjan SICOMP84]
[Schieber, Vishkin SICOMP88]
[Bender, Farach-Colton 00]
7
Cartesian Treeの性質
補題: A[1,n1] に対する木に A[n] を追加したとき，
A[n] は根から最右葉までのパス上に存在する．
証明: A[n] は配列中で一番右の要素なので
左の子にはならない．
0
1
1
2064
2
3
3
3
4
5
4
54
4
5
5
6
8
Cartesian Treeの作成
A[1,n1] に対する木に A[n] を追加するとき
• A[n1] から根までの要素と順に比較していく
• A[n] より小さい要素 x が現れたら，そこに挿入
• x の右の子は A[n] の左の子にする
1
1
3
3
4
4
4
5
9
5
計算量
補題: Cartesian treeは O(n) 時間で構成可
証明: A[i] を挿入するときの比較回数を ci とすると，
n
全体の計算量は
Oc 

i 1
i
Cartesian treeの最右パス上の各ノードは， A[i] の
挿入後にその左の子になるため，一度しか A[i] と
比較されない．よって，比較回数の和は n 以下．
つまり計算量は O(n)．
10
Cartesian Treeの括弧列表現
A 143504537
0
1
3
3
4
4
5
5
7
P’123234543434543212123434543232343210
P ((()((())()(())))()((()(()))()(())))
1
4
3
5
0
4
5
3
7
11
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
0
4
5
3
7
12
P’でのRMQ
• P’ を長さ w = (lg n)/2 のブロックに分割
• 各ブロック中の最小値を配列 B で表す
• P’[i’, j’] の最小値は以下の３つのどれか
– i’ を含むブロック中の最小値
– j’ を含むブロック中の最小値
– これらのブロックの間での最小値
P (()((()())())(()())())
P’ 1212343432321232321210
B
1
3
2
1
1
0
13
計算量
• P の長さ: 4n
• B の長さ: 4n/w = 8n/lg n
• ブロック内のRMQは表引きで定数時間
表のサイズ

O2
1 logn
2
 
log 2 n log log n  O n log 2 n log log n

 8n 

• 計算量 t (n)  O(1)  t 
 lg n 
 8n 
  o(n)
s(n)  4n  s
 lg n 
14
Sparse Tableアルゴリズム [2]
• 配列 B[1,m] の各区間[i,i+2k1]について
最小値を求めM[i,k] に格納する.
( i = 1 ,...,m , k = 1 ,2, ･･･ ,lg m )
• 問い合わせ区間 [s,b] が与えられたとき
1. k = lg(bs) とする
2. M[s, k] と M[b2k+1, k] を比較し,小さいほうを解とし
て出力する.
• O(1) 時間，O(m lg2 m) bit 領域
0
3
B 143504537
15
• 前述の再帰データ構造で，B の長さが O(n/lg3 n)
のときに用いる
⇒o(n) bit領域
定理: RMQは 4n+o(n) ビットのデータ構造を用いて
定数時間で計算できる
16
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
A 143504537

• 親の値は子より小さい
• 子の値は大きい順
0
1
3
3
4
4
5
5
17
7
補題: l = lca(i,j) とする．
• l = i のとき，RMQA(i,j) = i
• l  i のとき，RMQA(i,j) は l の子で，l から j への
パス上にあるもの
証明: l = i のとき，i+1,…, j は
A 143504537
i の子孫．木の定義より，

i1 = l1= r1
それらは A[i] より大きい．
0
l2 1
l  i のとき，l < i.
r2
3 j1
3
l の子は値の大きい順に並んで
4
4
いるので，一番右のものが最小 i2
5
j2
5
18
7
• 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
 l
– else return rank)(U, w)
i = 3, j = 9
A 143504537
0
r
1
3
3
xw
y
U ((()(())())(()())())
E 12323432321232321210
4
4
i
5
5
7
19
j
区間最大最小木 [5]
(Range Min-Max Trees)
• これまでの木構造の簡潔データ構造では，
実現したい問合せ毎に索引を追加していた
• 塵 (o(n) bits) も積もれば山
– 再帰に基づく手法 [6] では，findopen,
findclose のみで 3.73n bits
• 様々な問合せを1つの索引で実現したい
20
諸定義
• ベクトル P[0..2n-1] と関数 g に対し
t
sumP, g , s, t    g Pi 
def
is
fwd_search( P, g , s, d )  min i | sumP, g , s  1, i   d 
def
is
bwd_search( P, g , s, d )  max i | sumP, g , i  1, s   d 
def
is
rmq( P, g , s, t )  min sumP, g , s, i 
def
s i t
rmqi( P, g , s, t )  arg min sumP, g , s, i 
def
s i t
• RMQ, RMQi も同様に定義 (区間最大値)
21
括弧列での操作の実現法
• 補題関数  を (()=1, ())=1 とすると
findclose ( P, i )  fwd_search( P,  , i,1)
findopen( P, i )  bwd_search( P,  , i,0)  1
enclose ( P, i )  bwd_search( P,  , i,2)  1
level_ancestor ( P, i, d )  bwd_search( P,  , i, d  1)  1
enclose
findclose
P (()((()())())(()())())
E 1212343432321232321210
22
rank/select の実現
• 関数 ,  を  (0)=0,  (1)=1,  (0)=1,  (1)=0
とすると
rank1 ( P, i )  sum( P,  ,0, i )
select 1 ( P, i )  fwd_search( P,  ,0, i )
rank0 ( P, i )   sum( P, ,0, i )
select 0 ( P, i )  fwd_search( P, ,0,i )
• rank/select と括弧列の操作を統一的に扱う
23
区間最大最小木
• 超過配列 E を長さ s のブロックに分割
• 木の葉は1つのブロックに対応し，ブロック中の
最小値と最大値を格納
• 内部節点は l 個の子を持ち，子の最大/最小値を
格納
0/4
1/4
1/3
0/2
m/M 1/2 2/4 3/4 2/3 1/3 2/3 1/2 0/0
E 1212343432321232321210
(()((()())())(()())())
s=l=3
24
区間最大最小木の性質
• 各節点は配列のある区間に対応
• 配列の任意の区間は，節点に対応する O(lh) 個の
区間と2つの葉の部分区間の和集合で表される
(h は木の高さ)
0/4
1/4
1/3
0/2
m/M 1/2 2/4 3/4 2/3 1/3 2/3 1/2 0/0
E 1212343432321232321210
(()((()())())(()())())
s=l=3
25
超過配列の性質
• 全ての i に対し，E[i+1] = E[i]1 またはE[i]+1
• 区間 E[u,v] の最小値が a, 最大値が b のとき，
区間内には a  e  b の全ての整数 e が存在し，
それ以外は存在しない (中間値の定理)
• 長さ l の区間の最大値と最小値の差は l1 以下
–
⇒ 値を少ないビットで表現可能
1
3
2
4
5 6
11
8
7
9
10
1 2 3 4 5 6
7
8 9 10
11
P (()((()())())(()())())
E 1212343432321232321210
26
fwd_search(E,i,d)の計算
• 区間 E[i+1,N1] を前述のように分割 (N: 配列長)
• 分割した区間を左から順に見て行き，E[i]+d を
含む区間を探す
• O(lh+s) 時間
0/4
1/4
1/3
0/2
m/M 1/2 2/4 3/4 2/3 1/3 2/3 1/2 0/0
E 1212343432321232321210
(()((()())())(()())())
27
配列が短い (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)
28
子の探索は O(c) 時間
最近共通祖先等の計算
• lca(v,w) = parent(RMQ(v,w)+1)
– RMQ: 超過配列の区間 E[v,w] の最小値の位置
• 区間最大最小木で定数時間
• 深さ最大節点も同様
0/4
1/4
1/3
0/2
m/M 1/2 2/4 3/4 2/3 1/3 2/3 1/2 0/0
E 1212343432321232321210
(()((()())())(()())())
29
次数の計算
• 節点 v に対応する E の区間を [v,w] とする
• deg(v) = (E[v+1,w1] 内の最小値の数)
• 区間最大最小木の各区間に，その区間内の
最小値の数を格納する
• i 番目の子も求まる
1
2
2
1
1
2
2
1
1
2
2
1
E 1212343432321232321210
(()((()())())(()())())
30
配列が長い場合
• 括弧列を長さ wc のブロックに分割
それらのexcessの最大/最小値を M1,…, Mt,
m1,…, mt とする
• fwd_search(E,i,d) を求めるとき，i を含むブロックに
答えがなく，E[i]+d < (そのブロックの最小値) の時，
答えを含むブロック j は，mj < E[i]+d となる
最初のブロック
31
その他の問い合わせ
• RMQは従来のデータ構造を使用
– ブロック数は少ない (n/wc) ので問題なし
• その他問い合わせも同様
• 定理: 順序木の既知の全演算を定数時間で行える
2n + O(n/log n) bitsのデータ構造が存在
32
サイズの更なる削減
• “Succincter” [7] を利用
• augmented B-tree
– 配列 A[1..n] に対するB-tree
– 各節点は値が付加してある
– 値は子節点の値と部分木のサイズから決まる
• 区間最大最小木はaugmented B-tree
• 定理: 2n + O(n/logc n) bits
(c > 0 は任意の定数)
33
参考文献
[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.
34

Download Report