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

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

背景 大量データの存在 単純な検索だけではなく，データマイニングなどの問合せを行いたい NTCIR-4 PATENT (日本語特許公報全文1993-1997) 文書数 3,496,252 サイズ 113.8G bzip2での圧縮サイズ 15.2G 従来の索引 (接尾辞配列) + データ 680.4G 1000人ゲノムプロジェクト DNA配列 3G文字×1000人 Webページ 単純な検索だけではなく，データマイニングなどの問合せを行いたい

従来のデータ構造の問題点 データのサイズが大きい 索引サイズが大きい 簡潔データ構造 圧縮するとランダムアクセスができない (遅い) 検索を行うには索引を追加する必要がある 索引サイズが大きい メモリに載らない ディスクに置く→低速処理 索引の情報量を落としてサイズ削減→精度低下 簡潔データ構造 従来の索引 (接尾辞配列) + データ 680.4G 簡潔データ構造 (索引+データ) 21.6G

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

簡潔表現 サイズが情報理論的下限に(ほぼ)一致する表現 入力が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) 時間にするには?

1. ビットベクトル 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 だが，実際は無視できない

小ブロック内でのRankの計算 語長は log n ではなく計算機の語長にする 語長 w = 64 bits とすると，w/2 = 32 bits の全パタン に対する表を作るとメモリが多く必要 キャッシュが効かないので遅い 16 bits / 8 bits に区切って表引きをする 最近のCPUは専用命令 (POPCOUNT) がある Intel SSE4.2以降 GPGPU (CUDA) 小ブロック長を w より大きくしてもいい R2 のサイズが小さくなる キャッシュが効くのであまり遅くならない

POPCOUNTの計算 (w = 64) r = x; r = ((r & 0xaaaaaaaaaaaaaaaa)>>1) r = ((r & 0xcccccccccccccccc)>>2) + (r & 0x3333333333333333); r = ((r>>4) + r) & 0x0f0f0f0f0f0f0f0f; r = (r>>8) + r; r = (r>>16) + r; r = ((r>>32) + r) & 127; O(log w) time

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の和を求める

Rank/Selectの拡張 (1) 0 のビットに関する問合せ rankc(B, x): B[0..x] = B[0]B[1]…B[x] 内の c の数 selectc(B, i): B の先頭から i 番目の c の位置 (i  1) rank0(B, x) = (x+1)  rank1(B, x) より， rank0 は追加索引無しで O(1) 時間 select0 は select1 の索引からは求まらないので， select1 と同様の索引を追加 大ブロックの長さが logc n 以下のときは，select1 の 索引を使用できる (ただしブロックの境界は異なる)

Rank/Selectの拡張 (2) 疎なベクトルの圧縮 必要な操作 長さ 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 次のエントロピーにほぼ一致

ベクトルの圧縮法 (1) ベクトルを長さ 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 の索引のサイズが無視できない

ベクトルの圧縮法 (2) 定理: 長さ n = 2w, 1の数 m のビットベクトルは bits で表現でき， select1 は 語長 (log n) bits の word RAM 上で O(1) 時間で求まる．(Grossi, Vitter [3]) 証明： 1 の位置を 0  p1  p2   pm < n とする． 各値は w bits の数だが，それを上位 bits と 下位 w  z bits に分ける．それぞれ qi, ri とする． bits なので下限に近い

q1, q2  q1, q3  q2,… を 1 進数で格納 ri はそのまま格納 k  0 は k 個の 0 と 1 個の 1 (0k1) で表す 最大 2m bits (m 個の 1 と qm  m 個の 0) ri はそのまま格納 m(wz) bits B = 1000000001000000110000000001000 n = 32, m = 5, w = 5, pi = 0, 9, 16, 17, 27 qi = 0, 1, 2, 2, 3 ri = 0, 1, 0, 1, 3 H: 10101101 L: 000 001 000 101 011

値の復元 qi = select(H,i+1)  i ri = L[i] pi = (qi << (wz)) + ri select の索引: O(m log log m/log m) bits pi は O(1) 時間で求まる n = 32, m = 5, w = 5, pi = 0, 9, 16, 17, 27 qi = 0, 1, 2, 2, 3 ri = 0, 1, 0, 1, 3 H: 10101101 L: 000 001 000 101 011

Rank/Selectの拡張 (3) 多値アルファベット access(S, x): S[x] を返す rankc(S, x): S[0..x] = S[0]S[1]…S[x] 内の c の数 selectc(S, i): S の先頭から i 番目の c の位置 (i  1) c  A = {0, 1, …, 1} アルファベットサイズ  > 2

