160407駒場

数理工学のすすめ
東京大学大学院情報理工学系研究科
数理情報学専攻
定兼邦彦
2016年4月7日
http://researchmap.jp/sada/resources/
自己紹介
•
•
•
•
•
•
•
•
名前：定兼邦彦（さだかねくにひこ）
所属：東京大学大学院情報理工学系研究科数理情報学専攻
経歴： 1991年理1入学，2000年理学系研究科情報科学専攻修了
2000年東北大学大学院情報科学研究科助手
2003年九州大学大学院システム情報科学研究院助教授
2009年国立情報学研究所准教授
2014年東京大学大学院情報理工学系研究科教授
研究分野：データ圧縮，データ構造，情報検索
•
•
•
•
最近の研究：
ビッグデータ処理
簡潔データ構造
並列アルゴリズム
2
アルゴリズムとデータ構造
• アルゴリズム (algorithms, 算法): 計算等の手順
– 数を小さい順に並べる (ソート)
– Webのキーワード検索
– 最短経路探索
• データ構造 (data structures): 計算機にデータを
格納する方法
– 配列，リスト，ハッシュ，2分木
• アルゴリズムやデータ構造を工夫すると，
同じ問題が高速に解けるようになる
3
ビッグデータ処理の問題点
• 大量のデータがあるとき，それを圧縮することで
ディスク容量や通信コストを抑えられる
• しかし圧縮してあるデータを使うときは復元しな
ければならない
データを圧縮したまま使えないか？
• データを高速に処理するにはデータ構造を用い
るが，そのサイズも問題になる
データ構造も圧縮できないか？
4
モールス符号 (信号)
•
•
•
•
•
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
－－・・
5
• s から t へ矢印の通りに移動するルートを
表現するには
t
Q
s
P
P:    
Q:    
0010110
1100001
7ビットで表現できる
もっと小さくできる?
6
• s から t へ矢印の通りに移動する行き方は
何通り?
• ルートは4個の→と3個の↑で表現できる
• 逆に，4個の→と3個の↑をどういう順に並べても，
それは s から t へのルートになっている
t
• 行き方は
通り
7 C3  7 C4  35
Q
7 7
      35
 3  4
• 26 = 64 > 35 なので，
6 ビットで表現できる
s
P
P:    
Q:    
• s から t へのルートを 6 ビットで表現するには
どう符号化すればいいか
• 各ルートを 0 から 34 の整数で表現する
 6
• s から最初に右に行くルートは    20 通り
 3
– 0 から 19 の整数で表現する
• s から最初に上に行くルートは
– 20 から 34 の整数で表現する
6
   15
 2
通り
t
Q
s
P
8
• s から最初に右に行くルート20個を考える
 5
• 次に右に行くルートは  3   10 通り
 
– 0 から 9 の整数で表現する
• 次に上に行くルートは
5
   10
 2
通り
– 10 から 19 の整数で表現する
t
s
P
9
• s から右，右に行くルート10個を考える
 4
• 次に右に行くルートは  3   4 通り
– 0 から 3 の整数で表現する
• 次に上に行くルートは
 4
   6
 2
通り
– 4 から 9 の整数で表現する
t
s
P
10
• s から右右上に行くルート6個を考える
 3
• 次に右に行くルートは  2   3 通り
 
– 4 から 6 の整数で表現する
• 次に上に行くルートは
 3
   3
1
通り
– 7 から 9 の整数で表現する
t
s
P
11
• s から右右上右に行くルート3個を考える
 2
• 次に右に行くルートは  2   1 通り
 
– 4 から 4 の整数で表現する
• 次に上に行くルートは
 2
   2
1
通り
– 5 から 6 の整数で表現する
t
s
P
12
• s から右右上右上に行くルート2個を考える
1
• 次に右に行くルートは 1  1 通り
 
– 5 から 5 の整数で表現する
• 次に上に行くルートは
1
   1
 0
