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

(1)

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

第14週データ探索：ハッシュ法、木構造探索法

2015年1月15日金岡晃

(2)

授業計画

1

第1週 (9/25)

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

第2週 (10/2)

アルゴリズムの効率、線型構造、

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

(10/9)

＜演習＞アルゴリズムの効率、

線型構造、スタックと待ち行列第4週

(10/16)

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

＋＜演習＞

第5週 (10/23)

休講第6週

(10/30)

木の構造、木の走査、二分木、

決定木 第7週

(11/13)

＜演習＞木の構造、木の走査、

二分木、決定木 第8週

(11/20)

中間試験

第9週 (11/27)

休講第10週

(12/4)

グラフ構造と最短路問題＋

＜演習＞

第11週 (12/11)

休講第12週

(12/18)

データ整列：ヒープソート法、クイックソート法＋＜

演習＞

第13週 (1/8)

データ探索：ハッシュ法、

木構造探索法 →休講 第14週

(1/15)

データ探索：ハッシュ法、

木構造探索法＋＜演習＞

1/29 期末試験

2015/1/15 アルゴリズムとデータ構造

(3)

【復習】第 12 週

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

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

2 2015/1/15 アルゴリズムとデータ構造

(4)

整列法の分類（１）

3

選択による方法選択による方法

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

選択：複数のデータの中から最大あるいは最小のものを選ぶ動作

挿入による方法挿入による方法

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

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

交換による方法交換による方法

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

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

(5)

整列法の分類（２）

4

併合による方法併合による方法

併合整列法（マージソート法）、多ウェイ併合法

併合：整列している2つのデータの並びを統合して1つにする操作

分配による方法分配による方法

バケット整列法分配：データの先頭を見て、グループに大まかに仕分ける操作

分配：データの先頭を見て、グループに大まかに仕分ける操作

(6)

ヒープ整列法

5

1次元配列データ𝑎 1 , ⋯ , 𝑎[𝑛]は、二分木の物理構造とみなすことができる。

𝑖

2𝑖 2𝑖 + 1

第𝑖要素𝑎 𝑖 の左の子と右の子を、それぞれ

𝑎 2𝑖 , 𝑎 2𝑖 + 1 と考えれば、1次元配列と二分木との間を一意に対応づけることができる。

1次元配列を二分木と見なして整列する方法ヒープ整列法（Heapsort）

ヒープ整列法（Heapsort）

ヒープ：親子関係にある任意の2つの節において、子節の値が親節の値を超えないような準完全二分木

ヒープでは最大のデータは根に保持される特徴を利用する

(7)

ヒープ整列法のアルゴリズム

6

(8)

クイックソート

7

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

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

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

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

(9)

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

8

straight-sort(x, y)は

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

straight-sort(x, y)は

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

(10)

課題の解説

9

(11)

演習（その 10 ）

10

Floydのアルゴリズム

演習：下のグラフに対し、Floydのアルゴリズムを適用した場合、最終的に出力される配列costの情報を示せ

𝑆 𝐷

𝐴 𝐵 𝐸

𝐶

4 3

1

1 2 2

𝑉 = {𝐴, 𝐵, 𝐶, 𝐷, 𝐸, 𝑆}

S A B C D E

S 0 3 ∞ ∞ 4 ∞

A 3 0 1 1 ∞ ∞

B ∞ 1 0 ∞ ∞ 2

C ∞ 1 ∞ 0 ∞ ∞

D 4 ∞ ∞ ∞ 0 2

E ∞ ∞ 2 ∞ 2 0

配列costの初期状態配列costの初期状態

(12)

演習（その 11 ）

11

ヒープソート、クイックソートヒープソート、クイックソート

演習：下記の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

(13)

第 14 週

データ探索：ハッシュ法、木構造探索法

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

(14)

本日の到達目標と概要

• 到達目標

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

• 概要

– データ探索

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

• ハッシュ法概要

• ハッシュ関数

• 開番地法と連鎖法 – 木構造探索法

• 二分木探索法

• 平衡二分木

• AVL木

• B木

• 桁探索木

(15)

データ探索

14

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

いずれもデータの探索

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

コンピュータによる探索

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

(16)

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

15

指定の仕方指定の仕方

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

複数条件指定複数条件指定

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

今日の講義では

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

• 一致型の探索

• レコードを「キー」と呼ぶ今日の講義では

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

• 一致型の探索

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

(17)

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

16

線型探索線型探索

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

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

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

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

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

二分探索二分探索

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

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

• 一致なら探索終了

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

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

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

追加：𝑂(𝑛)

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

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

(18)

ハッシュ法

17

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

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

ハッシュ（Hash）

意味：寄せ集め、ごたまぜハッシュ（Hash）

意味：寄せ集め、ごたまぜ

(19)

ハッシュ関数

18

ハッシュを行う関数

仮定：キーが小文字アルファベット8文字まで仮定：キーが小文字アルファベット8文字まで

キーのパターン数は 27⁸ − 1

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

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

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

利用される手法

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

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

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

• 折り返し法（Folding）

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

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

(20)

用語：同族

19

