数理情報工学演習第二B 数理2研 定兼　邦彦 2016/9/30

簡潔データ構造 簡潔データ構造＝データの簡潔表現＋簡潔索引 簡潔データ構造の例 集合 木，グラフ 文字列 順列，関数

簡潔表現 サイズが情報理論的下限に(ほぼ)一致する表現 入力がL通りのとき，情報理論的下限はlog L bits 例1: 集合 S  {1,2,...,n} のサイズの下限 log 2n = n bits {1,2} {1,2,3} {1,3} {2,3} {3} {2} {1}  n = 3 log の底は 2

例2: n ノードの順序木 例3: n 文字の文字列 n log  bits (: アルファベットサイズ) n = 4

どんなデータにも簡潔表現は存在 表現法によって，演算操作の手間が変化 適当な順序で列挙し，符号を割り当てる log L ビットで表現可 効率的な演算ができるかどうかは分からない 表現法によって，演算操作の手間が変化 目的に適した表現を用いる必要あり n = 4 000 001 010 011 100

簡潔索引 決められた操作を実現するためのデータ構造 サイズ: o(log L) bits 従来の表現と(ほぼ)同じ操作時間 計算モデル: word RAM 語長 w = log log L とする (従来のデータ構造と同じポインタサイズ)

word RAM 語長 w bits の word RAMでは 算術演算: +, , *, /, log (最上位ビットの位置) 論理演算: and, or, not, shift これらの演算は O(w) bits の表を用いて定数時間 で計算できる ( > 0 は任意の定数)

簡潔データ構造の基本的な考え 索引を上手く間引く 間引いた情報を他の部分から高速に復元する 例: 木構造 n 節点の通常の平衡2分木は O(n) 個のポインタで 表現され，各種操作は O(log n) 時間 これを O(n) bits にしたい 木の葉は常に (log n) 個の要素を格納すると， 節点数は O(n/log n) になり， O(n) bits で表現できる 木の高さは O(log n)，葉の探索も O(log n) 時間なので 全体でも O(log n) 時間 o(n) bits, o(log n) 時間にするには?

ビットベクトル B: 長さ n の 0,1 ベクトル B[0]B[1]…B[n1] サイズの下限 = log 2n = n bits 操作 rank(B, x): B[0..x] = B[0]B[1]…B[x] 内の 1 の数 select(B, i): B の先頭から i 番目の 1 の位置 (i  1) 全ての簡潔データ構造の基本 ナイーブなデータ構造 全ての答えを配列に格納 2n 語 (2 n log n bits) O(1) 時間問合せ B = 1001010001000000 3 5 9 n = 16

Rankの簡潔索引1 B を長さ log2 n のブロックに分割 ブロックの境界での rank(x)の値を R に格納 Rのサイズ rank(x): O(log2 n) 時間 R[x/log2 n]

Rankの簡潔索引2 各ブロックを長さ ½ log n の小ブロックに分割 小ブロックの境界での rank の値を R2 に格納 rank(x): O(log n) 時間 R1[x/log2 n] R2[x/log n]

Rankの簡潔索引3 小ブロック内での問い合わせに対する答えを予め求め，表に格納しておく x 表の大きさ 1 2 000 001 010 1 2 000 001 010 011 100 101 110 111 3 ½ log nビットの Bの全パタン

定理： 長さ n のビットベクトルでのrankは 語長 (log n) bits のword RAM上で n + O(n log log n/log n) bits を用いて O(1) 時間で求まる． 注： 小ブロックでのrankを計算する表の大きさは bits だが，実際は無視できない

Selectの簡潔索引 rank同様にやってもうまくいかない B を，1 を log2 n 個含む大ブロックに分割 i = q (log2 n) + r (½ log n) + s とする i が log2 n の倍数のときに select(i) を S1 に格納 i が ½ log n の倍数のときに select(i) を S2 に格納 S2 の要素は (n) になり得る→(log n) bits 必要 → S2 全体で (n) bits rank の索引を使って2分探索で求まるが O(log n) 時間 B を，1 を log2 n 個含む大ブロックに分割 大ブロックごとに2通りのデータ構造を使い分ける

