Presentation is loading. Please wait.

Presentation is loading. Please wait.

集合、辞書とハッシュ法 第8回 集合と辞書 ~ データ構造(4)~.

Similar presentations


Presentation on theme: "集合、辞書とハッシュ法 第8回 集合と辞書 ~ データ構造(4)~."— Presentation transcript:

1 集合、辞書とハッシュ法 第8回 集合と辞書 ~ データ構造(4)~

2 (問1)解答 a d b c e f 1 3 2 4 5 1 3 a 4 5 d -1 2 b c e f [0] [1] [2] [3]
[4] label left child right f [5] a 1 3 d b 2 4 5 c e f

3 集合(Set) B b A c a f e 要素aが集合Aに属する : 要素aが集合Aに属さない : a ∈ A
Aの要素の個数(Aの位数(cardinality) : |A|<∞のとき、Aは有限集合(finite set) 集合Aのその要素も集合Bの要素となっているときAはBの部分集合(subset): A⊆BかつA≠BのときAはBの真部分集合(proper subset): a ∈ A a ∈ A |A| B A⊆B b A c A⊂B a f e

4 集合と要素 B b A c a f e 有限集合は通常… 要素をすべて列挙して記述する A = { a, c, e, f }
集合と要素   有限集合は通常… 要素をすべて列挙して記述する A = { a, c, e, f } B = { a, b, c, e, f } 要素の並べ方によって区別しない A = { a, c, e, f } = { a, e, f, c } B b A c a f e

5 和集合、積集合、差集合 p.49 A B a d b c 和集合(union) A∪B = { a, b, c, d }
積集合(共通集合, intersection) A∩B = { b } 差集合(difference) A-B = { a, c } A B a d b c

6 空集合、互いに素 p.49 E B A a b c 空集合(empty set) φ 要素を1つも持たない集合 E = φ
互いに素(disjoint) A∩B = φ 併合(merge) A∩B = φ のときにA∪Bを求めること 集合族(family of sets) 集合の集合 B A a b c

7 集合に関する基本的演算と操作 C A B a c b UNION(A, B, C) C ← A∪B = {a, b, c}
集合に関する基本的演算と操作   UNION(A, B, C) C ← A∪B = {a, b, c} INTERSECTION(A, B, C) C ← A∩B = φ DIFFERENCE(A, B, C) C ← A – B = {a, c} MERGE(A, B, C)   A∩B =φ (AとBは互いに素)のとき C ← A ∪ B A∩B ≠ φ のとき,未定義またはエラー C A B a c b

8 集合に関する基本的演算と操作2 A A A MEMBER(x, A) x ∈ A : yes を返す x ∈ A : no を返す
INSERT(x, A) DELETE(x, A) EMPTY(A) A x A x A 空集合φ

9 配列による集合の実現 すべての要素が普遍集合={0, 1,2,…,N-1}から選ばれ、Nがあまり大きくないものとすると右図のように表現できる
配列による集合の実現   すべての要素が普遍集合={0, 1,2,…,N-1}から選ばれ、Nがあまり大きくないものとすると右図のように表現できる 配列A [0] [1] 1 [2] 1 [3] A={1,2,4}のときの例 i ∈ A のとき1、 i ∈ A のとき0で表現 割当を逆にしてもよい [4] 1 [5] [6] [7]

10 積集合を求める void intersection(int *A, int *B, int *C){ int i;
for ( i = 0; i < N; i++ ) C[i] = A[i] * B[i]; } 1 [0] [3] [1] [2] [4] [5] [6] [7] A 1 [0] [3] [1] [2] [4] [5] [6] [7] B C [0] [1] [2] 1 [3] [4] 1 [5] [6] [7]

11 連結リストによる集合の実現 普遍集合がうまく定義できない場合や、Nが大きい場合は連結リストで表現すると良い
連結リストによる集合の実現   普遍集合がうまく定義できない場合や、Nが大きい場合は連結リストで表現すると良い 領域量はO(|A|) MEMBER, INSERT, DELETEはO(|A|)で実行可能 INTERSECTION, DIFFERENCEはO(|A||B|)かかる A = { a, c, e, f } f a c e init A

12 辞書(Dictionary) 集合Aに対し、以下の3つの演算のみが適用されるときAを辞書と呼ぶ INSERT
挿入.データ(レコード)を登録する. DELETE 削除.与えられた値(検索キー)と同じデータ(レコード)を探し出して,削除する. MEMBER   与えられた値(検索キー)と同じデータ(レコード)が存在すればyes,存在しなければnoを出力する.

13 概念図 検索キー orange 辞書D MEMBER(“orange”, D) ⇒ yes MEMBER(“banana”, D) ⇒ no
apple orange tomato 検索キー orange MEMBER(“orange”, D) ⇒ yes MEMBER(“banana”, D) ⇒ no 辞書D

14 ハッシュ法(hashing) 辞書は、しばしばハッシュ表を用いて実現される
ハッシュ法では,検索キーの値を,データが格納される位置(配列の添字)に直接関連付ける これにより,データの個数によらず,データの探索が一定時間で行える 計算量 O (1) (一定時間)

15 ハッシュ法の概要 ハッシュ法による探索 h(x) 線形探索 ハッシュ関数 x=“apple” 4 (ハッシュ値) ハッシュテーブル
4 (ハッシュ値) Table[4]にアクセス ハッシュテーブル banana kiwi apple orange mango table[0] table[1] table[2] table[3] table[4] table[5] table[6] table[7] 線形探索 違う 違う 違う 見つけた! キー”apple” はどこ? banana orange mango apple kiwi 先頭から順番に探していく必要がある

16 用語 ハッシュ関数(hash function) h(x) : キーの値x を配列の添字へ写像する関数
用語               ハッシュ関数(hash function) h(x) : キーの値x を配列の添字へ写像する関数 ハッシュ値(hash value) : ハッシュ関数h(x)が返す値 ハッシュ表(hash table) : データを格納する配列 バケット(bucket) : ハッシュ表の各要素

17 100の剰余をとることで,ハッシュ値が0~99の範囲に収まる
ハッシュ関数の例 int hashfunc(char *s) { int i = 0; while (*s) i += *s++; return i % 100; } s a p p l e \0 文字列 97 112 101 108 文字 コード 530 % 100 = ハッシュ値 30 各文字の文字コードを足しこむ 100の剰余をとることで,ハッシュ値が0~99の範囲に収まる

18 文字コード ASCIIコード American Standard Code for Information Interchange
文字コード        6×16+1=97 ASCIIコード American Standard Code for Information Interchange 1文字1byte(8bit)で表現 char型が表現できる範囲 -128 ~ 0 ~ +127        128種類

19 衝突(コリジョン, collision) 異なるキーに対して同一のハッシュ値が生成されることを、コリジョン(衝突)という
コリジョンが発生した場合の対策には以下の2通りの方法がある (教科書と異なる名称なので注意 ) チェイン法 (chaining)      = 外部ハッシュ法 オープンアドレス法 (open addressing) = 内部ハッシュ法 h(x) ハッシュ関数 衝突 x=“apple” 4 (ハッシュ値) x=“almond” 4 (ハッシュ値)

20 注意:用語の別名 D. E. Knuth, “The Art of Computer Programming,” Vol. 3:Sorting and Searching, Addison-Wesley, 1973 チェイン法(chaining) オープンアドレス法(open addressing) N. Wirth, “Algorithms + Data Structures = Programs,” Prentice Hall, 1976 直接チェイン法(direct chaining) A. V. Aho, J. E. Hopcroft, J. D. Ullman, “Data Structures and Algorithms,” Addison-Wesley, 1983 オープンハッシュ法(open hashing) クローズドハッシュ法(closed hashing) この呼び方を使用 こちらの呼び名を 使っている本の方が多い オープンが 逆なので注意!!!!

21 チェイン法(chaining) 同一のハッシュ値を持つデータを連結リストで処理 データの格納 almond kiwi orange
table[0] kiwi orange banana ハッシュ値 4 table[1] table[2] mango 衝突 table[3] apple table[4] almond table[5] バケット数6のハッシュテーブル

22 チェイン法におけるデータの探索 データの探索 orange kiwi orange banana mango almond apple
違う 見つけた! ハッシュ値 0 table[0] kiwi orange banana table[1] table[2] mango table[3] almond apple table[4] table[5]

23 チェイン法の解析 あらかじめデータの個数を見積もり, それに見合った数のバケットを用意する
チェイン法の解析    データの個数Nに対してバケット数Bが十分大きい場合 一定時間 O(1) で探索可能 使用されないバケットが発生する可能性あり(メモリの無駄) table[0] table[1] table[2] table[3] table[4] table[5] table[6] table[7] table[8] table[9] データの個数Nに対してバケット数Bが小さい場合 探索に時間がかかる ( 最悪でO(N) ) 空きバケットは減少 table[0] あらかじめデータの個数を見積もり, それに見合った数のバケットを用意する

24 ハッシュ関数の効率 効率のよいハッシュ関数 ⇒データが各バケットに一様に割当てられる 効率のよくないハッシュ関数
⇒データが特定のバケットに偏る table[0] table[0] table[1] table[1] table[2] table[2] table[3] table[3] table[4] table[4] table[5] table[5]

25 オープンアドレス法(open addressing)
すでにバケットが使用されていた場合,空いている別のバケットにデータを保存 データの 格納 table[0] banana table[1] almond kiwi table[2] 衝突 ハッシュ値 4 table[3] apple table[4] 再ハッシュ ハッシュ値 5 almond table[5] orange table[6] バケット数8の ハッシュテーブル 空いてる table[7]

26 オープンアドレス法におけるデータの探索 データの 探索 banana almond kiwi apple 再ハッシュ almond
table[0] banana table[1] almond kiwi table[2] ハッシュ値 4 違う table[3] apple table[4] 再ハッシュ ハッシュ値 5 almond table[5] orange 見つけた! table[6] table[7]

27 空のバケットの区別 データが削除されたのか,使われたことがないのかを区別しない場合 lemon 別のバケットに入っているかもしれない…
table[0] 別のバケットに入っているかもしれない… ハッシュ値 1 banana table[1] 再ハッシュ kiwi table[2] table[3] ハッシュ値 3 再ハッシュ apple table[4] ハッシュ値 5 table[5] 再ハッシュ orange table[6] almond table[7]

28 空のバケットの区別(deletedとempty)
データが削除された (deleted)のか,使われたことがないのか(empty)を区別することで,emptyのバケットを見つけた時点で探索を打ち切れる lemon 0: empty -1: deleted table[0] ハッシュ値 1 banana table[1] 再ハッシュ kiwi table[2] -1 table[3] ハッシュ値 3 再ハッシュ apple table[4] ハッシュ値 5 table[5] 探索終了 orange table[6] almond table[7]

29 再ハッシュ(rehashing) 1次ハッシュ バケットがふさがっていた場合,循環的に直後のバケットを調べることになる
⇒ふさがったバケットが並びがちになる B = 8 の場合 lemon h(x) = 0 i : 再ハッシュの回数 grape table[0] h1(x) = 1 banana table[1] h2(x) = 2 kiwi table[2] h3(x) = 3 table[3]

30 3以外のバケットをランダムな順番で調べられる
衝突をランダムに処理する方法 1からB-1までの数字が必ず1回だけランダムに出現する数列d1, d2, … ,dB-1を用い, 次式により求める 例)数列{ 5, 1, 2, 4, 3, 6, 7}を用いた場合(B=8) キーh(x)=3のとき 0, 4, 5, 7, 6, 1, 2 ランダムな数列をどうやって作るかがポイント ⇒シフトレジスタを利用するなど 3以外のバケットをランダムな順番で調べられる