データ構造1 S を  個の0,1ベクトルで表現し，FIDで圧縮 rank と select は定数時間 access は O() 時間 サイズ 文字 c が nc 回出現するとき，ベクトルのサイズは 全体で $: 010000000 a: 000010011 c: 001100000 g: 100001100 S: g$ccaggaa

データ構造2 S をそのまま格納  個の 0,1 ベクトルは S から求まる サイズ $: 010000000 a: 000010011 access は O(1) 時間  個の 0,1 ベクトルは S から求まる rank/select の簡潔データ構造をそのまま用いる 0,1ベクトルの log n ビットを得る時間は O(log ) rank と select は O(log ) 時間 サイズ $: 010000000 a: 000010011 c: 001100000 g: 100001100 S: g$ccaggaa (n log )

ウェーブレット木 [4] 1 個の0,1ベクトルから成る2分木 根のベクトル V[0..n1] V[i] = 1 ⇔ S[i] の最上位ビットが 1 根の右(左)の部分木は，最上位ビットが 1(0) の S の文字だけからなる文字列のウェーブレット木 最上位ビットは取り除く 1 S: g $ c c a g g a a V V0 S0 V1 S1 $ = 00 a = 01 c = 10 g = 11

rank の計算 b = (c の最上位ビット) c’ = (c の最上位ビットを除いたもの) r = rankb(V, x) rankc(S, x) = rankc’(Sb, r) (再帰的に計算) O(log ) 時間 木の深さ d のノードのベクトルの長さの合計は n 木の高さは log  n log  + O(n log  log log n/log n) = |S| + o(|S|) bits

access の計算 select の計算 b = access(V, x) r = rankb(V, x) access(S, x) = b : access(Sb, r) (再帰的に計算) O(log ) 時間 b = (c の最上位ビット) c’ = (c の最上位ビットを除いたもの) selectc(S, x) = selectb(V, selectc’(S, x)) select の計算

ベクトルの圧縮 nc: 文字 c の頻度 圧縮された V のサイズ 圧縮された V0 と V1 のサイズ S: g $ c c a g g a a V0 1 1 1 1 1 V0 V1 1 1 1 1 1 1

全てのレベルを合計すると まとめ access/rank/select: O(log ) 時間 サイズ: nH0+O(n log  log log n/log n)

Multi-ary Wavelet Trees [5] ウェーブレット木を2分木ではなく多分木にする access/rank/select: O(log /log log n) 時間 サイズ: nH0+o(n log ) bits  = polylog(n) のとき access/rank/select: O(1) 時間 サイズ: nH0+o(n) bits サイズは nH0+o(n)(nH0+1) bits にできる [6]

まとめ サイズ access rank select O() O(1) |S| +   o(n) O(log ) n(H0+1.44)+  o(n) O() O(1) |S| +   o(n) O(log ) nH0+log   o(n) nH0+o(n log ) O(log /log log n) nH0+o(n)(nH0+1) O(log log )

アルファベットが大きいとき [7,8] T: S を表す   n 行列 A: T を1行につなげたもの rankc(S,i) = rank1(A,(c1)n+i)  rank1(A,(c1)n) selectc(S,i) = select1(A,rank1(A,(c1)n+i)) A を長さ  のブロックに分割 01000000 00001001 00110000 10000110 S: g$ccagga T と定義 0100 0000 | 0000 1001 | 0011 0000 | 1000 0110 A:

0100 0000 | 0000 1001 | 0011 0000 | 1000 0110 A: B: 10 0 0 110 110 0 10 110 B: A の各ブロックの1の数を1進数で符号化 2n bits で計算できる とすると

ブロック内のrank/select ブロックの長さ:  ブロック内の 1 の位置を格納 selectl: O(1) 時間 ki: ブロック i 中の 1 の数 非圧縮なら ki log  bits ⇒ 全体で n log  bits 圧縮すれば nH0+O(n) bits selectl: O(1) 時間 rankl: y-fast trie [9] を用いる O(log log ) 時間 O(ki) bits access: O() 時間

accessが高速なデータ構造 S を表すベクトル A を仮想的に作り B を格納 S を長さ  のchunkに分割する : あるchunkに対応する T の 1 の位置を並べたもの  は {1,2,...,} の順列になる X: あるchunk中の文字の出現頻度 の１進数表現 X = 0 10 0 110 10 | 0 0 110 0 110 -1: 4123 1342 : 2341 1423 0100 0000 0000 1001 0011 0000 1000 0110 S: g$cc agga T 0100 0000 | 0000 1001 | 0011 0000 | 1000 0110 A: B: 10 0 0 110 110 0 10 110

