組合せ爆発の対処

探索とは？

キー 一致するものを探す ・・・・ ・・・・ ・・・・ ・・・・ ・・・・ ： ： ：： ：： レコード フィールド

線形探索アルゴリズム(1)

n=10, i =0, target=54 a[i] : target i++ START END = ≠ i : n return i _{return -1} < ≧ 前提：配列aにn個のデータが保存 処理：_target と同じデータが蓄えら れている配列要素の添え字を返し， ない場合は-1を返すフローチャー トを記せ

ｋｅｙ ｄａｔａ ｔａｂｌｅ［０］ ｔａｂｌｅ［１］ ｔａｂｅｌ［２］ ｔａｂｌｅ［３］ ： ： ｔａｂｌｅ［ｎ－１］ ｔａｂｌｅ［ｎ］ ： ： ｔａｂｌｅ［１９９］ ７５ 福崎慎也 １０１ 渡邊滋之 １７ 大野綾子 ２８ 川島祐毅 ： ： ： ： ６４ 仲野弘幸 番人 (sentinel) ８７ 番人による少し早い線形探索

target = 54, i =0, a[n] = target a[i] : target i=i+1 START END = ≠ i : N return i return -1 < ≧

番人を利用した線形探索アルゴリズム

※ループ毎に iとn-1の比較が不要

n=10, target = 54, i =0 a[i] : target i=i+1 START END = ≠ 前処理 i : N return i _{return -1} < ≧ n=10, target = 54, i =0, a[n] = target a[i] : target i=i+1 START END = ≠ 前処理 i : N return i return -1 < ≧ 番人なし _番人あり

２つの線形探索アルゴリズムの比較