31 探索時に調べるバケット数(探索1回あたりの平均)
オープンアドレス法の解析 探索時に調べるバケット数(探索1回あたりの平均) 再ハッシュ時に 順番に バケットを調べる場合 ランダムな数によって データが見つかった場合 (探索成功) データが見つからない場合 (探索失敗) αはハッシュ表の使用率

32 探索成功時の比較バケット数 80% 3.0個 2.0個 90% 5.5個 2.6個 ハッシュ表の 使用率 α 再ハッシュ時に 順番に
バケットを調べる場合 ランダムな数によって 80% 3.0個 2.0個 90% 5.5個 2.6個

33 ハッシュ法の比較 チェイン法 オープンアドレス法 登録データ数 N の上限 なし = バケット数B 操作の効率 N ≧B のとき急速に低下
ハッシュ法の比較      チェイン法 オープンアドレス法 登録データ数 N の上限 なし (ただし,データ数が多すぎると探索時間が長くなる) = バケット数B 操作の効率 N ≧B のとき急速に低下 N が B に近づくにつれ急速に低下. データ数N の目安 2B  ≧  N 0.9B  ≧  N

34 乱数列の生成例 d1 =5 <<1 k d2 =1 B=8(=23 ), k=3, di=5の場合 d3 =2 d4 =4 k
乱数列の生成例  d1 =5 <<1 k d2 =1 B=8(=23 ), k=3, di=5の場合 d3 =2 d4 =4 1~7の乱数が 得られた k d5 1 =3 d6 1 =6 1 1 k=5でもうまくいくが, その他のkではうまくいかない k 1 d7 =7 1

