B - Researchmap

簡潔データ構造
国立情報学研究所
定兼邦彦
目次
0. 基礎
1. ビットベクトル
2. 木構造1
3. 木構造2
4. 接尾辞配列
5. 接尾辞木
6. 動的なデータ構造
7. 配列
2
6. 動的なデータ構造
• ビット列，文字列，順序木を扱う
• 操作: access, rank, select, insert, delete
3
メモリモデル
• メモリはビットの配列 M[0..]
• 連続する w bitsの読み書きが O(1) 時間
– w: 計算機の語長
• アルゴリズムが読み書きしたアドレスの最大値を
そのアルゴリズムのメモリ使用量と定義
4
動的メモリ管理 [1]
• 以下の問題に対するデータ構造を与える
• B: m 個の可変長ビット列の配列
– B[i] をブロック i と呼ぶ
– 各ブロックの長さは最大 b ビット
• address(i): ブロック i のアドレスを返す関数
• realloc(i, b’): ブロック i の長さを b’ に変更
(address(i) は変更される場合がある)
• 計算モデル: 語長 w bits の word RAM
5
定理: b  m, log m  w とする．
ブロック B[1..m] の長さの合計を s bits とする．
このとき B は s + O(m log m + b2) bits で格納でき，
address は O(1) 時間，realloc は O(b/w) 時間で
実現できる．
証明: p = (log (mb)) とする．p は B へのポインタ
を表現するために必要なビット数．
メモリを b+4p bits のセグメントに分割する．
メモリの確保，開放はセグメント単位で行う
(途中を開放することは無い．常に最後．)
6
セグメントを双方向リストに格納する．
リスト Lx は長さ x のブロックを格納する (1  x  b)
– pred, succ (p bits): 前後のセグメントのアドレス
– offset (log b  p bits): そのセグメント内の最初の
ブロックの位置
– block_data (b+p bits): ブロックを格納
Lx
block_data
b+p bits
block
block
p bits p bits
pred offset
block
p bits
bl succ
offset
pred offset ock
offset
block
block
block
succ
7
• block には，B[i] のビット列と i を格納
(x + log m  x + p bits)
• block はセグメントの後ろから入れていく．1つの
セグメントに入りきらない場合は新しいセグメントを
1つ確保し，block は2つのセグメントに分割して
格納する．
• 1つの block は1または2つのセグメントに入る．
(blockの長さ)  b + p = (block_dataの長さ)
• セグメント内の block を列挙するには，block_data
の offset ビット目から順に取り出せばいい．
• B[i] の格納は順不同．別にポインタを格納する．
8
• 各ブロック B[i] (1  i  m) に対し
– Len[i] (log b  p bits): B[i] の長さ
– Pos[i] (log (b+p)  p bits): B[i] を格納するセグメント内
のブロックの位置
– Seg[i], Ind[j] (p bits): B[i] を格納するセグメント
Seg
1
1
3
2
5
1
10
2
25
2
100
1
Ind
pred offset
B[1]
B[100]
B[5]
succ
B[25]
B[10]
9
succ
Pos[1]
Pos[100]
Pos[5]
pred offset
B[3]
• 同じセグメントに格納されているブロックは
Seg の値は等しい (Seg[i1] = Seg[i2] = … = j)．
• Ind[j] が実際のセグメントのアドレスを現す
Seg
1
1
3
2
5
1
10
2
25
2
100
1
Ind
pred offset
B[1]
B[100]
B[5]
succ
B[25]
B[10]
10
succ
Pos[1]
Pos[100]
Pos[5]
pred offset
B[3]
address(i) の実現
• 1つのブロックは最大2つのセグメントに格納される
ので，address(i) の返り値は (addr, len) のペア2つ
とする．
• 1つ目のペアはInd[Seg[i]], Pos[i], Len[i]から決まる
• そのセグメント内に収まらない場合は，セグメント
の succ を使って残りのブロックを得る．
– 残りのブロックは succ のセグメント内の最初のブロック
• O(1) 時間
11
realloc(i, b’) の実現
• ブロック i の現在のアドレスと長さ b を求める
• ブロック i の内容を別の場所にコピーする
• 現在のアドレスは空きになるので，Lb の先頭の
ブロック j を空いたところへ移動
– Pos[j] と Seg[j] を更新
• Lb の先頭のセグメントが空になったら削除
– 全体で最後のセグメント z を空いたところへ移動
– Ind[z] を更新
• Lb’ の先頭セグメントにブロック i の内容を書く．
セグメントの空きが足りなければ新セグメントを
12
確保 (使用するメモリ領域を延ばす)
• ブロックとセグメントの移動は O(b/w) time
• ポインタ等の更新は O(1) time
必要な領域の計算
• ブロックの長さの合計は s
• 空きのあるセグメントは各リスト Lx ごとに最大1つ
– 全ブロックを格納するために必要なセグメント数は
s/b + b 以下
• 必要な領域は s + O(b2 + m log m) bits
• このデータ構造を D(b, m) と表す
• 注: 1ブロックの長さを w とすると，
1ブロックあたり log m bits は多すぎる
13
定理: b = O(w), log m  w とする．
ブロック B[1..m] の長さの合計を s bits とする．
このとき B は s + O(m log w + w4) bits で格納でき，
address と realloc は O(1) 時間で実現できる．
証明: B を w3 ごとに分割し，それぞれを D(1+w, w3)
を使って格納する．それらを Di で表す．
ただし各 Di は連続するメモリを使用することを
仮定しているのでうまくいかない．
各 Di の使用するメモリを管理するデータ構造 D
を用いる．
14
• Di が格納するブロックは w3 個．つまり w4 bits．
• それを w2 個のページに分割する．
– 各ページは w 個または 0 個のセグメントを持つ．
•
•
•
•
全 Di で使うページ数は m/w 個．
これらのページをデータ構造 D(O(w2), m/w)に格納
address は O(1) time
D での realloc は O(w) time だが，Di での realloc
が w 回起きないと D での realloc は起きないので，
最悪計算量を O(1) にできる．
15
必要な領域の計算
• 各 Di は (ブロックサイズ)+O(w3 log w) bits
• 全 Di で s + O(m log w) bits
• D は O(w4 + m/w log(m/w)) bits
• 全体で s + O(w4 + m log w) bits
このデータ構造で長さ n の0,1ベクトルを格納すると
• s = n, w = log n
• b = log n (1ブロックの長さ)
• m = s / b (ブロック数)
• 必要なメモリは nH0 + O(n log log n/log n + log416n)
動的なビットベクトル [2]
• 長さ n のビットベクトル B[1..n] を格納
• 操作
– access, rank, select
– insert(i, c): B[i] と B[i+1] の間にビット c を挿入
– delete(i): B[i] を削除
17
単純なデータ構造
• ベクトルを長さが L 以上 2L 以下のブロックに
分割 (L = (log2 n))
• ブロックをベクトルの順番に並べ平衡2分木に格納
– ブロックは葉に格納．ノード数 O(n/log2 n)
– 内部ノードには，その部分木に格納されている
全ブロック中の 1 の数を格納
– 木を格納する領域 O(n/log n) bits
• insert によってあるブロックの長さが 2L 超になった
ときは，ブロックを2つに分割
18
• delete によってあるブロックの長さが L 未満に
なったとき
– 左右どちらかのブロックの長さが L 超のときは，
そのブロックから 1 ビット移動
– 左右のブロックの長さがどちらも L の場合は，
どちらかと併合
• 平衡2分木の操作は O(log n) time
• ブロックの操作も O(log n) time
• 注: n の値が 2 倍になると “log n” が変わる
– log n が変わると索引を全て作り直す必要がある
19
“log n” の変更
• 長さ n のベクトルを 3 つの部分に分割
– left:
語長 w = log n  1 を使う
– middle: 語長 w = log n
を使う
– right: 語長 w = log n + 1 を使う
• insert を行った場合: left の最右ビットをmiddleへ
移動，middleの最右ビットをrightへ移動
• delete を行った場合: right の最左ビットをmiddleへ
移動，middleの最左ビットをleftへ移動
• n が2倍になると，leftが空になり，middle, rightが
新しいleft, middleになる．
20
• 索引の作り直しが不要
定理: 長さ n のビットベクトルは nH0 + O(n /log n) bits
で表現でき，access, rank, select, insert, delete は全て
O(log n) 時間で実行できる．
21
動的順序木 [2]
• 木構造を BP 列で表現し，動的なビットベクトル
同様に格納
• 平衡2分木のノードには，1の数だけでなく
区間最大最小木のノードの値を格納
定理: n ノードの動的順序木は 2n + O(n /log n) bits
で表現でき，全操作は O(log n) 時間で実行できる．
22
より高速なデータ構造
• 区間最大最小木として，分岐数が log n 以上
2 log n 以下の B-木を用いる
– 木の深さは O(log n /log log n) になる
• L = log2 n /log log n
23
操作の計算量
• P[i], findclose, findopen, enclose, rmq, pre_rank,
pre_select, isleaf, isancestor, depth, parent,
first_child, last_child, next_sibling, prev_sibling,
subtree_size, lca, deepest_node, height, in_rank,
in_select, leaf_rank, leaf_select, leftmost_leaf,
rightmost_leaf: O(log n / log log n) time
• level_ancestor, level_next, level_leftmost,
level_prev, level_rightmost: O(log n) time
• insert, delete: O(log n/ log log n) or O(log n) time
• degree, child, child_rank: O(q log n/ log log n)
24
or O(log n) time (q = degree)
7. 配列
• 入力: 長さ n の配列 (文字列) S[0..n1]
– S[i]  A, アルファベットサイズ 
• 問合せ
– S の指定された位置の部分文字列を返す
S[i..i+w1] (w = O(log n) つまり O(log n) bits)
– 語長 O(log n) bits の word RAM で O(1) 時間
• 索引サイズ: nHk(S) + o(n log ) bits
• 圧縮接尾辞配列では O(1) 時間にはならない
25
結果
• サイズ： LZ78 [Ziv, Lempel 78] と漸近的に同じ

