アルゴリズムとデータ構造

(1)

2015/12/02 1

アルゴリズムとデータ構造

第 7 回：探索のためのデータ構造（ 3 ）

前半：最適 2 分探索木の構築（発展）

後半：ハッシュ表（基本）

(2)

第 7 回探索のためのデータ構造（ 2 ）

n

今日の内容：

¨

今日は短い内容が二つあります。

¨

前半：（発展内容）最適

2

分探索木を学ぼう。

n 「発展内容」なので、わからないときは飛ばしても良いです。（試験にでません）

n これは、検索のみで挿入と削除をしないときに、平衡二分探索木（第6回）よりも検索時間が短くなるデータ構造を見つける話です。表を埋めることで、計算を高速に行う「動的計画法」の例です。興味ある人はどうぞ！

¨

後半：（基本内容）「ハッシュ表」を学ぼう。

n ハッシュ表は、平均的にO(1)時間で探索できる、実用的に効率が良い探索データ構造です。

n

ポイント

¨

前半：最適

2

分探索木の計算は、本当はけっこう難しいが（全部候補の木を探すと指数時間かかる）、表を埋めていくことで、高速に計算できる。

¨

後半：「ハッシュ表」では、「ハッシュ関数」を用いて検索する方法を理解しよう。

¨

後半：ハッシュ表には、衝突回避法の違いで、「外部ハッシュ法」と「内部ハッシュ法」があります。「内部ハッシュ法」は、簡単な仕組みで手品のようにうまく、衝突を回避できます。

¨ C++

の

unordered_map

や、

java

の

HashMap

は、ハッシュ表で実装されています。

アルゴリズムとデータ構造

2

(3)

2015/12/02 3

アルゴリズムとデータ構造

第 7 回前半：探索のためのデータ構造（ 3 ）

前半：最適 2 分探索木の構築（発展）

(4)

2015 2015/12/02

4 前回の復習

辞書に適したデータ構造とは？

次の３つの基本操作を伴う集合

S

を辞書

(dictionary)

という。

1. member(x,S) : x∈S

ならば

yes, x S

ならば

no

を出力

2. Insert(x,S) : SをS∪{x}に更新

3. delete(x,S) : S

を

S

－

{x}

に更新

∈

要するに検索と挿入と削除が高速に行える

データ構造

１．整列された配列

member

最悪時間計算量

O(log n)

insert, deleate

O(n)

これは問題！

２．２分探索木

member,insert,delete

O(n)

平均時間計算量

O(log n)

挿入の順番がランダム３．平衡２分探索木と仮定

AVL

木（全ての節点において、左部分木と右部分木の高さの差が１以内の２分探索木）

member,insert,delete

O(log n)

(5)

5 本日の内容

Q

１．平衡２分探索木よりもっと良い２分探索木はあるのか？

↓

検索のみの高速化なら可能！

検索される要素の確率分布が分かっているときに、その確率分布に対して，

検索にかかる時間が平均的に最も少なくなるような木を構築することが可能

↑

最適２分探索木

Q2.

検索・挿入・削除の時間計算量は、

O(log n)

の壁を破れないか？

平均時間計算量なら可能！

ハッシュ表を用いれば、平均時間計算量を

O(1)

（定数時間）で行える。

ただし、ハッシュ表のサイズ

m

を格納要素数

n

のオーダー

O(n)

にとった場合に

O(1)を実現可能

ハッシュ表は最も実用的な辞書に適した構造

(6)

最適 2 分探索木の構築問題

n

入力：

¨ n

個のデータ値

a ₁ < a ₂ <…< a _n

（実数値）

¨

データ値の出現確率の表

P

（右図）

n

タスク：

¨ n

個のデータ値を格納するすべての二分探索木の中から，表の出現確率に関して平均探索コストが最小となる

2

分決定木

T

（最適

2

分探索木）を求めよ

アルゴリズムとデータ構造有村博紀

6

補足スライド

値の生成確率の表

P

(-∞,a1) 0.050

a1 0.050

(a1,a2) 0.050

a2 0.025

(a2,a3) 0.050

a3 ^0.125

(a3,a4) 0.050

a4 0.250

(a4,a5) 0.050

a5 0.075

(a5,a6) 0.050

a6 0.125