35 1~B-1の乱数をうまく生成できるk をあらかじめ見つけておく必要がある
シフトレジスタによる乱数列の生成 B : 2のべき乗の数 (例: 21,22,23, …) k : 1~B-1までの間のある定数 di : 最初の値 ① diを2倍 (1ビット左シフト) ② 結果がBを超えていたら,Bを減算し,減算結果と,あらかじめ決めておいたkとの排他的論理和をとる 1~B-1の乱数をうまく生成できるk をあらかじめ見つけておく必要がある 乱数が得られる

36 乱数列の生成例 d1 1 =5 1 <<1 k 1 d2 1 =1 B=8(=23 ), k=3, di=5の場合 d3 1
乱数列の生成例  d1 1 =5 1 <<1 k 1 d2 1 =1 B=8(=23 ), k=3, di=5の場合 d3 1 =2 d4 1 =4 1 1~7の乱数が 得られた k 1 d5 1 =3 d6 1 =6 1 1 k=5でもうまくいくが, その他のkではうまくいかない k 1 d7 =7 1

37 まとめ 集合 辞書とハッシュ法

38 本日の課題 バケット数5のハッシュ表を考える.ハッシュ関数h(x)= x mod 5 を用いて,空のハッシュ表に数値データ x ={23, 48, 35, 4, 10}を格納する場合について以下の問に答えよ. (問1) チェイン法を用いてデータを格納した場合,ハッシュ表はどうなるか?図を描け. (問2) オープンアドレス法を用いてデータを格納した場合,ハッシュ表はどうなるか?図を描け.ただし再ハッシュには一次ハッシュを使用するものとする.


Download ppt "集合、辞書とハッシュ法 第8回 集合と辞書 ~ データ構造(4)~."

Similar presentations


Ads by Google