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

(1)

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

第13週データ探索：ハッシュ法

2014年1月9日金岡晃

(2)

授業計画

1

第1週 (9/26)

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

第2週 (10/3)

アルゴリズムの効率、線形構造第3週

(10/10)

スタックと待ち行列第4週

(10/17)

文字列照合（KMP法、BM法）

第5週 (10/24)

木構造、木の走査

→文字列照合（BM法）、木構造

第6週 (10/31)

木の走査、二分木、決定木 第7週

(11/14)

中間試験

第8週 (11/21)

休講第9週

(11/28)

グラフ構造と最短路問題第10週

(12/5)

解の探索：Aアルゴリズム第11週

(12/12)

データ整列：ヒープソート法

第12週 (12/19)

データ整列：クイックソート法

第13週 (1/9)

データ探索：ハッシュ法第14週

(1/16)

データ探索：木構造探索法 1/22-2/8 期末試験

2014/1/9 アルゴリズムとデータ構造

(3)

【復習】第 12 週

データ整列：クイックソート法

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

2 ^2014/1/9 アルゴリズムとデータ構造

(4)

整列法の分類（１）

3

選択による方法

単純選択法、ヒープ整列法選択：複数のデータの中から最大あるいは最小のものを選ぶ動作

挿入による方法

単純挿入法（シャトル整列法）、シェル法

挿入：すでに整列している複数のデータの並びの適切な位置に、あらたな1枚を追加挿入する操作

交換による方法

単純交換法（バブルソート法）、クイックソート法

交換：注目した2枚の順番が逆になっていたら入れ替える動作

(5)

クイックソート

4

基準値となるキーを選択し、基準値より小さい数のデータ集合と基準値より大きい数のデータ集合に分ける。

それぞれの集合についても、同じく基準値となるキーを選択し、2つのデータ集合に分ける。

要素が1つ以下の集合となった場合、その集合は確定となる。

クイックソート法（Quick Sort）

(6)

クイックソートのアルゴリズム

5

straight-sort(x, y)は

単純な方法を使うことを意味している

(7)

演習

6

下記の1次元配列データをクイックソート法（前スライドのアルゴリズムを利用）で処理したときの、処理の過程を記述せよ。このとき、 select(k)を、どういう基準で選択したかを明確に記載すること。

ただし、過程の記述は各配列がどう変化していったかのみ記載すれば良いものとする。また、ここではstraight-sort()を利用する閾値は10ではなく3とする。

a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10]

30 40 80 35 60 70 55 10 20 50

(8)

第 14 週

データ探索：ハッシュ法

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

(9)

本日の到達目標と概要

• 到達目標

– データ探索と、その実現方法としてのハッシュ法の理解

• 概要

– データ探索

– 単純な手法：線型探索、二分探索 – ハッシュ法概要

– ハッシュ関数

– 開番地法と連鎖法

(10)

データ探索

9

辞書を引く運賃を調べる名前を思い出す

いずれもデータの探索

ファイル構造に基づく探索構造探索コンピュータによる探索

ファイル構造に基づかない探索内容探索、連想探索

(11)

探索におけるレコードの指定

10

指定の仕方

一致型、最近接型、区間型

複数条件指定

「家賃が7万円以下で、駅から10分以内の物件」

今日の講義では

• 探索に用いられるフィールドが1つ

• 一致型の探索

• レコードを「キー」と呼ぶ

(12)

単純な探索方法：線型探索と二分探索

11

線型探索

• 目的のキーを求めて表の先頭番地から順に調べていくもっとも単純な方法

• 逐次検索ともいわれる。

• 追加は効率的に行える（データの最後に追加する）が、探索と削除に時間がかかる追加：𝑂(1)

探索と削除：それぞれ𝑂(𝑛)

二分探索

• キーの値が昇順に並んでいるときに適用可能な手法

• 中央のキー（データが𝑛個ある場合は 𝑛 + 1 /2（の四捨五入か切り上げか切り捨て）番目のキー）との大小関係を調べる

• 一致なら探索終了

• 探索キーが大なら、後半の中での中央のキーを選択し、調べる

• 探索キーが小なら、前半の中での中央のキーを選択し、調べる

• 追加は効率的ではないが探索が効率的

追加：𝑂(𝑛)

探索：それぞれ𝑂(log 𝑛)

(13)

ハッシュ法

12

キーの値から探索・格納・削除の番地を決定する手法。

キーの値を順番に置くのではなくハッシュする（ばらまく）

ハッシュ（Hash）：意味：

寄せ集め、ごたまぜ

(14)

ハッシュ関数

13

ハッシュを行う関数

仮定：キーが小文字アルファベット8文字までキーのパターン数は 27⁸ − 1

表のサイズを𝑁とすると、なるべく衝突をさけるためにパターンを上手にばらつかせなければならないが、 𝑁がパターン数より小さい場合は衝突を避けられない

