memo

計数工学プログラミング演習 ( 第 5 回 ) 2017/05/09 DEPARTMENT OF MATHEMATICAL INFORMATICS 1

内容 文字列 双方向リスト ハッシュ 2

文字列 文字列は char の配列 char name[] = ABC ; name は ABC を格納するのに十分な長さの配列 長さは, 文字列の長さ + 1 ( 終端記号用 ) char name[4] = { A, B, C, 0}; と書くのと同じ C 言語の標準ライブラリでは, 文字列の長さは明示的には格納せず, 終端記号 (0) で文字列の終わりを表現する char *name = ABC ; name は char のポインタで, メモリ上のどこかに格納された ABC 0 のアドレスが代入される 3

文字列処理のライブラリ #include <string.h> // 文字列処理の関数 #include <ctype.h> // 文字変換 ( 大文字 / 小文字 ) の関数 char *strcpy(char *p, char *q); アドレス p から始まる領域に,q 以降の文字列をコピーする p 側の領域は,q を格納するために必要なサイズがなければならない ( 無いとセキュリティホールになる ) つまり,p 側のメモリはあらかじめ確保しておく必要がある int strlen(char *s); 文字列 s の長さを返す. 長さは終端記号は含まない. 4

int strcmp(char *p, char *q); 文字列 p と q を比較して, 等しければ 0, 辞書順で p < q ならば負の値,p > q ならば正の値を返す if (p == q) とは意味が異なるので注意 p == q はアドレスの比較をしているだけ strcmp(p, q) == 0 は, アドレスは違っても中身が同じなら成立 int strcasecmp(char *p, char *q); 英文字列で, 大文字 / 小文字を区別せずに比較 環境によっては stricmp という名前の場合もある 5

標準入力から文字列を読み込む方法 scanf で %s を用いる char buf[10]; scanf( %s, buf); 文字列の長さは任意であるため, 注意しないとメモリを破壊してしまう 上の例では, 長さが 10 以上の文字列が来るとメモリを破壊 今回の演習では, 文字列の長さには上限があるとして良い 大きな領域を用意し, そこに一旦読み込み, 文字列の長さを求めてそれを格納するのに十分なだけの領域を malloc してそこにコピーする. char *p; p = malloc(strlen(buf)+1); strcpy(p, buf); 6