大ブロックの長さが logc n を超えるとき log2 n 個の1の位置をそのまま格納 1つの大ブロックで そのような大ブロックは最大 個 全体で c = 4 とすると

大ブロックの長さ m が logc n 以下のとき 長さ ½ log n の小ブロックに分割 小ブロックを葉に持つ完全 分木を構築 木のノードには，その子孫のベクトルの1の数を格納 大ブロック内の 1 の数は log2 n → 各ノードの値は 2 log log n bits B = 100101000100010011100000001 1 2 3 4 9 O(c) m  logc n

select(i) を求めるには，木の根から探索する 木の高さは O(c) ノードに格納する値は大ブロック全体で ベクトル全体で select(i) を求めるには，木の根から探索する 子ノードの情報は bits で 表現できるので，表引きで訪れる子が決まる 探索時間は O(c) つまり定数

定理： 長さ n のビットベクトルでの rank と select は 語長 (log n) bits のword RAM上で n+O(n log log n /log n) bits を用いて O(1) 時間で求まる． 注： 子ノードの探索では bits つまり (log log n)2 = O(log n) を仮定している． 　これは小さい n では成立しない 補足： 大ブロック内の select の索引を用いて rank を計算できる 　木を葉から根にたどり，rankの和を求める

疎なベクトルの圧縮 長さ n の 0,1 ベクトルで，1 の数が m 個 必要な操作 サイズの下限 m << n とすると rankc(B, x): B[0..x] = B[0]B[1]…B[x] 内の c の数 selectc(B, i): B の先頭から i 番目の c の位置 (i  1)

文字列のエントロピー 定義: 文字列 S の次数 0 のエントロピー H0 定義: k 次エントロピー abcababc (pc: 文字 c の出現確率) 定義: k 次エントロピー Pr[S[i] = c] が S[ik..i1] (文脈) から決まる ns: 文脈が s である文字数 ps,c: 文脈 s で文字 c が出る確率 abcababc 文脈

疎なベクトルのサイズの情報理論的下限は， ベクトルの 0 次のエントロピーにほぼ一致

ベクトルの圧縮法 ベクトルを長さ l = ½ log n の小ブロックに分割 i 番目の小ブロック Bi 内の 1 の数を mi とする 小ブロックは bits で表現できる 全ブロックの合計は 1の数 1の数が決まったときの全パタンの数

rank, select の索引はベクトルが圧縮されていない ときと全く同じで，O(n log log n /log n) bits 圧縮された小ブロックへのポインタが必要 Bi へのポインタを pi とする 0 = p0 < p1 < <pn/l < n (圧縮されているので n 未満) pi  pi1  ½ log n i が log n の倍数のときに pi をそのまま格納 それ以外のときは差分で格納

定理： 長さ n, 1の数 m のビットベクトルは bits で表現でき， rank0, rank1, select0, select1 は 語長 (log n) bits の word RAM上で O(1) 時間で求まる． データ構造は O(n) 時間で構築できる． このデータ構造は FID (fully indexable dictionary) と呼ばれる (Raman, Raman, Rao [2]). 注：m << n のときは となることが あり，rank/select の索引のサイズが無視できない

簡潔木 簡潔データ構造 (succinct data structure) の一種 サイズが情報理論的下限に(ほぼ)一致する表現 各種操作を圧縮したまま行える n = 4

BP表現 ((()()())(()())) 各節点を対応する括弧のペアで表現 ⇒ 2n bits parent, subtree size, lca, depth, level ancestor 等が定数時間で求まる i-th child はO(1)だが少し遅い 2 6 8 1 7 3 5 4 P ((()()())(()())) BP