同族（Synonym、同義語）

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

(21)

ハッシュ法

20

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

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

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

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

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

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

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

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

(22)

ハッシュ法：具体例

21

iwahashi iwahashi

enomoto enomoto ooba

ooba

kazama kazama kurosawa kurosawa

tada tada yamagata yamagata 元データ

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

0 1 2 3 4 5 6 7 8 9 10

ハッシュ関数

ℎ

₀

𝐾 = #𝐶1 𝑚𝑜𝑑 𝑁

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

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

ℎ

_𝑖

𝐾 = ℎ

₀

𝐾 + 2𝑖 𝑚𝑜𝑑 𝑁

(23)

ハッシュ法：具体例

22

(24)

探索効率

23

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

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

クラスタ（Cluster）

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

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

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

第2種クラスタ：同族同士の部分（Secondary Cluster）

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

(25)

開番地法

24

線型走査法（Linear Search）線型走査法（Linear Search）

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

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

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

• クラスタが発生する

ℎ_𝑖 𝐾 = ℎ₀ 𝐾 + 𝑑𝑖 𝑚𝑜𝑑 𝑁

2次走査（Quadratic Search）法 2次走査（Quadratic Search）法

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

ℎ_𝑖 𝐾 = ℎ₀ 𝐾 + 𝑎𝑖 + 𝑏𝑖² 𝑚𝑜𝑑 𝑁

(26)

連鎖法

25

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

連鎖リスト

連合連鎖（Coalesced Chaining）法：

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

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

• 最後の要素のポインタ部に格納した番地を入れる連合連鎖（Coalesced Chaining）法：

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

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

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

分離連鎖（Separate Chaining）法：

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

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

• 追い出されたキーを空き番地に格納分離連鎖（Separate Chaining）法：

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

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

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

(27)

演習（その 12 ）

26

ハッシュ法ハッシュ法

演習：スライド「ハッシュ法：具体例」と同じデータを、同じく𝑁 = 11の表にハッシュ法を用いて格納するとする。

ハッシュ関数を以下とした場合の、ハッシュ表への格納状態（表）と、平均探索回数を求めるプログラムを作成せよ

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

(28)

演習（その 12 ）：実行イメージ

27

> java HashSearch 0: iwahashi

1: tada 2: kazama 3:

4: ooba

5: yamagata 6:

7:

8: kurosawa 9: enomoto 10:

----

Average Num of Search: 1.17

> java HashSearch 0: iwahashi

1: tada 2: kazama 3:

4: ooba

5: yamagata 6:

7:

8: kurosawa 9: enomoto 10:

----

Average Num of Search: 1.17

ここに書いてある値は適当です。

自分で解いてみましょう

(29)

二分木探索法

28

• 各節に1つのキーを格納

• 節の左部分木にはその節のキーよりも小さい値のキーを格納

• 節の右部分木にはその節のキーよりも大きい値のキーを格納 60, 30, 75, 45 ,15 ,90

というキーを順に格納

キーの削除：

• 削除したいキー𝐾の検索

• 𝐾が葉であれば即座に消去

• 𝐾が節であれば直前あるいは直後の大きさのキーを𝐾の節に持ってくる

(30)

平衡二分木

29

二分探索木の問題点：

登録順序により木の形状が大きくかわる二分探索木の問題点：

登録順序により木の形状が大きくかわる

60, 30, 75, 45 ,15 ,90

というキーを順に格納する場合 90, 75, 15, 60 30, 45

というキーを順に格納する場合

• 探索時に木のポインタをたどる回数平衡係数（Balance Factor）

平衡係数（Balance Factor）