k log   log log n 

nH k ( S )  O n log  
log n


• S の i 文字目からの連続する log n 文字
(log n ビット) を定数時間で復元可能
• このアクセス時間は未圧縮の場合と同じ
– データは圧縮されていないと見なせる
26
LZ78(LZW)圧縮法 [3]
•
•
•
•
文字列を辞書中のパタンに分割
数字に置き換えて符号化
辞書を更新
文字列が長くなると圧縮率が
エントロピーに収束
入力
a a a ba a ba a ba
出力
1 a 1 b 3 b
5
辞書
1
3
a
b
a
b
a
6
a
b
2
4
5
27
LZ78の圧縮率
長さ n の文字列 S を分解したフレーズの数 c は
n
n c
log  n
( : アルファベットサイズ)
• 圧縮後のサイズ: clog c  log   bits
• S が定常エルゴード情報源 (エントロピー H) から
生成されるなら c log c  H (n  )
n
• S の k 次経験的エントロピーHkに対し
n
c log c  nH k  c log  (kc  c)
c
[4]
28
部分復元の難しさ
• k 次エントロピーを達成するには，文字の符号を
その直前の k 文字から決める必要がある．
• 文字列のある部分を復元するにはその直前も
復元する必要がある．
• でも実は・・・
29

k log 
• LZ78での圧縮サイズの O n log  
log n


 項は

