(cache) アルゴリズム基礎論演習2009
課題10 「内部ハッシュ法」
内容
内部ハッシュ法を用いて、辞書A に対して文字列x を挿入する手続きinsert(x,A) と、
辞書A に文字列x が含まれているかを検索するmember(x,A) を実装せよ。
※ 文字列x の最大文字数をL=10 とし、辞書のサイズをB=15 とする。
※ 辞書内に同じ要素が2つ以上含まれてはならない。(重複を許可しない)
入力
入力は、辞書に挿入する文字列 、および、検索する文字列 とする。
※ 各入力の終了条件は自由。
例えば、特殊文字列（''や'end'など）が入力されたら入力を終了するなど。
出力
出力は、検索を実行した際に、検索した文字列が辞書に含まれているかどうか を出力すること。
実行
今回は、辞書に名前を挿入する。
まず、辞書に対して以下の名前を挿入する。
【挿入】
・endou
・katou
・suzuki
・nishizawa
・hayashi
・wada
次に、辞書に対して以下の名前を検索する。
【検索】
・endou
・wada
・watanabe
ヒント
出力例
入力を赤字 で示した。
この出力例では、各入力の終了条件を空文字（''）の入力としてある。
INSERT : input name (finish : empty input)
input name to insert dictionary:suzuki
input name to insert dictionary:nakamura
input name to insert dictionary:wada
input name to insert dictionary:
SEARCH : input name (finish : empty input)
input name to search from dictionary:suzuki
suzuki is found.
input name to search from dictionary:tanaka
tanaka is not found.
input name to search from dictionary:
内部ハッシュ法による辞書構築
集合Aに対して以下の3つの演算のみが適用されるとき、集合Aのことを辞書という。
・INSRET(x,A) : 集合A に 要素x を挿入する
・DELETE(x,A) : 集合A から 要素x を削除する（注意：今回の課題では作成しない ）
・MEMBER(x,A) : 集合A に 要素x が含まれているかを判定する
単純に辞書を作成するだけであれば、配列や連結リストに次々と要素を挿入していけば簡単に作れる。
しかし、これでは要素の検索や削除を行う際に、辞書の中身を始めから順繰りに調べなければならない。
このような手間を削減する方法のひとつが、今回学習する内部ハッシュ法 である。
内部ハッシュ法では、まず、図1のような要素を格納する大きさB の配列を用意する。
ここで注意してもらいたいのが、配列の番号が1からBではなく、0 から(B-1) になっていることだ。
これには、内部ハッシュ法の要となるハッシュ関数 というものが大きく関わってきている。
私たちは辞書に検索をかけるとき、辞書の全てを確認することなく１発で目的の単語を配列の中から探し出したい。
ようするに、本の最後などに載っている『索引』 がほしいのである。
この索引に相当する機能を持っているのがハッシュ関数 である。
ハッシュ関数は、なんらかの名前を与えると、値 n (0≦n≦B-1 : nをハッシュ値と呼ぶ)を出力してくれる関数である。
名前(アルファベット)を“word” とし、wordの中身を以下のように1文字ずつに分割する。
今回は、最大文字数が10文字なのでwordの大きさ(L )は10としてある。
この時、ハッシュ関数は以下のように定義される。
ここで、ord(a) という関数は、引数として与えた文字の整数コード(ASCIIなど)を出力する関数であり、
B は配列のサイズで今回は15である。
例えば、word が 'apple' という単語だった場合は以下のようになる。
------------------------------------------------------------------------------------------------------
word = 'apple '
ord('a') = 97 , ord('p') = 112 , ord('l') = 108 , ord('e') = 101 , ord('') = 0
h(word) = (97 + 112 + 112 + 108 + 101 + 0 + 0 + 0 + 0 + 0) mod B
= 530 mod 15
= 5
※ 文字列の最大長が10と設定してあるので、空文字が5個分カウントされる。
------------------------------------------------------------------------------------------------------
この結果より、'apple'を配列番号5の場所に格納する。
こうすることにより、辞書に対して検索をかけるとき、検索する名前をハッシュ関数に通すことで
配列のどの部分に格納されているのかを１発で調べることが可能になる。
しかし、この格納方法にはひとつ問題がある。
ハッシュ関数はランダム性の高い関数ではあるが、必ずしも異なるハッシュ値を出力し続けるわけではない。
例えば、word が 'mango' だった場合、
------------------------------------------------------------------------------------------------------
word = 'mango '
ord('m') = 109 , ord('a') = 97 , ord('n') = 110 , ord('g') = 103 , ord('o') = 111 , ord('') = 0
h(word) = (109 + 97 + 110 + 103 + 111 + 0 + 0 + 0 + 0 + 0) mod B
= 530 mod 15
= 5
------------------------------------------------------------------------------------------------------
といったように、'apple'の時と同じ値が出力されてしまう。
先に'apple'を辞書に登録していた場合、なんの処理もしなければ'mango'が新しく上書きされてしまう。
このような問題を回避するために、例外処理を加える必要がある。
その例外処理とは、後から加えられる'mango'のような要素のハッシュ値を変更することである。
具体的には、以下のような式を適用してハッシュ値をずらす。
もし、ずらしたハッシュ値の場所にも既に要素が格納してある場合は、空配列が見つかるまでi の値を増加させる。
この時、iの値がBになっても空配列が見つからない場合は、辞書が一杯になっている。
例外処理の為とはいえ、この方法を用いると検索する要素を1発で探し出せなくなってしまう。
つまり、ハッシュ関数で探し出した場所に検索している要素と異なるものが格納されていたとしても、
この例外処理によってずれた場所に格納されている可能性が出てきてしまう。
最悪、辞書が完全に埋まっている状態で、辞書に含まれていない要素を検索した時、
全ての要素を検索し終えないと「辞書に含まれていなかった」という結論が得られないのである。
とは言え、辞書が完全に埋まってしまうほど、Bの値をギリギリに設定したりしなければ、
何の工夫もなく辞書を作成するよりも効率よく検索を行うことができる。
注意点
課題を作成する上で、注意すべき点は大体以下の4つ。
・辞書は必ず初期化する
・余剰演算(mod)の優先順位に注意する
・辞書が一杯である場合の処理を忘れない
（この処理をしないとハッシュ値をずらし続けてループに入る）
・LとBを逆に適用しないこと
追記(2010/01/04)
計算機環境の違いにより、整数コードがIEDでは異なっていた。
IED環境下では、正しくは以下のようになる。
------------------------------------------------------------------------------------------------------
word = 'apple '
ord('a') = 97 , ord('p') = 112 , ord('l') = 108 , ord('e') = 101 , ord('') = 32
h(word) = (97 + 112 + 112 + 108 + 101 + 32 + 32 + 32 + 32 + 32 ) mod B
= 690 mod 15
= 0
------------------------------------------------------------------------------------------------------
課題を作成する上で特別問題になる点ではないが、参考までに。
今回は、最大文字数が10文字なのでwordの大きさ(L)は10としてある。 この時、ハッシュ関数は以下のように定義される。
ここで、ord(a)という関数は、引数として与えた文字の整数コード(ASCIIなど)を出力する関数であり、 Bは配列のサイズで今回は15である。 例えば、word が 'apple' という単語だった場合は以下のようになる。 ------------------------------------------------------------------------------------------------------ word = 'apple ' ord('a') = 97 , ord('p') = 112 , ord('l') = 108 , ord('e') = 101 , ord('') = 0 h(word) = (97 + 112 + 112 + 108 + 101 + 0 + 0 + 0 + 0 + 0) mod B = 530 mod 15 = 5 ※ 文字列の最大長が10と設定してあるので、空文字が5個分カウントされる。 ------------------------------------------------------------------------------------------------------ この結果より、'apple'を配列番号5の場所に格納する。 こうすることにより、辞書に対して検索をかけるとき、検索する名前をハッシュ関数に通すことで 配列のどの部分に格納されているのかを１発で調べることが可能になる。 しかし、この格納方法にはひとつ問題がある。 ハッシュ関数はランダム性の高い関数ではあるが、必ずしも異なるハッシュ値を出力し続けるわけではない。 例えば、word が 'mango' だった場合、 ------------------------------------------------------------------------------------------------------ word = 'mango ' ord('m') = 109 , ord('a') = 97 , ord('n') = 110 , ord('g') = 103 , ord('o') = 111 , ord('') = 0 h(word) = (109 + 97 + 110 + 103 + 111 + 0 + 0 + 0 + 0 + 0) mod B = 530 mod 15 = 5 ------------------------------------------------------------------------------------------------------ といったように、'apple'の時と同じ値が出力されてしまう。 先に'apple'を辞書に登録していた場合、なんの処理もしなければ'mango'が新しく上書きされてしまう。 このような問題を回避するために、例外処理を加える必要がある。 その例外処理とは、後から加えられる'mango'のような要素のハッシュ値を変更することである。 具体的には、以下のような式を適用してハッシュ値をずらす。
もし、ずらしたハッシュ値の場所にも既に要素が格納してある場合は、空配列が見つかるまでiの値を増加させる。 この時、iの値がBになっても空配列が見つからない場合は、辞書が一杯になっている。 例外処理の為とはいえ、この方法を用いると検索する要素を1発で探し出せなくなってしまう。 つまり、ハッシュ関数で探し出した場所に検索している要素と異なるものが格納されていたとしても、 この例外処理によってずれた場所に格納されている可能性が出てきてしまう。 最悪、辞書が完全に埋まっている状態で、辞書に含まれていない要素を検索した時、 全ての要素を検索し終えないと「辞書に含まれていなかった」という結論が得られないのである。 とは言え、辞書が完全に埋まってしまうほど、Bの値をギリギリに設定したりしなければ、 何の工夫もなく辞書を作成するよりも効率よく検索を行うことができる。