(a6,+∞) 0.050 1.000

n

補足

¨

平均探索時間は

,

値

X

を格納する頂点深さ

cost(X)

として

Cost(T) := Σ _{X:値または区間} P(X) cost(X)

¨

素朴な方法は，

S

を格納するすべての可能な二分探索木をすべてに対する総当たり．

n 要素は昇順にソートされているとして良く，木の形だけ．

n 要素数がnのすべての可能な2分探索木の総数

= n

ⁿくらい

¨

もっと効率よく解けないか？

=> 「動的計画法」

プログラミングコンテストの問題風に*

*) 過去のプログラミングコンテストによく出題されている（例：KUPC2012）

a

₄

a

₃

a

₆

a

₁

a

₂

a

₅

v

₀

v

₁

v

₂

v

₃

v

₄

v

₅

v

₆

(7)

基本的アイディア

n

ソートした

n

個のデータ値

a ₁ < a ₂ <…< a _n

仮定を格納した長さ

n

の配列

A

を考える

n

一つの部分木は，配列の部分区間

A[i..j]

に対する最適部分木を求めれば良い．

n 2

分探索木は，真ん中の要素

A[k]

を選べば根が決まる

n A[i..j]

は，真ん中の要素

A[k]

と二つの部分

A[i..k-1]

と

A[k+1..j]

に分割できる．

n

それぞれの最適木を求めれば良い？

n

表にして求める．

n

何個のマス目が必要？

7 a

_k

T _i,k-1 T _k+1,j

(8)

2015 2015/12/02

8 最適 2 分探索木の定義 (1/2)

S={a ₁ , a ₂ ,…,a _n } :

格納要素。ただし

a ₁ <a ₂ <

・・・

<a _n

とする。

次の確率

(a ₁ ,...,a _n ), (β ₀ ,...,β _n )

が与えられていると仮定。

P{x=a _i }=α _i (i=1,2,…,n)

P{x<a ₁ }=β ₀ , P{a _i <x<a _i+1 }=β _i (i=1,2,…,n-1), P{a _n <x}=β _n T :S

を節点要素としてもつ２分探索木

T

の各節点がちょうど２つの子をもつように

n+1

個の架空の点（外点）を導入。

節点

a _i :

要素

a _i

が割り当てられている節点

外点

v ₀ :x<a ₁

のときに

member(x,S)

により（仮想的に）たどり着く外点

外点

v _i (i=1,2,…,n-1): a _i <x<a _i+1

のときに

member(x,S)

によりたどり着く外点外点

v _n :x>a _n

のときに

member(x,S)

によりたどり着く外点

a

₄

a

₃

a

₆

a

₁

a

₂

a

₅

v

₀

v

₁

v

₂

v

₃

v

₄

v

₅

v

₆

(9)

9 最適 2 分探索木の定義 (2/2)

S⊆X:

全順序集合

最適２分探索木

(optimal binary search tree)

とは検索コスト

(member(x,S)

の平均時間計算量

)

が最小の２分探索木

最適２分探索木は次式で定義されるコスト

c

を最小化する２分探索木

T

である。

c(T)=Σα _i (depth _T (a _i )+1)+Σβ _i depth _T (v _i )

ただし、

depth _T (u)

は２分探索木

T

における節点

u

の深さを表すものとする。

i=1

n n

i=0 ←

平均比較回数

a

₄

a

₃

a

₆

a

₁

a

₂

a

₅

v

₀

v

₁

v

₂

v

₃

v

₄

v

₅

v

₆

(10)

2015 2015/12/02

10 最適２分探索木の構成法

T _i,j :

節点

a _i , a _i+1 ,…,a _j

からなる２分探索木

T _i,j

のコストを同様に次のように定義する。

c(T _i,j )=Σα _p (depth _Ti,ｊ (a _p )+1)+Σβ _p depth _Ti,j (v _p )

木

T _i,j

は根が節点

a _k

であれば、ある木

T _i,k-1

と木

T _k+1,j

を用いて、左図のように表現できる。

c _i,j =min _Ti,j c(T _i,j )

と定義する。最終的には

c(T)=c _1,n

となるような木

T

を求めればよい。