通り
– 6 から 6 の整数で表現する
t
s
P
13
• 結局，経路 P は整数 6 で表される
 4   2  1
         4  1  1  6
 3   2  1
• 同様に，経路 Q は整数 30 で表される
 6  5  0
         20  10  0  30
 3  2  1
t
Q
s
P
14
• 一般に，上に r 回，右に nr 回移動する場合，
ルートの数は  n 
r
 
• 最初に右に行くルートの数は
• 最初に上に行くルートの数は
 n   n  1  n  1
   
  

 r   r   r  1
 n  1


 r 
 n  1


 r  1
• n 個の矢印のうち，↑の位置を nr,nr1, …,n1 とすると
ルートは整数  nr    nr 1      n1  で表される
 r   r  1
  

1
 
15
ルートの復元
•
•
•
•
ルートを表す整数 30 から，ルートを復元する
 6
s から最初に右に行くルートは  3   20 通り
 
30>20 なので，最初は上に行っている
最初に上に行った点からルート 3020 = 10 を復元
t
Q
s
P
16
圧縮率
• 上に r 回，右に nr 回移動する場合
– n 個の矢印→↑…で表現: n ビット
– 整数に変換して表現: 
 n  ビット
•

 n 
n


log

log
2
 2    2   n
 r 

log 2  
 r 

なので，変換する方が小さい

 n 
n
n
log 2    r log 2  n  r  log 2
r
nr
 r 

 nH  nr  エントロピー
なので，r が小さければ圧縮率が高くなる
(もしくは nr が小さければ)
17

 n 
log 2  
 r 

• 厳密には，ルートを表す
ビットの値の他に
n と r の値も保存する必要がある

 n 
• 合計で log  r   2log n  2log n  2 ビット

2

2
2
18
n が大きい場合
• n > 10億
n
•  r  を計算するには，大きい数の掛け算，割り算が
必要になり，遅いしメモリも多く必要となる
t
s
19
• ルートを一定の長さ l ごとに区切る
• 各部分ルートに対し，↑の数を記録する
t
r4 = 2
r3 = 5
l=8
r2 = 2
r1 = 3
s
20
• 各部分ルートは

 l 
log
 2  
 ri 

ビットで表現できる

 4 
log 2  
 2 


 8 
log
 2  
 5 

r4 = 2
r3 = 5

 8 
log
 2  
 3 

r2 = 2
t

 8 
log 2  
 2 

l=8
r1 = 3
s
21
•

 l 
 l  
 l  




log

log

log
 2    2    2    
 r1  
 r2  
 r3 

はどれくらいの大きさ?

 l 
 l  
 l  
log 2    log 2    log 2    
 r1  
 r2  
 r3 

l
l
l




 log 2    1  log 2    1  log 2    1  
 r1 
 r2 
 r3 
 l   l   l   n 
 log              
  r1   r2   r3    l 
 l  l  l   n
   
 log 
r

r

r


1 2 3
 l 
n n
 log     
r l 
• 分割してもサイズは
(あまり)増えない
22
• s から t への行き方は何通り?
t
s
23
• 5通り
24
• →と (, ↑ と ) を対応させると，各ルートは括弧
の対応の取れた(バランスした)括弧列を表す
(()())
((()))
()(())
()()()
(())()
25
• バランスした括弧列は，深さが常に 0 以上の
経路と対応する
((()))
(()())
()(())
(())()
()()()
26
バランスした括弧列と順序木には1対1対応がある
((()))
(()())
()(())
(())()
()()()
27
順序木の圧縮
• 木をバランスした括弧列で表現する
– 一番外側に括弧を追加する
• n 点の木は長さ 2n の括弧列で表現できる
• もっと短い表現は無いか
n=4
(((())))
((()()))
((())())
(()(()))
(()()())
28
順序木の個数
• n 点の順序木の個数を Tn とする
• Tn = (長さ 2n2 のバランスした括弧列の数)
< (長さ 2n2 の全ての括弧列の数) = 22n2
• Tn = (縦横n1マスずつの格子で対角線を
またがない経路の数)
1  2n  2 
  Cn 1