1語 (log n bits) あたり O(k log ) bits の冗長度が
あることを表す．
• つまり，1語ごとに k 文字をそのまま格納しても
冗長度は漸近的には増えない
• 1語を復元するために必要な情報は k 文字だけ
なので，他の部分は復元しなくていい
• ただし，k log  < log n である必要がある
30
単純なデータ構造1 (S1)
• S を w = ½ log n 文字ごとのブロックに分割
• 各ブロックの文字をハフマン符号で符号化
– n(1+H0(S)) bits
• ブロックへのポインタを格納
 O( n log  ) 
 O( n log  ) 
n
n
  O   log 
  O 
log 
 w
 w
 n/w 
 O(n log  / log n) 
 n log  log log n 

 O
log n


• ブロック内の文字の復号は表引きでO(1)時間
31
単純なデータ構造2 (S2) [5]
• S を w = ½ log n 文字ごとのブロックに分割
• 各ブロックの先頭 k 文字はそのまま格納
• 各ブロックの残りの w  k 文字は，文脈から決まる
確率に従い算術符号で符号化
( j 1) w
1
log
2

PrS[i ] | S[i  k ..i  1]
i  jw k 1
• 全ブロックでの合計は
n
1
1
log
  ns Prc | s log

PrS[i ] | S[i  k ..i  1] sAk cA
Prc | s 
i 1
1
  ns  ps ,c log
 nH k ( S )
