k - Researchmap

情報工学概論
(アルゴリズムとデータ構造)
第7回
11.3.3 万能ハッシュ法
• 運が悪いと，n 個のキーが同じスロットにハッシュさ
れ，平均検索時間が (n) になってしまう
• 万能ハッシュ法 (universal hashing) では，ハッ
シュ関数をランダムに選択する
• どのように意地悪くキーを選択しても，平均として
良い性能を示す．
2
• H: キーの普遍集合 U から値域 {0,1,...,m1}
へのハッシュ関数の有限集合
• H が万能 (universal) ⇔ 全ての異なるキーの
組 x, y  U に対し，h(x) = h(y) となるハッシュ
関数 h  H の個数がちょうど |H|/m
• ハッシュ関数を万能な H の中からランダムに選
んだときに，x と y が衝突する確率が 1/m
• これは h(x) と h(y) が値域 {0,1,...,m1} からラ
ンダムに選択されたときの衝突確率に等しい
3
定理 11.3 h を万能な集合から選択されたハッシュ関
数とする．h を用いて n 個のキーをサイズが m の
ハッシュ表にハッシュする. 衝突はチェイン法で解
消する．このとき，キー k のハッシュ先のリストの長
さの期待値 E[nh(k)] は
高々α（キーが表に存在しないとき）
高々1+α（キーが表に存在するとき）
期待値の計算は全てハッシュ関数に関して行い，
キーの分布については何も仮定しないことに注意
4
証明:異なるキーのペア k, l に対して，指標確率変数
1 (h(k )  h(l ))
X kl  
を定義する．
0 (h(k )  h(l ))
ハッシュ関数の定義より，1つのキーのペアが衝突を
起こす確率は高々 1/m．つまり Pr{h(k)=h(l)}1/m
よって E[Xkl]  1/m.
キー k に対し，k 以外で k と同じスロットにハッシュさ
れるキーの個数を確率変数 Yk で表す．
Yk   X kl
lT
l k
5


1


EYk   E  X kl   EX kl   
 lT
 lT
lT m
 l  k
 l  k
l k
かつ l : l T and l  k　n
• k  T のとき nh( k )  Yk 従って En   EY   n  
h(k )
k
m
• k  T のとき, キー k はリスト T[h(k)] に存在し，
カウント Yk には k は含まれていないので
nh( k )  Yk  1　かつ l : l T and l  k　 n 1
従って Enh ( k ) 
n 1
 EYk  1 
1  1 
m
6
万能ハッシュ関数族の設計
• どんなキー k も 0 から p-1 までの範囲に入るような
十分大きな素数 p を選ぶ．p > m を仮定．
• ha ,b (k )  (( ak  b) mod p ) mod m と定義
ただし a  {1,2,…,p-1}, b  {0,1,,…,p-1}．
m は素数でなくてもいい．
• 定理11.5: ハッシュ関数のクラス
*
H p,m  ha,b : a  Z p , b  Z p は万能である．
• 証明：相異なるキー k, l  Zp を考える．ハッシュ関
数 ha,b に対し
r = (ak+b) mod p
7
s = (al+b) mod p
と置く．


• 命題：r  s
rs  a(kl) (mod p) である．
a も kl も法 p の下で 0 ではない．
p は素数だから右辺の積も 0 ではない．
• (k,l) を固定する．p(p1) 個存在するハッシュ関数
のパラメタのペア (a,b) は， (k,l) を異なるペア (r,s)
に写像する．



a  (r  s) (k  l ) 1 mod p mod p
b  r  ak  mod p
• r  s であるペアは p(p1) 個存在するので， (a,b)
と (r,s) には1対1対応がある．
• (a,b) を一様ランダムに選べば， (r,s) も一様ランダ
ム．
8
• 従って，相異なるキー k と l が衝突する確率は，
法 p の下で相異なる r と s をランダムに選択したと
きに r  s (mod m) となる確率に等しい．
• r を固定すると，r 以外の p1 個の値の中で
r  s (mod m) となる s の個数は高々
p  m 1
p 1
 p