Tn  
n  n 1 
• Cn はカタラン数 (Catalan number) と呼ばれる
n=4
29
カタラン数
 2n   対角線を跨ぐ

Cn     
 n   s  t 経路の数
t
u
s’
s
• 対角線をまたぐ s-t 経路の数を求める
n=3
– 対角線を初めて跨いだ点を u とする
– s から u の経路を(紫の線で)折り返す
 2n 

– s’ から t の全ての経路の数と等しい 
 n 1
 2n   2n 
1  2n 
 
 
Cn     
 n   n  1 n  1  n 
30
順序木の表現のサイズ
1  2n 
4n
   3 / 2
Cn 
n 1  n  n

•
•
•
•
(スターリングの公式より)
b ビットで表現できるものは最大 2b 種類
n 点の順序木は Cn1 種類ある
順序木を表現するには log 2 Cn  2n ビット必要
つまり，括弧列による順序木の表現は
ほぼ最適サイズ
31
カタラン数の漸化式
C0  1
Cn 1 
2(2n  1)
Cn
n2
n
Cn 1   Ci Cn i
i 0
32
データの簡潔表現
• サイズが情報理論的下限に(ほぼ)一致する表現
• 入力がL通りのとき，情報理論的下限はlog L bits
• 例1: 集合 S  {1,2,...,n} のサイズの下限
– log 2n = n bits

{1}
{2}
{3}
n=3
{1,2} {1,3} {2,3}
{1,2,3}
log の底は 2
33
• 例2: n ノードの順序木
1  2n  2 
  2n  log n  bits
log 
n  n 1 
n=4
• 例3: n 文字の文字列
– n log  bits (: アルファベットサイズ)
34
集合に対する演算
• 集合 S  {1,2,...,n} に対して次の値を求めたい
– 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
35
集合の簡潔表現
•
•
•
•
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
A 1
3
7
9 10 14 15
1 3
5
6
7
7 9
B = 1010001011000110
n = 16
36
簡潔索引
• 決められた操作を実現するためのデータ構造
• サイズ: o(R) bits
– R: 簡潔表現のサイズ
– つまり，索引のサイズはほぼ無視できる
• 従来の表現と(ほぼ)同じ操作時間
37
Rankの簡潔索引1
• B を長さ log2 n のブロックに分割
• ブロックの境界での rank(x)の値を R に格納
x / log2 n 
rank ( x)   B[i]   B[i] 
x
i 1
i 1
x

 B[i]

i  x / log2 n 1
R[x/log2 n]
• Rのサイズ
n
n

log
n

bits
2
log n
log n
• rank(x): O(log2 n) 時間
38
Rankの簡潔索引2
• 各ブロックを長さ ½ log n の小ブロックに分割
• 小ブロックの境界での rank の値を R2 に格納
x / 12 logn 
x
x / log2 n 
rank ( x)   B[i ]   B[i ]   B[i]   B[i ]
i 1
i 1
i  x / 12 log n 1
i  x / log2 n 1
x
• R2のサイズ
R1[x/log2 n]
R2[x/log n]
n
4n log log n
2
 log log n  
bits
1
log n
2 log n
• rank(x): O(log n) 時間
39
Rankの簡潔索引3
• 小ブロック内での問い合わせに対する答えを
x
予め求め，表に格納しておく
x
 B[i]
i  x / 12 log n 1
½ log nビットの
Bの全パタン
• 表の大きさ
2
1 log n
2

 12 log n  log  12 log n 
 O n log n log log n
 n log log n 
 bits
 o
 log n 