BPでの基本操作 ノードは( の位置で表す findclose(P,i): P[i] の( と対応する )の位置を返す enclose(P,i): P[i] の( を囲む括弧の位置を返す enclose findclose 1 1 2 3 4 5 6 7 8 9 10 11 2 3 11 8 P (()((()())())(()())()) 4 7 9 10 5 6

木の巡回操作 parent(v) = enclose(P,v) firstchild(v) = v + 1 sibling(v) = findclose(P,v) + 1 lastchild(v) = findopen(P, findclose(P,v)1) 1 enclose findclose 2 3 8 11 1 2 3 4 5 6 7 8 9 10 11 4 (()((()())())(()())()) 7 9 10 5 6

子孫の数 (部分木の大きさ) v を根とする部分木の大きさは subtreesize(v) = (findclose(P,v)v+1)/2 degree (子の数) は findclose の繰り返しで求まるが 子の数に比例する時間がかかる degree を O(1) 時間で求める索引も存在 1 2 3 11 1 2 3 4 5 6 7 8 9 10 11 8 P (()((()())())(()())()) 4 7 9 10 5 6

ノードの深さ 超過配列 E[i] = rank((P,i)  rank)(P,i) とすると depth(v) = E[v] E は格納せず P と rank 計算用索引を格納 (()((()())())(()())()) 1212343432321232321210 P E 2 1 3 8 4 5 6 7 9 10 11

区間最大最小木 (Range Min-Max Trees) これまでの木構造の簡潔データ構造では， 実現したい問合せ毎に索引を追加していた 塵 (o(n) bits) も積もれば山 再帰に基づく手法 では，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) 時間

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

文字列用の標準的データ構造 操作 代表的データ構造 サイズ：文字列 + O(n log n) bits パタンの出現回数，場所 共通部分文字列，極大パタン アラインメント 代表的データ構造 接尾辞木 [1,2] 接尾辞配列 [3] サイズ：文字列 + O(n log n) bits ヒトのDNA配列：30億文字 (750MB) 接尾辞木：40GB

接尾辞 (suffix) 文字列 T の先頭の何文字を除いたもの (n 種類) T の任意の部分文字列は，ある接尾辞の接頭辞 = T 1 いるかいないかいないかいるかいるいるいるか 2 るかいないかいないかいるかいるいるいるか 3 かいないかいないかいるかいるいるいるか 4 いないかいないかいるかいるいるいるか 5 ないかいないかいるかいるいるいるか 6 いかいないかいるかいるいるいるか 7 かいないかいるかいるいるいるか 8 いないかいるかいるいるいるか 9 ないかいるかいるいるいるか 10 いかいるかいるいるいるか 11 かいるかいるいるいるか 12 いるかいるいるいるか 13 るかいるいるいるか 14 かいるいるいるか 15 いるいるいるか 16 るいるいるか 17 いるいるか 18 るいるか 19 いるか 20 るか 21 か

接尾辞配列 接尾辞のポインタを 辞書順にソートした配列 サイズ n log n + n log |A| bits パタン P の検索 6 いかいないかいるかいるいるいるか 10 いかいるかいるいるいるか 4 いないかいないかいるかいるいるいるか 8 いないかいるかいるいるいるか 15 いるいるいるか 17 いるいるか 19 いるか 1 いるかいないかいないかいるかいるいるいるか 12 いるかいるいるいるか 21 か 3 かいないかいないかいるかいるいるいるか 7 かいないかいるかいるいるいるか 14 かいるいるいるか 11 かいるかいるいるいるか 5 ないかいないかいるかいるいるいるか 9 ないかいるかいるいるいるか 16 るいるいるか 18 るいるか 20 るか 2 るかいないかいないかいるかいるいるいるか 13 るかいるいるいるか SA 接尾辞のポインタを 辞書順にソートした配列 サイズ n log n + n log |A| bits パタン P の検索 O(|P| log n) time

圧縮接尾辞配列 (CSA) SA の代わりに [i] = SA-1[SA[i]+1] を格納 サイズ: O(n log |A|) bits パタン P の検索: O(|P| log n) time 0 1 7 $ 5 2 1 ababac$ 6 3 3 abac$ 7 4 5 ac$ 3 5 2 babac$ 4 6 4 bac$ 1 7 6 c$ SA  i

の計算法 接尾辞配列 SA を作る i を (T[SA[i]-1], i) の順に基数ソート  SA i=1,2,...,n に対し, c=T[SA[i]-1] を求める で c に対応する範囲に i を書く 0 1 7 $ 5 2 1 ababac$ 6 3 3 abac$ 7 4 5 ac$ 3 5 2 babac$ 4 6 4 bac$ 1 7 6 c$ SA  i

なぜ圧縮できるのか 接尾辞は辞書順に格納される 先頭の1文字を消しても辞書順は同じ  SA 12 14 15 16 17 18 19 20 21 3 4 5 9 1 2 6 7 10 11 13  6 いかいないかいるかいるいるいるか 10 いかいるかいるいるいるか 4 いないかいないかいるかいるいるいるか 8 いないかいるかいるいるいるか 15 いるいるいるか 17 いるいるか 19 いるか 1 いるかいないかいないかいるかいるいるいるか 12 いるかいるいるいるか 21 か 3 かいないかいないかいるかいるいるいるか 7 かいないかいるかいるいるいるか 14 かいるいるいるか 11 かいるかいるいるいるか 5 ないかいないかいるかいるいるいるか 9 ないかいるかいるいるいるか 16 るいるいるか 18 るいるか 20 るか 2 るかいないかいないかいるかいるいるいるか 13 るかいるいるいるか SA 接尾辞は辞書順に格納される 先頭の1文字を消しても辞書順は同じ

CSA の性質 i < j のとき T[SA[i]]  T[SA[j]] i < j より T[SA[i]+1..n] < T[SA[j]+1..n] SA[i’] = SA[i]+1, SA[j’] = SA[j]+1 とすると, i’ < j’ つまり i’ =SA-1[SA[i]+1]=[i]<[j]=j’ 0 1 7 $ 5 2 1 ababac$ 6 3 3 abac$ 7 4 5 ac$ 3 5 2 babac$ 4 6 4 bac$ 1 7 6 c$ SA  i

の符号化法 ’[i] = T[SA[i]]  n + [i] を格納 ’[i] (i = 1,2,...,n) は単調増加列になる [i] = ’[i] mod n T[SA[i]] = ’[i] div n ’[i] (i = 1,2,...,n) は単調増加列になる n(2+log ) $: 2 a: 5, 8, 9 c: 3, 4 g: 1, 6, 7 $: 000010 a: 010101, 011000, 011001 c: 100011, 100100 g: 110001, 110110, 110111

’の符号化法 ’[i] の2進表現の上位 log n ビット ’[i] の下位 log  ビットはそのまま格納 $: 2 直前の値からの差分を1進数で符号化 最大 2n ビット (1の数 = n，0の数  n) ’[i] の下位 log  ビットはそのまま格納 n log  bits $: 2 a: 5, 8, 9 c: 3, 4 g: 1, 6, 7 $: 000010 a: 010101, 011000, 011001 c: 100011, 100100 g: 110001, 110110, 110111 1, 000001, 01, 1, 001, 01, 0001, 01, 1 10, 01, 00, 01, 11, 00, 01, 10, 11

’の復号 ’[i] = x   + y 時間計算量： O(1) 上位桁： x = select(H,i)  i 下位桁： y = L[i] ’[i] = x   + y 時間計算量： O(1) 領域計算量： n(2+log ) + O(n log log n/log n) $: 2 a: 5, 8, 9 c: 3, 4 g: 1, 6, 7 H: 1, 000001, 01, 1, 001, 01, 0001, 01, 1 L: 10, 01, 00, 01, 11, 00, 01, 10, 11

の圧縮 [i] を T[SA[i]] で分割 各 S(c) を符号化： 全体で H0  log  (等号は p1 = p2 = … のとき) ( :文字 c の出現確率)

要素 SA[i]のアクセス方法 i が log n の倍数のときに SA[i] を格納 k = 0; w = log n;  SA while (i % w != 0) i = [i]; k++; return SA2[i / w] - k;  i SA 0 8 0 1 7 $ 5 2 1 ababac$ 6 3 3 abac$ 7 4 5 ac$ 3 5 2 babac$ 4 6 4 bac$ 1 7 6 c$ SA2 0 8 1 3 2 4 アクセス時間: 平均 O(log n) 時間

SA[i]が log n の倍数のものを SA2 に格納 B[i]=1  SA[i] が log n の倍数 SA[i]が log n の倍数のものを SA2 に格納 10 8 9 11 13 15 1 6 7 12 14 16 2 3 4 5  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 B 1 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 T E B D E B D D A D D E B E B D C SA 8 14 5 2 12 16 7 15 6 9 3 10 13 4 1 11 SA2 2 3 4 1 k = 0; w = log n; while (B[i] != 0) i = [i]; k++; return SA2[rank (B,i)]w  k; B : n+o(n) ビット アクセス時間: O(log n) 時間

の階層的表現 レベル i では T 中の連続する 2i 文字を1つの文字とみなす 文字列のエントロピーは増えない B 1 1 0 1 1 1 0 0 1 0 0 1 0 1 0 0 T E B D E B D D A D D E B E B D C SA 8 14 5 2 12 16 7 15 6 9 3 10 13 4 1 11 BD EB DD AD DE BE BD C$ SA1 4 7 1 6 8 3 5 2 BDEB DDAD DEBE BDC$ SA2 2 3 4 1

データ構造のサイズ レベル数が 1/ のとき : 1/  n(3+H0) bits SA1/ : n/log n  log n = n bits B:  n + n/2 + n/4 + ...  2n bits 合計: bits SA[i] の計算: 時間

部分文字列の検索 二分探索時に実際のSAの値は必要ない T E B D E B D D A D D E B E B D C 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 　　10 8 9 11 13 15 1 6 7 12 14 16 2 3 4 5  r 1 2 2 2 2 3 4 4 4 4 4 4 5 5 5 5 D 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 SA 8 14 5 2 12 16 7 15 6 9 3 10 13 4 1 11 A B B B B C D D D D D D E E E E D D D D E A C D D E E B B B B C D E A E B B D D D E D E C D E 1 2 3 4 5 C A B C D E

後方検索 P=P[1..p] の検索 for (k = p; k >=1; k--)  SA 0 1 7 $ C[$]=[1,1] C[a]=[2,4] C[b]=[5,6] C[c]=[7,7] P=P[1..p] の検索 for (k = p; k >=1; k--) 0 1 7 $ 5 2 1 ababac$ 6 3 3 abac$ 7 4 5 ac$ 3 5 2 babac$ 4 6 4 bac$ 1 7 6 c$ SA  i O(p log n) time

の値で二分探索: O(log n) time P の検索に O(|P| log n) time

テキストの部分的な復元  T[9..13] = DDEBEを復元する場合 i=SA-1[9]=10 を求める 1 2 3 4 5 C A B C D E 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 T E B D E B D D A D D E B E B D C A B B B B C D D D D D D E E E E  10 8 9 11 13 15 1 6 7 12 14 16 2 3 4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 SA 8 14 5 2 12 16 7 15 6 9 3 10 13 4 1 11

圧縮接尾辞配列の機能 lookup(i): SA[i] を返す (O(log n) 時間) inverse(i): SA-1[i] を返す (O(log n) 時間) [i]: SA-1[SA[i]+1] を返す(O(1) 時間) substring(i,l): T[SA[i]..SA[i]+l-1]を返す O(l) 時間 (i からT[SA[i] は長さ n のベクトルのrankで求まる)