双方向リストの構造体 リストの要素 双方向リスト typedef struct dlobj { struct dlobj *prev; // 前の要素へのポインタ struct dlobj *next; // 後の要素へのポインタ int key; // キー } dlobj; typedef struct { dlobj *head; } dlist; // 先頭要素のポインタ 7

連結リストの探索 dlist_search(l, k): リスト L に属する, キー k を持つ最初の要素のポインタを返す キー k を持つ要素が存在しなければ NULL を返す O(n) 時間 head(l) dlobj *dlist_search(dlist *L, int k) { dlobj *x; x = L->head; while (x!= NULL && x->key!= k) { x = x->next; } return x; } 9 16 4 8

連結リストへの挿入 dlist_insert(l, x): x を L の先頭に挿入 x のキーは既にセットされているとする O(1) 時間 x 9 head(l) void dlist_insert(dlist *L, dlobj *x) { x->next = L->head; if (L->head!= NULL) L->head->prev = x; L->head = x; x->prev = NULL; } 16 4 head(l) 9 16 4 9

連結リストからの削除 dlist_delete(l, x): L から x を削除 O(1) 時間 void dlist_delete(dlist *L, dlobj *x) { if (x->prev!= NULL) x->prev->next = x->next; else L->head = x->next; if (x->next!= NULL) x->next->prev = x->prev; } head(l) head(l) x 9 16 4 9 4 10

ハッシュ表 辞書操作 (insert, delete, search) を効率よく実現するデータ構造 insert(s, x): 集合 S に x を入れる delete(s, x): 集合 S から x を削除 search(s, x): 集合 S から x を取り出す ハッシュ表は実際的な場面では極めて速い 妥当な仮定の下で,SEARCHの時間の期待値は O(1) リストで辞書を実現すると O(n) ただし, ハッシュも最悪の場合は (n) 11

連想配列 配列の添え字が整数以外のもの ID[ coffee ] = コーヒー ; ID[ milk ] = 牛乳 ; 実装法 配列に入れて線形探索 ( 全部見る ) key の辞書順にソートして配列に格納し,2 分探索 2 分探索木に入れる ハッシュ ハッシュを使えば効率的に実装できる 12

直接アドレス表 出現する可能性のあるキーの全集合 ( 普遍集合, universal set) が大きくない場合にうまく働く キーが普遍集合 U = {0,1,, m 1} から選択され, どの 2 つの要素も同じキーをもたないと仮定する 直接アドレス表 (direct-access table) T で辞書を表現する 配列 T[0..m 1] の各要素が U のキーに対応 T[k] は, キー k を持つ要素をさす. そのような要素がなければ T[k] = NIL T[k] をスロット k と呼ぶ 13

1 U ( キーの普遍集合 ) 0 4 9 7 K ( 実際 2 のキー ) 5 3 8 6 T 0 1 2 3 4 5 6 7 8 9 キー付属データ 2 3 5 8 14

直接アドレス表の欠点 キーの普遍集合 U が大きい場合は非現実的 表 T をメモリに格納できない T に割り付けた領域のほとんどが無駄になる 辞書に格納されているキーの集合 K が U に比べて十分に小さい場合はハッシュ表が有効 15

ハッシュ表 直接アドレス表では, キー k はスロット k に格納 ハッシュ表 T[0..m 1] では, スロット h(k) に格納 h: ハッシュ関数 (hash function) h: U {0,1,,m 1} 必要な領域 : ( K ) 要素の探索 : O(1) ( 平均時間 ) 16

ハッシュ関数の衝突 衝突 (collision): 2 つのキーが同じスロットにハッシュされること T U ( キーの普遍集合 ) h(k 2 ) h(k 1 ) K ( 実際 k 1 のキー ) k 3 k 2 k 4 h(k 3 ) = h(k 4 ) 17

衝突の回避方法 別のハッシュ関数を用いる U > m なので完全に回避することは不可能 チェイン法 オープンアドレス法 18

チェイン法による衝突解決 同じスロットにハッシュされたすべての要素を連結リストに格納 hash_insert(t,x) リスト T[h(x->key)] の先頭に x を挿入, O(1) 時間 hash_search(t,k) リスト T[h(k)] の中からキー k を持つ要素を探索 hash_delete(t,x) リスト T[h(x->key)] から x を削除, 双方向リストを用いれば O(1) 時間 19

ハッシュの構造体 typedef struct { int n; // ハッシュに格納されている要素数 int m; // ハッシュ表のサイズ dlist **T; // 双方向リストのポインタの配列 ( のポインタ ) } hash; 20

ハッシュ関数の選び方 h: ハッシュ関数 (hash function) h: U {0,1,,m 1} x y h(x) h(x) になるのが理想だが, U > m なら無理 キーが文字列 (typedef char *hashkey_t) のとき, 例えば int hash_func(char *key) { int h = 0; while (*key!= 0) { h = h * 101 + tolower(*key++); // 小文字に変換してからハッシュ値を計算 } return abs(h); // 非負の値にする } この値を m ( ハッシュ表のサイズ ) で割った余りをハッシュ値とする 21

課題 ( ハッシュを用いた英和辞書 ) プログラムの入力は各行が1つの操作に対応 行の最初の単語が i 英語とその和訳を辞書に登録 (insert) i coffee コーヒー すでに辞書にある単語を再登録することは無い 行の最初の単語が d 英語とその和訳を辞書から削除 (delete) d milk その単語が辞書に存在しないときは何もしない 行の最初の単語が s 英語とその和訳を表示 (search) s milk key[milk] = 牛乳と表示 (UNICODE) 辞書にない場合は Not found と表示 行を読み込めなかったときはプログラムを終了する 22

main 関数の最後は return 0; をつけておく 提出するソースコードの中に, 学生証番号, 氏名, メールアドレスをコメントとして書いておく 締切 : 2017 年 5 月 9 日 ( 火 ) 17:35 ( 演習終了時 ) 23

ハッシュ表に格納される構造体 ( 英語と日本語のペア ) typedef struct dlobj { struct dlobj *prev; // 前の要素へのポインタ struct dlobj *next; // 後の要素へのポインタ char *eng; // 英語 ( 文字列へのポインタ ) char *jpn; // 日本語 ( 文字列へのポインタ ) } dlobj; dlobj には文字列のポインタを格納しているので, ファイルから読み込んだ文字列のメモリ管理に注意 24

キーの比較は文字列比較の関数で行う dlobj *dlist_search(dlist *L, char *key){ dlobj *now = L->head; while(now!= NULL){ if(strcasecmp(now->eng, key) == 0){ return now; } now = now->next; } return NULL; } 25

作成する関数 hash *hash_new(int m); 表のサイズが m のハッシュ表を作る dlobj *hash_search(hash *H, char *key); キー ( 英単語 ) が key である要素を返す dlobjを返す理由は, 削除を高速にするため void hash_insert(hash *H, char *eng, char *jpn); 英語と日本語のペアをハッシュ表に入れる 同じものは H に無いと仮定 (searchして無かったときだけ入れる) void hash_delete(hash *H, dlobj *obj); ハッシュ表から要素 obj を削除 ハッシュ表内のどのリストから削除するかは obj からハッシュ値を計算して決める 26

main 関数の例 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> int main() { hash *H; char buf1[100], buf2[100]; char *eng, *jpn; dlobj *obj; H = hash_new(100); while (1) { if (scanf( %s, buf1) < 1) break; // コマンドを読み込む // 入力が無ければループを抜ける 27

if (buf1[0] == i ) { // コマンドが i ( 挿入 ) の場合 scanf(" %s %s", buf1, buf2); // 2 つの文字列を読み込む eng = malloc(strlen(buf1)+1); // key を格納するメモリを確保 strcpy(eng, buf1); // 確保した領域に内容をコピー jpn = strdup(buf2); // 上 2 行と同様のことをする関数 hash_insert(h, eng, jpn); // ハッシュ表に単語を挿入 } else if (buf1[0] == d ) { // コマンドが d ( 削除 ) の場合 scanf( %s, buf1); // 英単語を読み込む obj = hash_search(h, buf1); // 英単語を探す if (obj!= NULL) { // 見つかった場合 hash_delete(h, obj); // ハッシュ表から削除 dlobj_free(obj); // ハッシュ表から削除したオブジェクトのメモリを開放 } } else 28

if (buf1[0] == s ) { // コマンドが s ( 検索 ) の場合 scanf( %s, buf1); // 英単語を読み込む obj = hash_search(h, buf1); // 英単語を検索 if (obj == NULL) { // 見つからなかった場合 printf("not found n"); } else { // 見つかった場合はそれを表示 printf("key[%s] = %s n", obj->eng, obj->jpn); } } else break; // コマンドがそれ以外の時はループから抜ける } hash_free(h); // ハッシュ表のメモリを開放 return 0; } 29

void hash_insert(hash *H, char *eng, char *jpn) { dlobj *obj; int h; obj = dlobj_new(eng, jpn); // 英語と日本語の文字列へのポインタを含むリストの要素を作る h = hash_func(eng) % H->m; // 英語文字列からハッシュ値を計算 dlist_insert(h->t[h], obj); // h に対応するリストの先頭に挿入 H->n++; } 30