000
001
010
011
100
101
110
111
0
0
0
0
0
1
1
1
1
1
0
0
1
1
1
1
2
2
2
0
1
1
2
1
2
2
403
定理：長さ n のビットベクトルでのrankは
語長 (log n) bits のword RAM上で
n + O(n log log n/log n) bits を用いて
O(1) 時間で求まる．
注：小ブロックでのrankを計算する表の大きさは
O n log n log log n  bits だが，実際は無視できない
表を使わずに，ビット演算または POPCOUNT 命令
で計算するほうがいい．
41
Selectの簡潔索引
• rank同様にやってもうまくいかない
–
–
–
–
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通りのデータ構造を使い分ける
42
• 大ブロックの長さが logc n を超えるとき
– log2 n 個の1の位置をそのまま格納
– 1つの大ブロックで log 2 n  log n  log 3 n bits
n
– そのような大ブロックは最大
個
c
log n
n
3

log
n bits
– 全体で log c n
n
– c = 4 とすると
bits
log n
43
• 大ブロックの長さ m が logc n 以下のとき
–
–
–
–
長さ ½ log n の小ブロックに分割
小ブロックを葉に持つ完全 log n 分木を構築
木のノードには，その子孫のベクトルの1の数を格納
大ブロック内の 1 の数は log2 n
→ 各ノードの値は 2 log log n bits
log n
9
3
1
2
4
0
1
1
O(c)
2
2
1
0
1
B = 100101000100010011100000001
m  logc n
44
• 木の高さは O(c)
• ノードに格納する値は大ブロック全体で
 cm log log n 
 bits
O
log n


• ベクトル全体で
 cn log log n 
 bits
O
 log n 
• select(i) を求めるには，木の根から探索する
– 子ノードの情報は log n  2 log log n  Olog n bits で
表現できるので，表引きで訪れる子が決まる
• 探索時間は O(c) つまり定数
45
定理：長さ n のビットベクトルでの rank と select は
語長 (log n) bits のword RAM上で n+O(n log log n
/log n) bits を用いて O(1) 時間で求まる．
注：子ノードの探索では log n  2 log log n  Olog n bits
つまり (log log n)2 = O(log n) を仮定している．
これは小さい n では成立しない
補足：大ブロック内の select の索引を用いて
rank を計算できる
木を葉から根にたどり，rankの和を求める
46
ベクトルの圧縮法
• ベクトルを長さ l = ½ log n の小ブロックに分割
• i 番目の小ブロック Bi 内の 1 の数を mi とする
– 小ブロックは
  l 
log l  log  
  mi 
1の数
bits で表現できる
1の数が決まったときの全パタンの数
• 全ブロックの合計は

  l   n / l 
 l  



log l  log      log l  log    1



i 0 
 mi  
  mi   i 0 
n/l
 l  n
 log     1  log l 
l
i  0  mi 
n
 n log log n 

 log    O
m
 log n 
n/l
47
• rank, select の索引はベクトルが圧縮されていない
ときと全く同じで，O(n log log n /log n) bits
• 小ブロック内の 1 の数は select の索引に格納済
• 圧縮された小ブロックへのポインタが必要
• Bi へのポインタを pi とする
– 0 = p0 < p1 < <pn/l < n (圧縮されているので n 未満)
– pi  pi1  ½ log n
• i が log n の倍数のときに pi をそのまま格納
n
n
 log n 
bits
2
log n
log n
• それ以外のときは差分で格納
n
1




log
2 log n  log n   O n log log n / log n bits
1
2 log n
48
定理：長さ n, 1の数 m のビットベクトルは
n
 n log log n 
 bits で表現でき，
log    
 m

log n

rank0, rank1, select0, select1 は語長 (log n) bits の
word RAM上で O(1) 時間で求まる．
データ構造は O(n) 時間で構築できる．
このデータ構造は FID (fully indexable dictionary)
と呼ばれる (Raman, Raman, Rao).
n
 n log log n 
注：m << n のときは log  m    log n  となることが
 


あり，rank/select の索引のサイズが無視できない 49

Download Report