X: 0 10 0 110 10 | 0 0 110 0 110 -1: 4123 1342 : 2341 1423 0100 0000 0000 1001 0011 0000 1000 0110 S: g$cc agga T (C の j 文字目) (Cの i 行の j 番目の1) rankl:  に対するy-fast trieと2分探索で求まる 0100 0000 | 0000 1001 | 0011 0000 | 1000 0110 A: B: 10 0 0 110 110 0 10 110

順列の計算 [10] {1,2,...,} の順列  に対するデータ構造  = log log  として用いる (i): O(1) 時間 -1(i): O() 時間 サイズ: (1+1/)  log  + O( log log /log ) bits  = log log  として用いる

計算量 データ構造 問い合わせ時間  と -1: n log  + O(n log /log log ) bits B: 2n + o(n) bits X: 2n + o(n) bits 問い合わせ時間 access: O(log log ) rank: O(log log ) select: O(1)

S から -1 の計算 あるchunk C の j 文字目を c とする -1(j) = (C 中で c より小さい文字の数)+rankl(C,c,j) = (select0(X,c)  c) + rankl(C,c,j) rankl は y-fast trieで計算  log log  + O() bits O(log log ) time -1の計算: O(log log ) time の計算: O(log log  log log log ) time -1: 4123 1342 : 2341 1423 0100 0000 0000 1001 0011 0000 1000 0110 S: g$cc agga T X: 0 10 0 110 10 | 0 0 110 0 110

計算量 データ構造: n(log  + o(log )) bits 問い合わせ時間 S: n log  bits (さらに圧縮可)  と -1: O(n log /log log log ) bits B: 2n + o(n) bits X: 2n + o(n) bits 問い合わせ時間 access: O(1) rank: O((log log )2 log log log ) select: O(log log  log log log )

O((log log )2 log log log ) まとめ サイズ access rank select n(H0+1.44)+  o(n) O() O(1) |S| +   o(n) O(log ) nH0+log   o(n) nH0+o(n log ) O(log /log log n) nH0+o(n)(H0+1) O(log log ) n log  +n  o(log ) |S|+n  o(log ) O((log log )2 log log log ) O(log log  log log log )

参考文献 [1] G. Jacobson. Space-efficient Static Trees and Graphs. In Proc. IEEE FOCS, pages 549–554, 1989. 簡潔データ構造の最初の論文. ただし問い合わせは O(1) 時間ではない. [2] R. Raman, V. Raman, and S. S. Rao. Succinct Indexable Dictionaries with Applications to Encoding k-ary Trees and Multisets, ACM Transactions on Algorithms (TALG) , Vol. 3, Issue 4, 2007. [3] R. Grossi and J. S. Vitter. Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching. SIAM Journal on Computing, 35(2):378–407, 2005. [4] R. Grossi, A. Gupta, and J. S. Vitter. High-Order Entropy-Compressed Text Indexes. In Proc. ACM-SIAM SODA, pages 841–850, 2003. [5] Paolo Ferragina, Giovani Manzini, Veli Mäkinen, and Gonzalo Navarro. Compressed Representations of Sequences and Full-Text Indexes. ACM Transactions on Algorithms (TALG) 3(2), article 20, 24 pages, 2007.

[6] Jérémy Barbay, Travis Gagie, Gonzalo Navarro, and Yakov Nekrich. Alphabet Partitioning for Compressed Rank/Select and Applications. Proc. ISAAC, pages 315-326. LNCS 6507, 2010. [7] Alexander Golynski , J. Ian Munro , S. Srinivasa Rao, Rank/select operations on large alphabets: a tool for text indexing, Proc. SODA, pp. 368-373, 2006. [8] Jérémy Barbay, Meng He, J. Ian Munro, S. Srinivasa Rao. Succinct indexes for strings, binary relations and multi-labeled trees. Proc. SODA, 2007. [9] Dan E. Willard. Log-logarithmic worst-case range queries are possible in space theta(n). Information Processing Letters, 17(2):81–84, 1983. [10] J. Ian Munro, Rajeev Raman, Venkatesh Raman, S. Srinivasa Rao. Succinct representations of permutations. Proc. ICALP, pp. 345–356, 2003. [11] R. Pagh. Low Redundancy in Static Dictionaries with Constant Query Time. SIAM Journal on Computing, 31(2):353–363, 2001.