• 二分木の任意の節での、(左部分木の高さ-右部分木の高さ）の値

• どの節においても平衡係数がある一定の範囲に収まっている場合、高さ平衡二分木（Height Balanced Binary Tree）あるいは単に平衡二分木という

節のレベル節のレベル

(31)

AVL 木

30

• G. Adelson-VelskiiとY. Landisの２人により提案された

• キーを追加していく過程で、平衡性が破れたら直ちに二分木の構造を手直ししてつねに平衡性を維持できるような機構を備える

(32)

AVL 木

31

単回転（Single Rotation）と複回転（Double Rotation）単回転（Single Rotation）と複回転（Double Rotation）

• 節Aを根の方向に移動し、それに押し出されるように節Pを節Aの右の子に移動する操作

• 単回転を２回行うことを複回転と言う

(33)

B 木

32

• R. BayerとE. McCreightにより提案された順序付き多進木

• 定義

• 根以外の節には、 𝑚個以上、 2𝑚個以下のキーが格納される。それらのキー（ 𝑛個とする）を𝑎 1 , 𝑎 2 , 𝑎 3 , ⋯ , 𝑎[𝑛]とする。

• 根には１個以上2𝑚個以下のキーが格納される

• 葉はすべて同一レベルにある

• 葉以外の節には、部分木へのポインタが𝑛 + 1個ある。これらのポインタを𝑝 0 , 𝑝 1 , ⋯ , 𝑝 𝑛 とする。

• 任意の節において、キー列𝑎 1 , 𝑎 2 , 𝑎 3 , ⋯ , 𝑎[𝑛]は昇順に整列している。また、葉以外の任意の節について、キー𝑎 𝑖 の大きさは、 𝑝 𝑖 − 1 の指す部分木内のどのキーよりも大きく、 𝑝 𝑖 の指す部分木内のどのキーよりも小さい 1 ≤ 𝑖 ≤ 𝑛

(34)

B 木の構成

33

(35)

B 木：キー追加

34

キー45の追加（単純追加の場合）

キー20の追加（分割による場合）

(36)

B 木：キー削除（１）

35

キー15の削除（単純削除の場合）

キー32の削除（アンダーフローによる場合）

(37)

B 木：キー削除（２）

36

キー70の削除（連結による場合）

(38)

桁探索（ Digital Search ）木

37

• 目的のキーを構成している英数字やビット（桁）を順に見つつ、分岐先を判断しながら探索や格納を進めていく方法

(39)

桁探索木：トライ

38

• キーを格納するのは葉のみに限定し、内部節には桁に関する分岐情報のみを保持するようにしたもの

(40)

B 木の節の物理構造

39

BTreeNode[0]

public class BTreeNode {

public int dimension;

public BTreeNode[] node;

public int[] key;

public BinTreeNode(int inDimension){

dimension = inDimension;

node[] = new

BTreeNode[2*dimension+1];

key[] = new int[2*dimension];

… }

} key[0] key[1] …

…

BTreeNode[1]

(41)

演習（その 13 ）

40

B木 B木

演習：下図のような2次のB木があるものとする。これに、まずキー50を追加し、

その後、キー10を削除し、さらにその後にキー43を削除するものとする。それぞれの処理が終わった直後のB木を図示せよ。

入力：なし（B木データはプログラム中に記載してよい）

出力：B木の状態

(42)

演習（その 13 ）：実行イメージ

41

 java Btree

root : 13, 40, 68, 88 node1: 3, 10

node2: 15, 20, 30, 33 node3: ……

……

 java Btree

root : 13, 40, 68, 88 node1: 3, 10

node2: 15, 20, 30, 33 node3: ……

……

ここに書いてある値は適当です。

自分で解いてみましょう

(43)

本日の到達目標と概要

• 到達目標

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

• 概要

– データ探索

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

• ハッシュ法概要

• ハッシュ関数

• 開番地法と連鎖法 – 木構造探索法

• 二分木探索法

• 平衡二分木

• AVL木

• B木

• 桁探索木

(44)

締切と提出方法：演習その 12, 13

• 締切

– 3週間後（2月5日）の16:10まで

• 提出方法

– 電子メール

• メールアドレス

– [email protected]

– メールのタイトルに「アルゴリズムとデータ構造第7回課題」と書いてください

– 作ったプログラムをメールに添付してください。

• 注意事項

– 必ず金岡から受領確認メールを返します。

• 必ず日本語で受領確認メールを返します

• 英語のメールはエラーメール（アドレスが間違っている）の可能性が高いです

– メールで提出がされていないものは未提出とみなします

43

(45)

試験について

•

日時

– 2015

年

1

月

29

日（木）

3

限・

4

限

•

形式

–

筆記試験

•

持ち込みあり

– PC

、スマートフォン、タブレットの持ち込みも可

–

ネットワーク接続可

•

教室は掲示で確認すること

•

時間

– 13:00-14:30

の

90

分

•

試験範囲

–

初回から今回までの配布資料と教科書内の該当する箇所

44

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

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

授業計画

【復習】第 12 週

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

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

整列法の分類（１）

整列法の分類（２）

ヒープ整列法

ヒープ整列法のアルゴリズム

クイックソート

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

課題の解説

演習（その 10 ）

演習（その 11 ）

第 14 週

データ探索：ハッシュ法、木構造探 索法

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

本日の到達目標と概要

データ探索

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

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

ハッシュ法

ハッシュ関数

用語：同族

ハッシュ法

ハッシュ法：具体例

ℎ

𝐾 = #𝐶1 𝑚𝑜𝑑 𝑁

ℎ

𝐾 = ℎ

𝐾 + 2𝑖 𝑚𝑜𝑑 𝑁

ハッシュ法：具体例

探索効率

開番地法

連鎖法

演習（その 12 ）

演習（その 12 ）：実行イメージ

二分木探索法

平衡二分木

AVL 木

AVL 木

B 木

B 木の構成

B 木：キー追加

B 木：キー削除（１）

B 木：キー削除（２）

桁探索（ Digital Search ）木

桁探索木：トライ

B 木の節の物理構造

演習（その 13 ）

演習（その 13 ）：実行イメージ

本日の到達目標と概要

締切と提出方法：演習その 12, 13

試験について

日時

年

月

日（木）

限・

限

形式

筆記試験

持ち込みあり

、スマートフォン、タブレットの持ち込みも可

ネットワーク接続可

教室は掲示で確認すること

時間

の

分

試験範囲

初回から今回までの配布資料と教科書内の該当する箇所

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

データ探索：ハッシュ法、木構造探索法