東京大学大学院情報理工学系研究科 数理情報学専攻 定兼 邦彦 2016年4月7日 数理工学のすすめ 東京大学大学院情報理工学系研究科 数理情報学専攻 定兼 邦彦 2016年4月7日 http://researchmap.jp/sada/resources/

自己紹介 名前： 定兼 邦彦 （さだかね くにひこ） 所属： 東京大学大学院情報理工学系研究科数理情報学専攻 名前： 定兼　邦彦　（さだかね　くにひこ） 所属： 東京大学大学院情報理工学系研究科数理情報学専攻 経歴： 1991年理1入学，2000年理学系研究科情報科学専攻修了 2000年　東北大学大学院情報科学研究科助手 2003年　九州大学大学院システム情報科学研究院助教授 2009年　国立情報学研究所准教授 2014年　東京大学大学院情報理工学系研究科教授 研究分野： データ圧縮，データ構造，情報検索 最近の研究： ビッグデータ処理 簡潔データ構造 並列アルゴリズム

アルゴリズムとデータ構造 アルゴリズム (algorithms, 算法): 計算等の手順 数を小さい順に並べる (ソート) Webのキーワード検索 最短経路探索 データ構造 (data structures): 計算機にデータを格納する方法 配列，リスト，ハッシュ，2分木 アルゴリズムやデータ構造を工夫すると， 同じ問題が高速に解けるようになる

ビッグデータ処理の問題点 大量のデータがあるとき，それを圧縮することでディスク容量や通信コストを抑えられる しかし圧縮してあるデータを使うときは復元しなければならない データを高速に処理するにはデータ構造を用いるが，そのサイズも問題になる データを圧縮したまま使えないか？ データ構造も圧縮できないか？

モールス符号 (信号) 1830年代に提案 短点 ・ と長点 － の組み合わせ 長点は短点3つ分の長さ SOS = ・ ・ ・－ － －・ ・ ・ 英語で使われる頻度の高い e, t は 短い符号 ・, － になっている ⇒データ圧縮 文字 符号 A ・－ N －・ B －・・・ O －－－ C －・－・ P ・－－・ D －・・ Q －－・－ E ・ R ・－・ F ・・－・ S ・・・ G －－・ T － H ・・・・ U ・・－ I ・・ V ・・・－ J ・－－－ W ・－－ K －・－ X －・・－ L ・－・・ Y －・－－ M －－ Z －－・・

s から t へ矢印の通りに移動するルートを 表現するには Q P P:     0010110 Q:     1100001 7ビットで表現できる もっと小さくできる?

s から t へ矢印の通りに移動する行き方は 何通り? ルートは4個の→と3個の↑で表現できる 行き方は 通り 26 = 64 > 35 なので， 6 ビットで表現できる s t P Q P:     Q:    

s から t へのルートを 6 ビットで表現するには どう符号化すればいいか 各ルートを 0 から 34 の整数で表現する 0 から 19 の整数で表現する s から最初に上に行くルートは 通り 20 から 34 の整数で表現する s t P Q

s から最初に右に行くルート20個を考える 次に右に行くルートは 通り 次に上に行くルートは 通り P 0 から 9 の整数で表現する 次に右に行くルートは 通り 0 から 9 の整数で表現する 次に上に行くルートは 通り 10 から 19 の整数で表現する s t P

s から右，右に行くルート10個を考える 次に右に行くルートは 通り 次に上に行くルートは 通り P 0 から 3 の整数で表現する 次に右に行くルートは 通り 0 から 3 の整数で表現する 次に上に行くルートは 通り 4 から 9 の整数で表現する s t P

s から右右上に行くルート6個を考える 次に右に行くルートは 通り 次に上に行くルートは 通り P 4 から 6 の整数で表現する 次に右に行くルートは 通り 4 から 6 の整数で表現する 次に上に行くルートは 通り 7 から 9 の整数で表現する s t P

s から右右上右に行くルート3個を考える 次に右に行くルートは 通り 次に上に行くルートは 通り P 4 から 4 の整数で表現する 次に右に行くルートは 通り 4 から 4 の整数で表現する 次に上に行くルートは 通り 5 から 6 の整数で表現する s t P

s から右右上右上に行くルート2個を考える 次に右に行くルートは 通り 次に上に行くルートは 通り P 5 から 5 の整数で表現する 次に右に行くルートは 通り 5 から 5 の整数で表現する 次に上に行くルートは 通り 6 から 6 の整数で表現する s t P

結局，経路 P は整数 6 で表される 同様に，経路 Q は整数 30 で表される s t P Q