c _i,j =min min min ( ^c(T i,k-1 )+Σ α _p + Σ β _p + α _k + c(T _k+1,j ) + Σ α _p + Σ β _p )

p=i

j j

p=i-1

a

_k

T _i,k-1 T _k+1,j

k:i≦k≦j T

_i,k-1

T

_k+1,j

p=i p=i-1 p=k+1 p=k

k-1 k-1 j j

P{a _i-1 <x<a _k } P{a _k <x<a _j+1 }

=min (c _i,k-1 + c _k+1,j ) + Σα _p + Σβ _p

k:i≦k≦j p=i

j

p=i-1 j

よって最適な木

T _i,j

^のコスト

c _i,j

^{はより小さな最適な木}

T _i,k-1 , T _k+1,j (i ≦ k ≦ j)

^の

コスト

c _i,k-1 , c _k+1,j

から求めることができる。

(11)

11 最適２分探索木の構成法 (

続き

)

c _i,j =min (c _i,k-1 + c _k+1,j ) + Σα _p + Σβ _p

k:i≦k≦j p=i

j

p=i-1 j

T _i,i-1

は

a _i-1 <x<a _i

に対する木であり外点

v _i-1

のみからなる木である。

コストの定義よりc

_i,i-1 =c(T _i,i-1 )=0となる。

したがって、まとめると以下の漸化式が得られる。

c _i,i-1 =0

for 1≦i≦j≦n for 1≦i≦n

この漸化式より、

c _1,n

およびそのコストを達成する最適２分探索木

T

を動的計画法を使って時間計算量

O(n ² )

で計算可能。

動的計画法とは

対象となる問題の部分問題の解を計算して記憶しておき、

それらを用いて元の問題の解を計算する技法

上記漸化式の場合、

c _i,j

の値の計算には、

j’-i’<j-i

である

c _i’,j’

しか使わない。したがって、

j-i

の値が小さな

c _i,j

から順に計算すれば各

c _i,j

を

O(j-i+1)

で求めることができる。

(12)

2015 2015/12/02

12

例

^S={a ¹ ^,a ² ^,a ³ ^,a ⁴ ^,a ⁵ ^}

α ₁ =α ₂ =α ₃ =0.1, α ₄ =α ₅ =0.2, β ₀ =β ₁ =β ₃ =β ₄ =β ₅ =0.05

の場合

0

0 0 c _i,j

^の値

k=1 0.2

k=2 0.2

k=3 0.2

k=4 0.3

k=5 0.3

k=1 0.55

k=2 0.55

k=4 0.85

k=2 0.9

k=4 1.2

k=2 1.6

k=4 1.7 k=4 1 2.2

2 3 4 5 6 i

0 1 2 3 4 5 j

-1 0

1 2

3 4 j-i

k=3 1.1 k=4 0.65

c _2,4 = min {c _2,1 +c _3,4 , c _2,2 +c _4,4 , c _2,3 +c _5,4 } + (α ₂ +α ₃ +α ₄ ) + (β ₁ +β ₂ +β ₃ +β ₄ )

= min {0.65, 0.5, 0.55}

+ 0.4 + 0.2

= 1.1