1 
 m   1 
m
m
• よって，s と r が衝突する確率は高々 1/m
• 従って，任意の異なる値 k,l Zp のペアに対し
1
Prha ,b (k )  ha ,b (l ) 
m

つまり H p,m  ha,b : a  Z *p , b  Z p

は万能
9
乱数発生法
• {0, 1, …, p1} の整数を一様ランダムに生成
– C言語
int x;
x = rand() % p; // 整数乱数を p で割った余り
– Fortran
real r
integer x
call RANDOM_NUMBER(r) ! 0 <= r < 1 の実数乱数
x = INT(r * p)
10
乱数の種の設定
• 現在時刻を乱数の種にする
• C言語
srand((int)clock());
srand((int)time(NULL));
• Fortran
call random_seed()
11
12. 2分探索木
• 探索木: SEARCH, MINIMUM, MAXIMUM,
PREDECESSOR, SUCCESSOR, INSERT,
DELETE等が利用できる動的集合用データ構造
• 辞書やプライオリティーキューとして利用できる
• 基本操作は木の高さに比例した時間がかかる
– ランダムに構成された2分探索木の高さ: O(lg n)
– 最悪時: O(n)
• 最悪時でも O(lg n) に改良できる (2色木)
12
12.1 2分探索木とは何か?
• 各節点は key, left, right, p フィールドを持つ
• 2分探索木条件 (binary-search-tree property)
– 節点 y が x の左部分木に属する⇒ key[y]key[x]
– 節点 y が x の右部分木に属する⇒ key[x]key[y]
2
3
5
7
3
2
7
5
5
8
5
8
13
木の中間順巡回
• 木の中間順巡回 (通りがけ順, inorder tree walk
– 根の左部分木に出現するキー集合
– 根のキー
– 右部分木に出現するキー集合の順にキーを出力
• 木の根から辿ると，全てのキーをソートされた順
序で出力できる
5
• (n) 時間
INORDER_TREE_WALK(node x)
{
if (x != NIL) {
INORDER_TREE_WALK(left(x));
print(key(x));
INORDER_TREE_WALK(right(x));
}
}
3
2
3
2
5
5
5
7
7
8
8 14
その他の巡回法
• 先行順巡回 (行きがけ順, preorder tree walk):
根節点を先に出力し，次に左右の部分木を出力
• 後行順巡回 (帰りがけ順, postorder tree walk):
先に左右の部分木を出力し，最後に根節点を出力
POSTORDER_TREE_WALK(node x)
PREORDER_TREE_WALK(node x)
{
{
if (x != NIL) {
if (x != NIL) {
POSTORDER_TREE_WALK(left(x));
print(key(x));
POSTORDER_TREE_WALK(right(x));
PREORDER_TREE_WALK(left(x));
PREORDER_TREE_WALK(right(x)); print(key(x));
}
}
}
}
15
12.2 2分探索木に対する質問操作
• 質問操作は高さに比例した時間で終了する
• 探索: 2分探索木の中から，ある与えられたキーを
持つ節点のポインタを求める(存在しなければNIL)
TREE_SEARCH(node x, data k)
{
if (x == NIL || k == key(x)) return x;
if (k < key(x)) return TREE_SEARCH(left(x),k);
else return TREE_SEARCH(right(x),k);
}
16
探索の正当性
• キー k が見つかったら探索を終了する
• k が key(x) より小さい場合
– 2分探索木条件より，k は x の右部分木にはない
– 左部分木に対して探索を続行する
• k が key(x) より大きい場合
– 右部分木に対して探索を続行する
• 探索する節点は根からのパスになる
– 実行時間は O(h) (h: 木の高さ)
17
• 再帰はwhileループにすることができる
ITERATIVE_TREE_SEARCH(node x, data k)
{
while (x != NIL && k != key(x)) {
if (k < key(x)) x = left(x);
else x = right(x);
}
return x;
}
18
最小値と最大値
• 最小/最大のキーを持つ要素のポインタを
返す
• O(h) 時間
TREE_MINIMUM(node x)
{
while (left(x) != NIL) {
x = left(x);
}
return x;
}
TREE_MAXIMUM(node x)
{
while (right(x) != NIL) {
x = right(x);
}
return x;
}
19
次節点と前節点
• 2分探索木のある節点が与えられたとき，木
の中間順 (inorder) で次/前の節点を求める
• O(h) 時間
TREE_SUCCESSOR(node x)
{
node y;
if (right(x) != NIL) return TREE_MINIMUM(right(x));
y = p(x);
while (y != NIL && x == right(y)) {
x = y;
y = p(y);
}
return y;
}
20
x が右部分木を持つ場合
• x の次節点は，x 以上の要素で最小
⇒ x の次節点は， x の右部分木の最小要素
= TREE_MINIMUM(right(x))
x
2
7
8
5
5
次節点
21
x が右部分木を持たない場合
• x の親を y とする
• x が，x の親の右の子ならば，親は x 以下
• y は，x を左部分木に持つ x の祖先で最も
x に近いもの
次節点
y = p(x);
while (y != NIL && x == right(y)) {
x = y;
y = p(y);
}
return y;
2
9 y
5 yx
3
7
5
yx
8 x
22
定理 12.2 高さ h の2分探索木上の動的集合演
算 SEARCH, MAXIMUM, MINIMUM,
SUCCESSOR, PREDECESSOR は O(h)
時間で実行できる
23
12.3 挿入と削除
• 要素を挿入/削除したあとも2分探索木条件が
満たされる必要がある
• 挿入は比較的簡単
• 削除は複雑
• どちらも O(h) 時間
24
5
挿入
3
z 6
7 y
TREE_INSERT(tree T, node z)
x
{
2
5 z 6
8
node x,y;
y = NIL;
x = root(T);
while (x != NIL) {
// z を挿入する場所 x を決める
y = x;
if (key(z) < key(x)) x = left(x);
挿入場所は必ず葉
else x = right(x);
}
// y は x の親
p(z) = y;
// z の親を y にする
if (y == NIL) root(T) = z;
// T が空なら z が根節点
else if (key(z) < key(y)) left(y) = z; // y の子を z にする
else right(y) = z;
25
}
削除
• 探索木から節点 z を削除する
• z が子を持たない場合
– z の親と z の子を結ぶ
3
z
– z の親 p(z) を変更する
• z が子を1つ持つ場合
3
2
2
5
5
5
7 z
8
8
26
削除: z が子を2つ持つ場合
• z の次節点は左の子を持たない
• z の場所に y を入れ，元の y を削除する
15
z
15
5
6
3
3
12
10
y
6
12
13
10
13
7
7
27
TREE_DELETE(tree T, node z)
{
node x, y;
if (left(z) == NIL || right(z) == NIL) y = z; // z の子の数が1以下
else y = TREE_SUCCESSOR(z);
// z は2つの子を持つ
if (left(y) != NIL) x = left(y); else x = right(y); // x は y の子
if (x != NIL) p(x) = p(y);
// y を削除する
if (p(y) == NIL) root(T) = x;
// y が根なら x を根に
else if (y == left(p(y))) left(p(y)) = x;
// y の親と子をつなぐ
else right(p(y)) = x;
if (y != z) {
key(z) = key(y);
// y の内容を z に移動
// y の付属データを z にコピー
}
return y;
// 不必要な y を回収
28
}
12.4 ランダムに構成された2分探索木
• 2分探索木上の基本操作は O(h) 時間で実行
可
• 要素の挿入削除を繰り返すと探索木の高さ h
は変化する
• n 個の相異なるキーをランダムな順序で挿入し
た2分探索木の高さを解析する
• 高さの期待値は O(lg n)
29
• 仮定
– 入力キーの n! 種類の順列がどれも等確率で出現する
– 全てのキーは異なる
• 確率変数の定義
– Xn: n 個のキー上のランダムに構成された2分探索木の
高さ
– Yn = 2Xn 指数高さ
– Rn: n 個のキーの中での根のキーの順位 (rank)
Rn = i なら，根の左部分木は i1 個のキー上の
ランダムに構成された2分探索木，右部分木は
ni 個のキー上のランダムに構成された2分探索木
30
• 2分探索木の高さは根の左右の部分木の高さの
大きいほう+1． Rn = i のとき
X n  max X i 1 , X n i  1
Yn  2 max Yi 1 , Yn i 
• Y1 = 1. 便宜上 Y0 = 1 と定義する.
• 指標確率変数 Z n,1 , Z n, 2 ,, Z n,n を次のように定義
Rn  i 
1
Z n ,i  IRn  i  
0 それ以外
• Rn の値は {1,2,…,n} の任意の要素を等確率で
取るから，Pr{Rn = i} = 1/n (i=1,2,…,n) よって
1
EZ n ,i  
n
31
• 根の順位が i のときだけ Zn,i = 1 になるから
n
Yi   Z n ,i 2 max Yi 1 , Yn i 
i 1
• E[Yn] が多項式であることが示せれば，
E[Xn] が O(lg n) であることが示せる．
• Zn,i は Yi1 とも Yni とも独立
– 根の左部分木内の各要素は根よりも小さい，つまり
順位が i より小さい i1 個のキー上のランダムに構成
された木である．
– この部分木は順位の制約がないi1 個のキー上のラン
ダムな木と同じ
– 部分木の高さ Yi1 と根の順位 Zn,i は独立
32
 n

EYi   E  Z n ,i 2 max Yi 1 , Yn i 
 i 1

  EZ n ,i 2 max Yi 1 , Yn i 
n
(期待値の線形性)
i 1
  EZ n ,i E2 max Yi 1 , Yn i 
n
(独立性)
i 1
2 n
  Emax Yi 1 , Yn i 
n i 1
2 n
  EYi 1   EYn i 
n i 1
4 n 1
  EYi 
n i 0
33
•
1  n  3

EYn   
4 3 
を示す
1  3 1
0  Y0  EY0     
4  3 4
1 1  3 
  1
1  Y1  EY1   
4 3 
4 n 1
EYn    EYi 
n u 0
4 n 1 1  i  3 

  
n u 0 4  3 
1  n  3

 
n 4 
1  n  3

 
4 3 
34
• 関数 f(x) = 2x は上に凸であるから
2
E X n 
   EY 
E2
Xn
n
• 以上より
1  n  3
  Olog n 
EX n   log EYn   log 
4 3 
• 定理12.4 n 個のキー上のランダムに構成さ
れた2分探索木の高さの期待値は O(lg n).
35
36
補題 13.3 空の2分探索木に n 個の相異なるキーk1,
k2,...,knをこの順序で挿入して得られる木をTとする．
1 i < j  n に対し，T の中で ki が kj の先祖である
ための必要十分条件は
ki = min{kl: 1 l  i かつ kl > kj}
(k1から ki で kj より大きいものの中で最小) または
ki = max{kl: 1 l  i かつ kl < kj}
15
(k1から ki で kj より小さいものの中で最大)
6
挿入順 (一例)
15, 6, 12, 3, 10, 7, 13
12
3
10
kj 7
ki
13
37
証明: (必要性) ki が kj の先祖だと仮定する． kj <
ki とし， ki = min{kl: 1 l  i かつ kl > kj} が成り
立たないと仮定する．つまり， kj < km < ki となる
km (m < i) が存在する．
kj は km の左の部分木， ki は km の右の部分木に
なり， ki が kj の先祖という仮定に矛盾する．
kj > ki の場合も同様．
15
3
kj
2
km
5
6
ki
12
3
10
kj 7
ki
13
38
証明: (十分性) ki は, k1から ki で kj より大きいもの
の中で最小と仮定する．探索木の根から ki までの
パス上の節点 x を考える．
ki < x のとき， kj < ki より kj < x
x < ki のとき， x > kj とすると x は仮定を満たさない
ので x < kj
15
よって根から kj へのパスは ki を通る．
x
つまり ki は kj の祖先
6
12
3
10
kj 7
ki
13
39
系13.4 空の2分探索木に n 個の相異なるキーk1,
k2,...,kn をこの順序で挿入した結果を T とする．
kj (1 j  n) に対し，Gj と Lj を
Gj = {ki: 1 i  j かつ kl > kj である全ての l  i に
対して kl > ki > kj}
Lj = {ki: 1 i  j かつ kl < kj である全ての l  i に
対して kl < ki < kj}
とする．このとき，根と kj を結ぶパス上に現れる
キーの集合は Gj  Lj に一致し， kj の T におけ
る深さ d(kj, T) は
d(kj, T) = |Gj| + |Lj|
40
Gj
21
Lj
9
25
12
4
10
3
7
29
19
26
17
kj
6
18
キー 21 9 4 25 7 12 3 10 19 29 17 6 26 18
Gj’ 21
25
19 29
←kj より大きい
Gj 21
19
←最小値を更新
Lj’
9 4
7 12 3 10
←kj より小さい 41
Lj
9
12
←最大値を更新
Gj のサイズの解析
• Gj: kj より大きいキーの中で，今までの最小値を
更新したものの集合
• n 個の異なるキーが1つずつ動的集合に挿入さ
れたと仮定する
• キーの全ての順列が同じ確率で出現するときに，
集合の最小値が何回変化するか求める
• i 番目に挿入されたキーを ki とする (1 i  n)
• 最初の i 個の中で ki が最小値の確率 = 1/i
42
• 集合の最小値の変更回数の期待値は
n
1
 Hn

i 1 i
補題 13.5 n 個の相異なる数のランダム順列を
k1,k2,...,kn とし，|S| を，集合
S={ki: 1  i  n, かつ, 全ての l < i についてkl >ki}
の大きさを表す確率変数とする．このとき
Pr{|S|  (+1)Hn}  1/n2
(  4.32 は (ln  1) = 2 を満たす数)
43
証明: 集合 S の大きさは n 回のベルヌーイ試行
から決定されるとみなすことができる．
i 回目の試行が成功する確率は 1/i．
以下の定理を使う．
定理 6.6 i = 1,2,...,n に対して i 番目の試行の
成功確率が pi である n 回のベルヌーイ試行
の列を考える．Xを全成功回数を表す確率変
数とし， = E[X] とおく．このとき r >  に対し
r
 e 
PrX    r   
 r 
44
 > 1 より
Pr| S | (   1) H n   Pr| S |    H n 
H n
 eH n 

 
 H n 
(1 ln  ) H n
e
 e (ln  1)  ln n
 n (ln  1) 
 1/ n2
45
定理 13.6 n 個の相異なるキー上のランダムに構
成された2分探索木の高さの平均は O(lg n)
証明 n 個のキー上のランダム順列をk1,k2,...,kn
とし，空の2分探索木にこれらをこの順序で挿入
した結果を T とする．与えられたキー kj の深さ
d(kj,T) が少なくとも t である確率を考える．
系13.4 より， kj の深さが少なくとも t ならば，集合
Gj, Lj のどちらかはサイズが t/2 以上．よって
Pr{d (k j , T )  t}  Pr{| G j | t / 2}  Pr{| L j | t / 2}
46
Pr{| G j | t / 2}


 Pr ki : 1  i  jかつkl  ki  k j for all l  i  t / 2
 Prki : i  nかつkl  ki for all l  i  t / 2
 Pr| S | t / 2
Pr{| L j | t / 2}  Pr| S | t / 2
Prd (k j , T )  t  2 Pr| S | t / 2
t = 2(+1)Hn とすると
Prd (k j , T )  2(   1) H n  2 Pr| S | (   1) H n 
 2/n
2
47
2分探索木には n 個の節点が存在する．少なくと
も1つの節点が高さ 2(+1)Hn 以上である確率
は高々 n(2/n2) = 2/n．
2分探索木の高さは確率 (12/n) 以上で
2(+1)Hn未満，確率 2/n 以下で n 以下．よって
高さの期待値は高々
(2(   1) H n )(1  2 / n)  n(2 / n)  O(lg n)
48

Download Report