一般に，上に r 回，右に nr 回移動する場合， ルートの数は 最初に右に行くルートの数は 最初に上に行くルートの数は n 個の矢印のうち，↑の位置を nr,nr1, …,n1 とすると ルートは整数 で表される

ルートの復元 ルートを表す整数 30 から，ルートを復元する s から最初に右に行くルートは 通り 30>20 なので，最初は上に行っている 最初に上に行った点からルート 3020 = 10 を復元 s t P Q

圧縮率 上に r 回，右に nr 回移動する場合 なので，変換する方が小さい n 個の矢印→↑…で表現: n ビット 整数に変換して表現: ビット なので，変換する方が小さい 　なので，r が小さければ圧縮率が高くなる (もしくは nr が小さければ) エントロピー

厳密には，ルートを表す ビットの値の他に n と r の値も保存する必要がある 合計で ビット

n が大きい場合 n > 10億 を計算するには，大きい数の掛け算，割り算が必要になり，遅いしメモリも多く必要となる s t

ルートを一定の長さ l ごとに区切る 各部分ルートに対し，↑の数を記録する l = 8 t t r4 = 2 r3 = 5 r2 = 2 s s

各部分ルートは ビットで表現できる t t r4 = 2 r3 = 5 l = 8 r2 = 2 r1 = 3 s s

はどれくらいの大きさ? 分割してもサイズは (あまり)増えない

s から t への行き方は何通り? t s

5通り

→と (, ↑ と ) を対応させると，各ルートは括弧の対応の取れた(バランスした)括弧列を表す (()()) (())() ((())) ()(()) ()()()

バランスした括弧列は，深さが常に 0 以上の経路と対応する ((())) (()()) (())() ()(()) ()()()

バランスした括弧列と順序木には1対1対応がある ((())) (()()) (())() ()(()) ()()()

順序木の圧縮 木をバランスした括弧列で表現する n 点の木は長さ 2n の括弧列で表現できる もっと短い表現は無いか 一番外側に括弧を追加する n 点の木は長さ 2n の括弧列で表現できる もっと短い表現は無いか n = 4 (((()))) ((()())) ((())()) (()(())) (()()())

順序木の個数 n 点の順序木の個数を Tn とする Tn = (長さ 2n2 のバランスした括弧列の数) < (長さ 2n2 の全ての括弧列の数) = 22n2 Tn = (縦横n1マスずつの格子で対角線を またがない経路の数) Cn はカタラン数 (Catalan number) と呼ばれる n = 4

カタラン数 対角線をまたぐ s-t 経路の数を求める t u s’ s n = 3 対角線を初めて跨いだ点を u とする s から u の経路を(紫の線で)折り返す s’ から t の全ての経路の数と等しい

順序木の表現のサイズ (スターリングの公式より) b ビットで表現できるものは最大 2b 種類 n 点の順序木は Cn1 種類ある 順序木を表現するには ビット必要 つまり，括弧列による順序木の表現は ほぼ最適サイズ

カタラン数の漸化式

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

集合に対する演算 集合 S  {1,2,...,n} に対して次の値を求めたい S の要素を小さい順に配列に入れておくと rank(S, x): S の中の x 以下の要素の数 select(S, i): S の要素で i 番目に小さいもの S の要素を小さい順に配列に入れておくと select(S, i) = A[i] なので定数時間 rank(S, x) は二分探索で O(log m) 時間 (m: 要素数) データ構造のサイズ: m log n ビット m > n / log n のとき，サイズは下限 n より大きい 1 2 3 4 5 6 7 A 1 3 7 9 10 14 15

集合の簡潔表現 B: 長さ n の 0,1 ベクトル B[1]B[2]…B[n] x  S  B[x] = 1 サイズの下限 log 2n = n bits と一致する rank, selectは O(n) 時間かかってしまう 　⇒ 索引を用いる 1 2 3 4 5 6 7 A 1 3 7 9 10 14 15 B = 1010001011000110 3 7 9 1 n = 16

簡潔索引 決められた操作を実現するためのデータ構造 サイズ: o(R) bits 従来の表現と(ほぼ)同じ操作時間 R: 簡潔表現のサイズ つまり，索引のサイズはほぼ無視できる 従来の表現と(ほぼ)同じ操作時間

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 だが，実際は無視できない 表を使わずに，ビット演算または POPCOUNT 命令 で計算するほうがいい．

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

ベクトルの圧縮法 ベクトルを長さ 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). 注：m << n のときは となることが あり，rank/select の索引のサイズが無視できない