第7回 探索問題
探索問題とは
配列や線形リスト，木構造などのデータ構造を使って蓄えられた情報の中から，必要な情報や条件(キー)と一致する情報を探し出すことが探索問題である．
例えば，次のように，氏名，住所，電話番号などの個人情報を蓄えるデータ要素を考える．データベースシステムなどの情報システムでは，このようなデータ要素の単位をレコードと呼ぶ．
typedef struct record {
int id; //ID(検索キー)
char name[40]; //氏名
char address[80]; //住所
char phone[12]; //電話番号
int age; //年齢
} RECORD;
このようなレコードが数千件，数万件蓄えられている配列データやデータベースから，目的となる人物のデータを取り出したり，例えば「年齢が20才以上の人物」，「住所が埼玉県」などの条件に一致するレコードを探し出すことが，探索問題である．
目的となる人物を探し出すためには，氏名だけでは，同姓同名の人が存在することがあるため，本人と別人を確認するために住所など他の項目も比較する必要が出てきてしまう．このため，一般的なデータベースシステムでは，通常はIDとして全データで重複のないことが保証される番号や記号を，別途割り当てておく．こうした検索用の項目(フィールドと呼ぶ)のことを「検索キー」と呼ぶ．
仮に，このようなデータが線形リストになっていた場合には，先頭から順にリストをたどって検索キーが一致するレコード(線形リストのノード)を探すことになる．数千件程度のデータならば，特に工夫をしなくとも，検索時間の長さは実用上問題にはならない．しかし，数万件を越えると高速化のための仕掛けやアルゴリズムの工夫が必要となる．例えばデータの五十音順に連結された線形リストに対して，「あ」「か」「さ」「た」「な」など各段の先頭位置へのポインタを用意しておければ，途中を飛ばして近い位置から探索を始められる．
次に，これらのアルゴリズムについて基本的なものを紹介する．
二分探索
二分探索(binary search)は，検索キーの大きさ順などでソート(整列)されている状態の配列データを前提とし，その中から効率よくキーが一致するデータを探し出すアルゴリズムである．
これは，例えば本の中から目的のページを探し出すときに，人間もよくやっている方法である．200ページの本があって，136ページを開きたかったとする．大抵の人は，まず真ん中くらいを適当に開けて，開いたページが目的の136ページよりも前か後ろか確認する．もしも後ろだったら，今度はそれより前の方でまた適当なページ(しかし，さっきの半分より確実にすくない1/4程度，半分の半分程度のページ)を開いてみる．そして目的のページとの前後関係を確認して，またさらに少ないページだけずらして開き，最終的に目的のページにたどり着く．
二分探索は，これを機械的に行う．最初にデータ配列のちょうど半分の位置の要素の検索キーを確認し，その前後関係から次は半分の半分，1/4のところを確認し，さらに1/8,1/16とずらしていきながら，最終的に目的の要素を探し出す．
これをC言語で書くと次のようになる．
#define N 100; //データの個数
RECORD r[N]; //RECORD型が上記個数分，ID順番で整列しているとする
int key; //探したいキー
int head; //探索範囲の先頭
int tail; //探索範囲の最後
int half; //真ん中
head = 0;
tail = N-1; //C言語で配列は0番からN-1番まで
do {
half = (head+tail)/2;
if( r[half].id == key ){ //keyと一致したら探索終了
printf(r[half]の中の必要な項目を表示);
exit(EXIT_SUCSESS);
}
else if( r[half].id < key )
head = half+1;
else
tail = half-1;
} while(head <= tail)
exit(EXIT_FAILURE); //探索失敗(keyが見つからなかった)
ハッシュ探索
ちょっとしたアドレス帳などのソフトウェアから本格的なデータベースシステムまで，よく使用されている探索アルゴリズムが，ハッシュ法である．ハッシュ法は，ハッシュ関数と呼ばれるキーの値から代表値(ハッシュ値と呼ぶ)を計算する関数を用いて，データの検索位置を決定する方法である．
まずデータを登録する表tableを考える，大きさは例えば100程度とし，table[100]とする．ここにデータを登録していく時点で，どの位置にデータを登録するかも，ハッシュ関数次第で決定する．検索キーに対してハッシュ関数で計算を行い，仮に18と計算されたとする．その場合には，table[18]にそのデータを登録する．逆に，データを検索するときには，検索キーを使ってまたハッシュ関数を計算し，答え18を得る．すると一発でtable[18]からデータを引き出せることになる．
例えば，五十音の電話帳に用いるハッシュ関数として単純なものでは，「あ」から始まる名前なら0，「い」なら1，などと先頭のよみだけで番号化するハッシュ関数が考えられる．他には，学籍番号をキーと考えれば，学籍番号と表の大きさの剰余(あまり)などが考えられる．
ハッシュ関数は，任意で構わないが，決定する際に問題となる点がハッシュ値の衝突(collision)である．違うキーに対するハッシュを計算した時に，同じハッシュ値が計算されることを衝突と呼ぶ．例えば，先ほどの五十音の例では，「たかはし」「たかだ」などの名前で衝突が起こる．
この衝突は，次のような具体的な問題を生じる．データ格納時に衝突が起こった場合には，格納先にすでに別のデータが格納されていることになる．また，データを探索している時には，衝突により探した先に目的のデータがないことになる．
表の大きさを，データの数と比較して十分大きくとり，ハッシュ関数の値域を広げることで衝突する頻度を減らすことができる．理論的には，限界まで表を広げられれば衝突は0になる．つまり，取りうるIDすべてを格納できる大きな表を用意できれば，衝突を0にできる．このときのハッシュ関数はなにもせず，IDそのままがハッシュ値となる．例えば日本工大の学籍番号を考えた場合，7桁の数字であるため，0番から9999999番までの表を用意できれば，衝突なしに直接必要なデータにアクセスできる．
しかし，当然そのためには膨大なメモリ量を必要とし，また現在在学している5000人程度の学生に対して，表の中の空き部分が非常に多くなり，メモリの効率があまりに悪い．ハッシュ法は，5000人の学生に対してせいぜい10000程度の大きさの表を用意し，7桁の学籍番号からハッシュ関数により0から9999までのハッシュ値に変換することで，高速な検索性能とメモリ効率の両方を満足しようとしているわけである．ちなみに，ハッシュ(hashing)とは，元々は肉を切り刻む言葉からきており，元のIDを切り刻んで小さくするイメージにより名づけられている．
衝突が起こった場合，対応の仕方によりハッシュ法はいくつかに分類される．代表的なものが，オープンアドレス法とチェーン法である．
オープンアドレス法
オープンアドレス法では，衝突が起こった場合には，再ハッシュを行う方式である．再ハッシュには，そのための別関数を用意する．別関数は任意だが，単純なものでは，元のハッシュ値に+1して表のサイズとの剰余をとったものなどがある．つまり，基本的に衝突したらとなりの場所を探させるわけである．再ハッシュしても衝突した場合には，再ハッシュを繰り返すことになる．
これにより，データを格納しようとした時にすでに別データが格納されている場合には，再ハッシュし，再ハッシュ先が空ならばそこに格納する．もしもそこも別データで埋まっていたら，空きを見つけるまで再ハッシュを繰り返す．もしも表の大きさに等しい回数再ハッシュを行っても空きが見つからない場合には，表が全部埋まっているため格納は失敗と判断させる．
データを探索する時には，ハッシュした値で探索し，目的のデータでなかった場合には，再ハッシュし，再ハッシュ先が目的のデータかどうか確認する．もしもそこも別データであったら，見つけるまで再ハッシュを繰り返す．もしも表の大きさに等しい回数再ハッシュを行っても目的のデータが見つからない場合，表が全部調べても見つからなかったとして失敗と判断させる．また，再ハッシュのいずれかで空に出会った時には，目的のデータがそもそも格納されていないとして，失敗と判断する．
チェイン法
チェイン法は，配列と線形リストを組み合わせたデータ構造を使用する．表として配列を用意するが，この表にはデータは格納せず，線形リストへのポインタを格納する．ハッシュ関数によりハッシュ値を計算し，その値によって配列の線形リストの一つを選択し，その線形リストにデータを追加する．
この方法では，衝突が起こっても，同じハッシュ値のデータを線形リストに追加したり，その線形リストをたどって探索すればよい．