ps ,c
cA
sAk
32
• 算術符号での誤差は
2n/w = O(n log  / log n)
• 各ブロックの符号を連結し, ポインタを格納
 n log  
 n log  log log n 
n
  O   O

log 
log n
 w
 n/w 


• 算術符号を定数時間で復号するための表
O(  2
k
1 logn
2
 log n)  O(
n log n)  o(n)
(k = o(log n) のとき)
k
• 合計で
 n log 

k log   log log n
nH k ( S )  O
 log n

33
単純なデータ構造3 (S3) [6]
• S を w = ½ log n 文字ごとのブロックに分割
• 各ブロックを1つの文字だとみなし, 符号を割当てる
– 文字は 1 から   n の整数で表される
– 各文字の頻度を数える
– 頻度の多い順に符号 0, 1, 00, 01, 10, 11, 000, 001,...
を割当てる
w
• 各ブロックの符号を連結し, ポインタを格納
 n log  
 n log  log log n 
n
  O   O

log 
log n
 w
 n/w 


34
サイズの解析
• ブロックへのポインタ: O(n log  log log n/log n)
• ブロックの符号から文字列の復号
 w  w log   n  12 log  n  log   12 n log n  o(n)
補題: ブロックの符号長の合計は次の値以下.
 n log 

k log   log log n
nH k ( S )  O
 log n

(S2のサイズ)
35
証明：あるブロックの符号は
– S2: 最初の k 文字をそのまま
残りは算術符号
– S3: w 文字をまとめて1つの符号
S3では多く出現するパタンに短い符号を割り当て
ている⇒符号長の合計はS2よりも長くない．
注：S3のサイズは k に依存しない
⇒ 全ての 0  k  o(log n) について同時に成立

 n log 


S3  min nH k ( S )  O
k log   log log n 
0 k o (log n )
36
 log n

動的な配列 [1]
• 入力: 長さ n の配列 (文字列) S[0..n1]
– S[i]  A, アルファベットサイズ 
• 操作
– S の指定された位置の部分文字列を返す
S[i..i+w1] (w = O(log n) つまり O(log n) bits)
– S の指定された位置の部分文字列を変更
S[i..i+w1]
• 索引サイズ: nHk(S) + o(n log ) bits
– S が変更されると，エントロピーも変化する
– 索引サイズを現在の S のエントロピーでおさえる
37
定理:
サイズ


k log   log log n  
 
nH k S   O n log    
log n



S の1語の読み込み: O(1) time
S の1語の書き換え: O(1/) time
系:

k log   log log n 

サイズ nH k S   O n log  
log n


(LZ78と同じ)
S の1語の読み込み: O(1) time
S の1語の書き換え: O min  1 log  n, log n   time


k
log log n  
38
• 1語の挿入・削除を許すと，読み書き・挿入削除
の時間は O(log n /log log n) になる．
39
まとめ
• 簡潔データ構造は，データを圧縮して保存し，検索
や部分復元を高速に行える
• 基本的な圧縮法は
–
–
–
–
–
索引を間引く
問題を小さい (polylog-sizeの) 部分問題に分割
部分問題に対する索引のサイズは無視できる
全体を小さいサイズの問題に変換できる
小さいサイズの問題には従来のデータ構造が使える
• 課題
– 圧縮による速度低下
40
参考文献
[1] Jesper Jansson, Kunihiko Sadakane, Wing-Kin Sung. Compressed
random access memory, arXiv:1011.1708v1.
[2] Kunihiko Sadakane, Gonzalo Navarro: Fully-Functional Succinct
Trees. SODA 2010: 134-149.
[3] Jacob Ziv and Abraham Lempel; Compression of Individual
Sequences Via Variable-Rate Coding, IEEE Transactions on
Information Theory, September 1978.
[4] S. Rao Kosaraju, Giovanni Manzini: Compression of Low Entropy
Strings with Lempel-Ziv Algorithms. SIAM J. Comput. 29(3): 893911 (1999).
[5] Rodrigo González and Gonzalo Navarro. Statistical Encoding of
Succinct Data Structures. Proc. CPM'06, pages 295-306. LNCS 4009.
[6] P. Ferragina and R. Venturini. A simple storage scheme for strings
achieving entropy bounds. Theoretical Computer Science, 372(1):115–
41
121, 2007.

Download Report