二分探索法(バイナリサーチ）

a[0]=1 a[1]=3 a[2]=4 a[3]=8 a[4]=13 a[5]=14 a[6]=18 a[7]=20 a[8]=21 a[9]=25 探すキーの値は 14 とする。 low→ middle→ high→ <14 a[0]=1 a[1]=3 a[2]=4 a[3]=8 a[4]=13 a[5]=14 a[6]=18 a[7]=20 a[8]=21 a[9]=25 low→ middle→ high→ >14 =middle+1 a[0]=1 a[1]=3 a[2]=4 a[3]=8 a[4]=13 a[5]=14 a[6]=18 a[7]=20 a[8]=21 a[9]=25 high→ low, middle→ =14 =middle-1 探索範囲

二分探索アルゴリズム

(半分ずつ捨てるのがポイント）

サイズｎの配列key(0～n-1)

においてsを探す

① first=0, last=n-1

② mid = (first+last)/2

③ key(mid)=s -> Found

key(mid)<s -> first=mid+1 Goto ②

key(mid)>s -> last=mid-1 Goto ②

線形探索の計算量_{（比較の回数）は 最良１、最悪ｎ、平均ｎ／２} データ数ｎに対して Ｏ（ｎ） 二分探索の計算量_{（比較の回数）は} ２ｋ－１_≦ｎ＜２ｋ_{のとき ｋ回} つまり、データ数ｎに対して 約Ｏ（ｌｏｇ_２ｎ）

線形探索の計算量は Ｏ（ｎ） 二分探索の計算量は Ｏ（log2 ｎ） ｎ＝１，０００だったら？ ｎ＝１，０００ log₂ｎ＝約１０ （なぜなら２１０_{＝1,024） １００倍違う！ 定数係数が少しくらい違ったって、} 勝負は明らか！

ビッグO のグラフ化

N 5 10 15 20 25 O(2n_{) 32 1024 32768 1048576 33554432} O(N2_{) 25 100 225 400 625} O(NlogN) 3.49 10 17.64 26.02 34.94 O(N) 5 10 15 20 25 O(logN) 0.69 1 1.17 1.30 1.39 O(1) 1 1 1 1 1

O(1) O(logN) O(N) O(NlogN) O(N2₎ O(2n₎

ビッグオーの

グラフ化

データの登録も考えると

登録（ｎ要素当り） 探索（１回当り） 線形探索 Ｏ（ｎ） Ｏ（ｎ） 二分探索 Ｏ（ｎ２_{） Ｏ（log ｎ）} クイックソートで Ｏ（ｎ log ｎ）

登録１回あたりの探索回数をＳとすると、 線形探索 Ｏ（ｎ）＋Ｓ・Ｏ（ｎ） 二分探索 Ｏ（ｎ log ｎ）＋Ｓ・Ｏ（log ｎ） _{ｎ＜＜Sでないと、二分探索は有利に} ならない！ 頻繁にデータ集合が変わるような応用には 二分探索は適さない

ハッシュ法

ハッシング

（

ｈａｓｈｉｎｇ

_{）ともいう}

ｈａｓｈ： 切りきざむ 挿入・探索・削除がＯ（１）でできる つまり、データの個数ｎに依存しない 理想の探索技法！？

学生番号から氏名などを求めたい

2003年度に入学した学生だけを考えると、 70310001～70310101 でも、一般にキーはこのように順序よく 並んでいない ｄｉｒｅｃｔ ａｃｃｅｓｓ という 配列の0番目から100番目に氏名を格納 → （学生番号下3桁－1）番目の 配列要素を見ればよい

英和辞書

• 5万語の英和辞書の全体をメモリにのせて使 いたい • 各単語のインデクス番号が分かれば，O(1)で ある単語の意味を知ることができる インデクス番号 内容 1 2 3 …. hash:切り刻む 50,000 どうすれば 各単語の インデクス番号が 分かるか？

語を数に変換する

• ASCII(アスキー)コード – 大文字，小文字，数字，記号などを0から255まで の数で表現 – a:97, b:98, …, z:122 • 大文字，数字，記号などを使わないとしたら – スペースを０として，a:1, b:2, c:3, …, z:26の２７文 字で表現できる

語を数に変換する 方法１：単語の各文字に対応する数の総和を インデクス番号とする • cats = 3 + 1 + 20 + 19 = 43 • Dic[43] = cat:ネコ，猫科の動物・・・・ ここで，単語の最大文字数を１０とすると，辞書の一番最後の文字は， （理論的には） zzzzzzzzzz（zが１０個） = 26 X 10 = 260 50,000(単語あるとすれば） ÷ 260 = 192 → サイズ260の配列を準備すれば、 １つの配列要素に１９２語が該当する 例えば、単語の各文字に対応する数の総和がcatと同じ43になる単語 was(23+1+19), give(7+9+22+5), tend(20+5+14+4), ….

語を数に変換する 方法２：桁位置を利用する（べき乗化） • 数値の場合は０から９の１０種類（１０進数） – 各桁は１０のべき乗 • 今回の前提では，スペース，aからzの２７種類（２７ 進数） – 各桁は２７のべき乗 • cats = 3x273_+1x272_+20x271_+19x270 = 60,337 • zzzzzzzzzz = 26x279 _+26x278 _+…+26x270 = 205,891,132,094,648

配列１要素あたり１バイトとすると，

約190TBのメモリが必要！！

1TB = １０２４ * 1024 * 1024 * 1024 =

1,099,511,627,776 (約１兆バイト)

200兆以上！！

語を数に変換する

方法２：桁位置を利用する（べき乗化）

fira firb firc fird

fire

firf firg

125146 _{125147 125148 125149 125151 125152}

単語ではない

実在する単語

ハッシュ法

• 巨大な範囲の数を実用的なサイズの配列の 添え字（インデクス）に変換 • 簡単な方法としては，モジュロ演算子（％）を 使う – %nは０からn-1までの数を作りだす （値域：０～３） ２３ % 4 = 3 13052 % 4 = 0 38 % 4 = 2 配列のインデクス = 巨大な数 % 配列サイズ

ハッシュ関数（ｈａｓｈ ｆｕｎｃｔｉｏｎ）

キーの値ｘの集合 添字（ハッシュ値） ｈ（ｘ）の集合 ０，１，２， ・・・，９９ × × × × × × ・・・ ２６５ １００ ｈ（ｘ） 大きな値域の数を小さな値域の数へと ハッシュ（切り刻む）する。文字列を 一定範囲の整数に変換すること。

ハッシュ関数の例 ｉｎｔ ｈａｓｈ（ｃｈａｒ ＊ｓ） ｛ ｉｎｔ ｉ = ０； ｗｈｉｌｅ （＊ｓ） ｉ += ＊ｓ++； ｒｅｔｕｒｎ ｉ ％ 100｝ a:97……… z:122 アスキーコードの総和を １００で割った余りを配列 添字とする この関数で求まるハッシュ値 の例 _{文字列 ハッシュ値} ｏｎｅ 22 ｔｗｏ 46 ｔｈｒｅｅ ｆｏｕｒ ｆｉｖｅ ｓｉｘ ｓｅｖｅｎ ｅｉｇｈｔ ｎｉｎｅ ｔｅｎ a 97 b 98 c 99 d 100 e 101 f 102 g 103 h 104 i 105 j 106 k 107 l 108 m 109 n 110 o 111 p 112 q 113 r 114 s 115 t 116 u 117 v 118 w 119 x 120 y 121 z 122

ハッシュ表（テーブル）

ハッシュ値の例 _{文字列 ハッシュ値} ｏｎｅ 22 ｔｗｏ 46 ｔｈｒｅｅ ｆｏｕｒ ｆｉｖｅ ｓｉｘ ｓｅｖｅｎ ｅｉｇｈｔ ｎｉｎｅ ｔｅｎ 0 1 ….. 26 five 27 ten 28 29 eight ….. ハッシュ関数を使って データを挿入した配列

ハッシュ(1)

問題1： 以下のハッシュ関数を用いて、表の各文字列に対応する ハッシュ値を求めよ。 ｉｎｔ ｈａｓｈ（ｃｈａｒ ＊ｓ） ｛ ｉｎｔ ｉ = ０； ｗｈｉｌｅ （＊ｓ） ｉ += ＊ｓ++； ｒｅｔｕｒｎ ｉ ％ 11｝

a:1, b:2, c:3, d:4, e:5, f:6, g:7, h:8, i:9, j:10, k:11, l:12, m:13, n:14,o:15, p:16, q:17, r:18, s:19, t:20, u:21, v:22, w:23, x:24, y:25, z:26 ハッシュ関数 アルファベットに対応する数値 文字列 ハッシュ値 fukuzaki watanabe oono kawashima nakano miura 例：yamaguti = （25+1+13+1+21+20+9） % 11 = 2

異なるキーが同じハッシュ値に 写像されたら、どうするか？ チェイン法 オープンアドレス法

衝突

_の処理

大きく分けて

チェイン法

ハッシュ表の同じ場所に写像された データを連結リストにつなぐ ハッシュ表は連結リストの先頭を指す ポインタ_の配列

Ａ Ｂ Ｃ Ｄ Ｅ Ｆ Ｇ Ｈ Ｉ Ｊ ハッシュ表 ０ １ ２ ３ ４ ５ ６ ７ ８ ９

オープンアドレス法

ある一定の方法で，空セルを探して， そこに新たな項目を挿入する方法 ①線形探査(linear probing) ②平方探査(quadratic probing) ③ダブルハッシュ(double hashing)

ｈ（ｘ）＝ｈ_０（ｘ） ｈ_１（ｘ） ｈ_２（ｘ） ｈ_３（ｘ） ハッシュ表 ： ： ： ： オープンアドレス 法は、ハッシュ表の 中で仮想的な連結 リストを作るようなもの ただし、次の要素は ポインタでなく、 再ハッシュ関数に よって決まる

オープンアドレス法：線形探査

• 配列を単純にシーケンシャルに辿って

空きセルを探すやり方

0 1 ….. 26 five 27 ten 28 29 eight …..

nine = 110+105+110+101

= 426

ハッシュ値= ４２６%100

=26

衝突 衝突

nine

OK

再ハッシュ（ｒｅｈａｓｈ） ｋ回目にアクセスする場所： ｈ_ｋ（ｘ） ｘはキー、ｋ＝０,１,２,・・・,Ｂ－１ 最も簡単な再ハッシュ関数は ｈ_{ｋ（ｘ）＝（ｈ（ｘ）＋ｋ） ％ Ｂ} ｈ（ｘ）：最初のハッシュ関数 Ｂ：ハッシュ表（配列）の大きさ

オープンアドレス法：線形探査 (2)

オープンアドレス法：線形探査の問題点

0 ….. 25 26 five 27 ten 28 nine 29 eight 30 この状態でさらにハッシュ値が ２６のキーを挿入する場合 データが連続してしまい， 効率が落ちる クラスター化

オープンアドレス法：平方探査

線形探査のように，隣接するセルに挿入してい くとクラスターができやすいので，もっと離れた 場所に挿入しようというやり方 ｈ_ｋ（ｘ）＝（ｈ（ｘ）＋ｋ2_{） ％ Ｂ} ｈ（ｘ）：最初のハッシュ関数 Ｂ：ハッシュ表（配列）の大きさ 注意点：配列のサイズを素数_{にしなければ} 同じ場所を探し続けることがある

オープンアドレス法：平方探査の問題点

サイズ５９の配列（すべてセルが空いているとする）に， １８４，３０２，４２０，５３８というキーを 順番に挿入することを考えると 184 % 59 = 7 → 1ステップで配列の要素８へ 302 % 59 = 7 → 2ステップで配列の要素11へ 420 % 59 = 7 → 3ステップで配列の要素16へ 538 % 59 = 7 → ４ステップで配列の要素23へ

第2種クラスター化

オープンアドレス法：ダブルハッシュ

• キーの値によって探査の歩幅が異なるように する方法 • キーに対して2度目のハッシュを行い，得られ た結果をステップ幅として使う ｈ_{s（ｘ）＝（C – （k % C）） ％ Ｂ} Ｂ：ハッシュ表（配列）の大きさ C: 定数（配列サイズより小さい素数）

オープンアドレス法：ダブルハッシュの注意点 • 最初のハッシュ関数と同じであってはならない • ０が作られることのある関数であってはならない • ハッシュ表のサイズは素数でなければならない – ハッシュ表のサイズが５９で，ステップ幅は？ 184 % 59 = 7 → 配列の要素８へ 302 % 59 = 7 →(11-(302%11))%59 = 6, 要素14へ 420 % 59 = 7 → (11-(420%11))%59= 9, 要素17へ 538 % 59 = 7 → (11-(538%11))%59=10,要素18へ ｈ_{s（ｘ）＝（１１ – （k % １１）） ％ ５９とすると}

良いハッシュ関数とは

• 手早い計算

– ハッシュ法の利点はスピードなので，ハッシュ関数は高速 であるべき

• ランダムキー

– Index = key % arraySizeで得られるインデクスもランダム （均等）に分布

• ノンランダムキー

– テーブルサイズには素数を使う

– 多くのキーと配列サイズに共通の公約数がある場合，そ れらが同じ位置へハッシュされるため

ハッシュ(2)

問題1： (2) (1)の表に示した文字列を上から順番に、要素数11のハッ シュ表に格納せよ。 (3)衝突が発生した場合には、チェイン法とオープンアドレス 法でそれぞれどのように衝突が回避されるかを図で示せ。 (4) オープンアドレス法は線形探査とダブルハッシュの両方を 示すこと。線形探査とダブルハッシュのハッシュ関数は以 下のとおり。 ｈ_{s（ｘ）＝（７ – （k % ７）） ％ 11} kはハッシュ関数hash()内の11で割った余りを求める直前の変数iの値 ｈ_{ｋ（ｘ）＝（ｈ（ｘ）＋ｋ） ％ １１} k回目にアクセスする場所（K=0, 1, 2, …, 10) 線形探査のハッシュ関数 ダブルハッシュのハッシュ関数