なるべく衝突が起こらないようにハッシュ関数を設計する利用される手法

• 除算法（Division）：キーのビット列を2進数と見なして表サイズの剰余を用いる

• 乱数法（平方採中法(mid-square）とも）：

• 乱数生成の種（Seed）としてキーを用いて、乱数を出力する

• 折り返し法（Folding）

• キーのビット列を適当に分断してそれらの和を計算する

ハッシュ関数は暗号でも重要な意味を持つ

(15)

用語：同族

14

同族（Synonym、同義語）

• ハッシュ関数の出力が一緒になる入力値

(16)

ハッシュ法

15

ハッシュ関数を用意し、キーを入力にしてハッシュ関数により得られた結果を番地として使う

衝突が起きた場合には対応が必要

• 空いている番地を探す：開番地法（開アドレス法）

• 衝突が起こったときに代わりの番地へのポインタを入れるようにする：連鎖法

開番地法の具体例：線型走査法（Linear Search）

• 得られた結果に一定の間隔𝑑を足し、空いているか確認し、空いていればその番地を使う

• 空いていない場合、間隔𝑑をさらに足すことを繰り返す

• この手法での一定の間隔をハッシュ増分（Hash Increment）と呼ぶ

(17)

ハッシュ法：具体例

16

iwahashi enomoto ooba

kazama kurosawa

tada yamagata 元データ

サイズ𝑁 = 11の表に入れる

0 1 2 3 4 5 6 7 8 9 10

ハッシュ関数

ℎ

₀

𝐾 = #𝐶1 𝑚𝑜𝑑 𝑁

データの1文字目アルファベットの順番（1~26）

衝突が起きた場合はハッシュ増分2の線型走査法を使う

ℎ

_𝑖

𝐾 = ℎ

₀

𝐾 + 2𝑖 𝑚𝑜𝑑 𝑁

(18)

ハッシュ法：具体例

17

(19)

探索効率

18

• ハッシュ法のキーの探索は、番地を求めることと同じ

• 探索の効率は衝突の回数に依存するクラスタ（Cluster）

• ひとたび互いに𝑑番地離れたキー同士が塊を形成し始めると加速度的に成長して探索効率を急激に低下させてしまう

• この塊をクラスタと呼ぶ

第1種クラスタ（Primary Cluster）：同族でないキー同士の塊部分第2種クラスタ：同族同士の部分（Secondary Cluster）

前スライドの例での平均探索回数：1+1+1+2+3+2+6/7＝2.29

(20)

開番地法

19

線型走査法（Linear Search）

• 得られた結果に一定の間隔𝑑を足し、空いているか確認し、空いていればその番地を使う

• 空いていない場合、間隔𝑑をさらに足すことを繰り返す

• この手法での一定の間隔をハッシュ増分（Hash Increment）と呼ぶ

• クラスタが発生する

ℎ

_𝑖

𝐾 = ℎ

₀

𝐾 + 𝑑𝑖 𝑚𝑜𝑑 𝑁

2次走査（Quadratic Search）法

• クラスタの発生を抑える

ℎ

_𝑖

𝐾 = ℎ

₀

𝐾 + 𝑎𝑖 + 𝑏𝑖

²

𝑚𝑜𝑑 𝑁

(21)

連鎖法

20

• キーKの番地を調べるときにh0(K)にすでにほかのキーが入っている場合、同じ値を持つキーが次にどこに入っているかの番地（ポインタ）を持つ

連鎖リスト

連合連鎖（Coalesced Chaining）法：

• 連鎖リストをたどって最後の要素を見つける

• 空き番地を見つけ、そこに格納

• 最後の要素のポインタ部に格納した番地を入れる

分離連鎖（Separate Chaining）法：

• 先に入っている同族でないキーを追い出してキーKを格納

• 同族が連鎖するようにする

• 追い出されたキーを空き番地に格納

(22)

演習

21

スライド「ハッシュ法：具体例」と同じデータを、同じく𝑁 = 11の表にハッシュ法を用いて格納するとする。この場合、以下の問に答えよ。

１）ハッシュ関数を以下とした場合の、ハッシュ表への格納状態（表）と、平均探索回数を求めよ

２）ハッシュ関数を以下とした場合の、ハッシュ表への格納状態（表）と、平均探索回数を求めよ

ℎ₀ 𝐾 = #𝐶1 × 26 + #𝐶2 𝑚𝑜𝑑 𝑁 ℎ_𝑖 𝐾 = ℎ₀ 𝐾 + 3𝑖 𝑚𝑜𝑑 𝑁

ℎ₀ 𝐾 = #𝐶1 × 26 + #𝐶2 𝑚𝑜𝑑 𝑁 ℎ_𝑖 𝐾 = ℎ₀ 𝐾 + 𝑖 + 𝑖² 𝑚𝑜𝑑 𝑁