(

最小は

c _2,2 +c _4,4

で

k=3

のとき）

a

₄

a

₂

a

₅

a

₁

a

₃

最適２分探索木は

(13)

13 最悪時間計算量は O(n ² )

j-i=h

の場合、

n-h

個の

c _i,j

を計算しなければならない。

１つの

c _i,j

を求めるのに

h+1

個の候補から最小値を計算するので、全体では

O(Σ(n-h)(h+1))=O(n ³ )

となるが、最小候補をもっと絞り込むことができるため工夫をすれば

O(n ² )

の最悪時間計算量で計算可能である。

c _i,j

を最小にする候補の木

T _i,j

の根節点

a _k

は、

i≦k≦j

よりさらに絞り込めて

r _i,j-1 ≦k≦r _i+1,j

であることが知られている。ただし、

r _i,j

は最適な木

T _i,j

の根節点の

インデックス、つまり

a _m

を最適な木

T _i,j

の根節点とすると

r _i,j =m

である。

この事実を使うと上の計算は以下のようになる。

h=0 n-1

O (r _i+ _1,i+h − r _i,i+h−1 + 1)

i=1 n−h

∑

h=0 n−1

# ∑

$ % &

' ( = O (r _n−h+ _1,n − r _1,h + n − h

h=0 n− 1

∑ ⁾

#

$ % &

' ( = O(n ² )

(14)

2015/12/02

2015 14

アルゴリズムとデータ構造

第 7 回：探索のためのデータ構造（ 3 ）

後半：ハッシュ表

(15)

15 前回の復習

辞書に適したデータ構造とは？

次の３つの基本操作を伴う集合

S

を辞書

(dictionary)

という。

1. member(x,S) : x∈S

ならば

yes, x S

ならば

no

を出力

2. Insert(x,S) : SをS∪{x}に更新

3. delete(x,S) : S

を

S

－

{x}

に更新

∈

要するに検索と挿入と削除が高速に行える

データ構造

１．整列された配列

member

O(log n)

insert, deleate

O(n)

これは問題！

２．２分探索木

member,insert,delete

O(n)

O(log n)

挿入の順番がランダム３．平衡２分探索木と仮定

AVL

木（全ての節点において、左部分木と右部分木の高さの差が１以内の２分探索木）

member,insert,delete

O(log n)

(16)

2015 2015/12/02

16 本日の内容

Q2.

検索・挿入・削除の時間計算量は、O(log n)の壁を破れないか？

平均時間計算量なら可能！

ハッシュ表を用いれば、平均時間計算量を

O(1)

（定数時間）で行える。

ただし、ハッシュ表のサイズmを格納要素数nのオーダーO(n)にとった場合に

O(1)

を実現可能

ハッシュ表は最も実用的な辞書に適した構造

(17)

17 ハッシング

ハッシュ表

(hash table)

とは

ハッシュ関数

h

^{を使って、要素}

x

^{があらかじめ準備した}

m

^{個の場所のうち、}

位置

h(x)

^{に格納される表}

[ハッシュ関数のもつべき性質]

・関数値の高速な算出が可能である

・要素となりうる

x

に対して、ハッシュ値

h(x)

が

m

個の位置にできるだけ偏りなく分布すること

[よく用いられるハッシュ関数]

・

x

が整数の場合

h(x)=x%m (x

を

m

で割った余り

)

・xが文字列の場合

h(x)=(Σord(x[i]))%m

ただし、

ord(a)

は文字

a

の整数コード

(ASCII, JIS, EUC

等

)

であり、

k

は

x

の文字列長

hash

は英語で「ごた混ぜにする」という意味。

i=0 k-1

一般にデータはいろいろな周期のものを含んでいるため、

m

がデータの周期を約数にもつと関数値の衝突が起こりやすくなる。そのため

m

としては素数を選ぶことが多い。

しかし、どのようなハッシュ関数を選んでも衝突は避けられない！

(18)

2015 2015/12/02

18 衝突対処法

異なる要素

x,y

に対し、ハッシュ値が等しくなる

(h(x)=h(y))

ことがある。

そのような場合の対処法として次の２つがある。

1.

外部ハッシュ法、チェイニング

(open hashing, chaining)

同じハッシュ値をもつ要素を、

その値に対応するバケットに格納する。

バケットは連結リストで実現できる。

2.

内部ハッシュ法、オープンアドレッシング

(closed hasing, open addressing) x

を格納しようとしたときに、位置

h(x)

がすでに

使われている場合、新しいハッシュ値

h _i (x) (i=1,2,…)

を次々と求め、最初に見つかった空いている位置

h _i (x)に格納する。h _i

としては、以下の関数などが使われる。

h _i (x)=(h(x)+i)%m

h(x)=x%m

の場合の

2 32

5 55 15

insert(15,S)

2 32

5

55

15

(19)

19 外部ハッシュ法の基本操作

member(x,S) h(x)に対応するバケット内で値がxのものを探し、見つかればyes、

見つからなければ

no

を返す。

Insert(x,S) h(x)

に対応するバケット内で値が

x

のものを探し、見つかれば何もしない、

見つからなければバケットに追加。

delete(x,S) h(x)

に対応するバケット内で値が

x

のものを探し、見つかれば削除、

見つからなければ何もしない。

基本操作の時間計算量

α=n/m :

占有率

(n:

格納要素数

, m:

バケット数

)

O(n)

(

全ての要素が同じハッシュ値をもつ場合

)

O(α)

(n=O(m)

であれば

O(1))

2 32

5 55 15

member(12,S)

h(12)=2 no

Insert(15,S)

h(15)=5

18 88 48

delete(88,S)

h(88)=8 48

(20)

2015 2015/12/02

20 内部ハッシュ法の基本操作

member(x,S)

位置

h(x)

から探し始め、

h(x),h ₁ (x),h ₂ (x),…

の順でその位置の要素が

x

と等しいかをチェックする。等しいものがみつかったら

yes

を返す。位置

h _i (x)

が空き

(“empty”)

となるまでチェックし、見つからなければ

no

を返す。

Insert(x,S)

位置

h(x)

h(x),h ₁ (x),h ₂ (x),…

x

と等しいかをチェックする。位置

h _i (x)

が空き

(“empty”)

となるまでチェックし、

x

と等しい要素が見つかれば何もしない。みつからなければ、検索途中で見つけた空き

(“empty” or “deleted”)

に

x

を格納する。

delete(x,S)

位置

h(x)

h(x),h ₁ (x),h ₂ (x),…

x

と等しいかをチェックする。位置

h _i (x)

が空き

(“empty”)

となるまでチェックし、

x

と等しい要素が見つかれば削除し”

deleted”

のフラグを立てる。みつからなければ何もしない。

基本操作の時間計算量

α=n/m :

占有率

(n:

格納要素数

, m:

バケット数

)

O(n)

(

全ての要素が同じハッシュ値をもつ場合

)

O(1/(1-α)) (x

が表にない場合

)

O(-(1/α)log(1-α)) (x

が表にある場合

)

どちらの場合も

n=O(m)

であれば、

O(1)

deleted empty

2 32 deleted

5 55 empty empty

15 member(12,S)

h(12)=2

no insert(12,S)

h(12)=2

12 delete(12,S)

(21)

21 内部ハッシュ法の平均時間計算量の証明

・

x

が表にない場合

h ₀ (x)(=h(x)),h ₁ (x),…の順にハッシュ値の計算を行うものとする。

位置

h _i (x)

で初めて空を見つける確率は

n(n-1)

・・・

(n-i+1)(m-n) m(m-1)・・・(m-i+1)(m-i)

である。（ただし、

i=0

のとき、上式は

(m-n)/m

をあらわすものとする。）

したがって、要素の比較回数の期待値は、

比較回数の定数倍の時間で計算できるので平均時間計算量は

O(1/(1-α)) (i +1) n(n − 1)  (n − i +1)(m − n )

m(m − 1)  (m − i + 1)(m − i )

i=0 n

∑ ⁼ ⁽ⁱ ⁺¹⁾

i=0 n

∑ _m(m ⁿ⁽ⁿ ⁻ ₋ ¹⁾ ₁₎ ^ _ ⁽ⁿ _(m ⁻ ₋ ⁱ _i ⁺¹⁾ ₊ ₁₎ ^# _$ ^% ¹ ⁻ _m ⁿ ⁻ ₋ ⁱ _i ^& _' ⁽

= (i + 1)

i=0 n

∑ _m(m ⁿ⁽ⁿ ⁻ ₋ ¹⁾ ₁₎ ^ _ ⁽ⁿ _(m ⁻ ₋ ⁱ _i ⁺¹⁾ ₊ ₁₎ ⁻ ⁱ

i=1 n+1

∑ _m(m ⁿ⁽ⁿ ⁻¹⁾ ₋₁₎ ^ _ ⁽ⁿ _(m ⁻ ₋ ⁱ _i ⁺ ₊₁₎ ¹⁾

≤ n(n − 1)  (n − i + 1) m(m − 1)  (m − i +1)

i=0 n

∑

≤ n

m

#

$ % &

' (

i

i=0

∞

∑ ⁼ ¹

1 − n m

= 1

1 − α

(22)

2015 2015/12/02

22 内部ハッシュ法の平均時間計算量の証明（続き）

・

x

が表にある場合

比較回数の期待値は、

n

個の異なる要素を空の表に格納するのに必要な比較回数

の平均に等しい。したがって

比較回数の定数倍で計算できるので、平均時間計算量は

O(- log(1-α))

（証明終わり）

1 α

確率

p

で生起する事象が

k

回目で初めて生起するとした場合、

k

の期待値は

1/p

であるという事実を使っている。つまり、確率

(m-i)/m

で生起する事象では、

k

の期待値は

m/(m-i)

である。

1 n m

… y= m

m-x

1 n

m

m − i ≤ 1 n

m m − x

0

∫

n i=0

n−1

∑ ^dx

= m

n ln m

m − n = − 1

α ^ln(1 ⁻ α )

(23)

第 7 回探索のためのデータ構造（ 2 ）

n

今日の内容：

¨

今日は短い内容が二つあります。

¨

前半：（発展内容）最適

2

分探索木を学ぼう。

n 「発展内容」なので、わからないときは飛ばしても良いです。（試験にでません）

n これは、検索のみで挿入と削除をしないときに、平衡二分探索木（第6回）よりも検索時間が短くなるデータ構造を見つける話です。表を埋めることで、計算を高速に行う「動的計画法」の例です。興味ある人はどうぞ！

¨

後半：（基本内容）「ハッシュ表」を学ぼう。

n ハッシュ表は、平均的にO(1)時間で探索できる、実用的に効率が良い探索データ構造です。

n

ポイント

¨

前半：最適

2

分探索木の計算は、本当はけっこう難しいが（全部候補の木を探すと指数時間かかる）、表を埋めていくことで、高速に計算できる。

¨

後半：「ハッシュ表」では、「ハッシュ関数」を用いて検索する方法を理解しよう。

¨

後半：ハッシュ表には、衝突回避法の違いで、「外部ハッシュ法」と「内部ハッシュ法」があります。「内部ハッシュ法」は、簡単な仕組みで手品のようにうまく、衝突を回避できます。

¨ C++

の

unordered_map

や、

java

の

HashMap

は、ハッシュ表で実装されています。

アルゴリズムとデータ構造

2015/12/02 1

アルゴリズムとデータ構造

第 7 回：探索のためのデータ構造（ 3 ）

前半：最適 2 分探索木の構築（発展）

後半：ハッシュ表（基本）

第 7 回 探索のためのデータ構造（ 2 ）

n

¨

¨

2

¨

n

¨

2

¨

¨

¨ C++

unordered_map

java

HashMap

2

2015/12/02 3

アルゴリズムとデータ構 造

第 7 回前半：探索のためのデータ構造（ 3 ）

前半： 最適 2 分探索木の構築（発展）

2015 2015/12/02

4 前回の復習

S

(dictionary)

1. member(x,S) : x∈S

yes, x S

no

2. Insert(x,S) : SをS∪{x}に更新

3. delete(x,S) : S

S

{x}

∈

member

O(log n)

insert, deleate

O(n)

member,insert,delete

O(n)

O(log n)

AVL

member,insert,delete

O(log n)

5 本日の内容

Q

↓

↑

Q2.

O(log n)

O(1)

m

n

O(n)

O(1)を実現可能

最適 2 分探索木の構築問題

n

¨ n

a 1 < a 2 <…< a n

¨

P

n

¨ n

2

T

2

6

P

(-∞,a1) 0.050

a1 0.050

(a1,a2) 0.050

a2 0.025

(a2,a3) 0.050

a3 0.125

(a3,a4) 0.050

a4 0.250

第 7 回探索のためのデータ構造（ 2 ）

アルゴリズムとデータ構造

前半：最適 2 分探索木の構築（発展）

a ₁ < a ₂ <…< a _n

a3 ^0.125

Cost(T) := Σ _{X:値または区間} P(X) cost(X)

a ₁ < a ₂ <…< a _n

T _i,k-1 T _k+1,j

S={a ₁ , a ₂ ,…,a _n } :

a ₁ <a ₂ <

<a _n

(a ₁ ,...,a _n ), (β ₀ ,...,β _n )

P{x=a _i }=α _i (i=1,2,…,n)

P{x<a ₁ }=β ₀ , P{a _i <x<a _i+1 }=β _i (i=1,2,…,n-1), P{a _n <x}=β _n T :S

a _i :

a _i

v ₀ :x<a ₁

v _i (i=1,2,…,n-1): a _i <x<a _i+1

v _n :x>a _n