1 T HE U NIVERSITY OF T OKYO D EPARTMENT OF M ATHEMATICAL I NFORMATICS 数理情報工学演習第一Ｃ プログラミング演習 ( 第 6 回 ) 2014/05/19

2 T HE U NIVERSITY OF T OKYO 今日の内容 :  文字列  ハッシュ  課題： ハッシュを用いた辞書

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

4 T HE U NIVERSITY OF T OKYO 文字列処理のライブラリ #include char *strcpy(char *p, char *q); – アドレス p から始まる領域に， q 以降の文字列をコピーする –p 側の領域は， q を格納するために必要なサイズがなければならない （無いとセキュリティホールになる） – つまり， p 側のメモリはあらかじめ確保しておく必要がある char *strcat(char *p, char *q); – 文字列 p の直後の領域に文字列 q をコピーする int strlen(char *s); – 文字列 s の長さを返す．長さは終端記号は含まない．

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

6 T HE U NIVERSITY OF T OKYO ファイルから文字列を読み込む方法 ファイル中の文字列の長さは任意であるため，注意しないとメモリを破壊して しまう –char buf[10]; –fscanf(f, “%s”, buf); // 長さが 10 以上の文字列が来るとメモリを破壊 長い文字列が来たときは途中で捨てる char *fgets(char *s, int n,FILE *f); – ファイル f から s の領域に 1 行 ( 最大 n バイト ) 読み込む –char buf[10], p[10], q[10]; –fgets(buf, 10, f);

7 T HE U NIVERSITY OF T OKYO int sscanf(char *s, char *format,...); – 文字列 s から format に従って変数に読み込む –sscanf(buf, “%s %s”, p, q); // buf から文字列を取り出して p, q にコピー –char *p2, *q2; –p2 = malloc(strlen(p)+1); // +1 は終端記号の分 –q2 = malloc(strlen(q)+1); –strcpy(p2, p); –strcpy(q2, q);

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

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

10 T HE U NIVERSITY OF T OKYO 直接アドレス表 出現する可能性のあるキーの全集合 ( 普遍集合, 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 と呼ぶ

11 T HE U NIVERSITY OF T OKYO U ( キーの普遍集合 ) K ( 実際 のキー ) キー付属データ T

12 T HE U NIVERSITY OF T OKYO 辞書操作の実現 DIRECT_ADDRESS_SEARCH(T,k) return T[k] DIRECT_ADDRESS_INSERT(T,x) T[key(x)] = x DIRECT_ADDRESS_DELETE(T,x) T[key(x)] = NULL いずれも O(1) 時間 T にオブジェクトそのものを格納してもいい

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

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

15 T HE U NIVERSITY OF T OKYO ハッシュ関数の衝突 衝突 (collision): 2 つのキーが同じスロットにハッシュされること k1k1 U ( キーの普遍集合 ) K ( 実際 のキー ) T k2k2 k3k3 k4k4 h(k2)h(k2) h(k1)h(k1) h(k 3 ) = h(k 4 )

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

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

18 T HE U NIVERSITY OF T OKYO リストの要素 キーとバリューのペア (key, value) を格納 key に従って要素を検索 key は付属した値 value を持つ hashkey_t と value_t は自分で typedef する typedef struct kvpair_ kvpair; typedef struct dlobj_{ struct dlobj_ *next; struct dlobj_ *prev; kvpair *x; } dlobj; dlist では kvpair の中身の処理はしない typedef struct kvpair_{ hashkey_t key; value_t value; } kvpair;

19 T HE U NIVERSITY OF T OKYO head(L) coffee コーヒー kvpair milk 牛乳 sugar 砂糖 typedef struct dlobj_{ struct dlobj_ *next; struct dlobj_ *prev; kvpair *x; } dlobj; typedef struct kvpair_{ hashkey_t key; value_t value; } kvpair; typedef char *hashkey_t; typedef char *value_t;

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

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

22 T HE U NIVERSITY OF T OKYO dlist.c では， 2 つの kvpair のキーが等しいかを判定する関数が必要 dlist.c の外部で定義されている関数を使用する int kvpair_cmp(kvpair *x, kvpair *y); // 外部で定義されている関数 dlobj *dlist_search(dlist *L, kvpair *x){ dlobj *now = L->nil->next; while(now != L->nil){ if(kvpair_cmp(now->x, x) == 0){ return now; } now = now->next; } return NULL; }

23 T HE U NIVERSITY OF T OKYO dlist.c で使われる外部関数 int kvpair_cmp(kvpair *x, kvpair *y); –x のキーと y のキーが等しければ 0 を返す –dlist_search() 内で使われる int kvpair_free(kvpair *x); –x のメモリを開放する –dlist_free() 内で使われる dlist.c でこれらの関数のプロトタイプ宣言をしておく

24 T HE U NIVERSITY OF T OKYO hash.c で定義する関数 static int hash_func(hashkey_t key); – ハッシュ値の計算 –hash.c 内部のみで使われる int kvpair_cmp(kvpair *x, kvpair *y); int kvpair_free(kvpair *x); void kvpair_print(kvpair *x); –key と value を表示する

25 T HE U NIVERSITY OF T OKYO hash.h で定義するもの typedef char *hashkey_t; // キーは文字列 typedef char *value_t; // value も文字列 hash の構造体 hash.c で定義される関数のプロトタイプ宣言 typedef struct kvpair_ { hashkey_t key; value_t value; } kvpair; typedef struct { int n; int m; dist **T; } hash;

26 T HE U NIVERSITY OF T OKYO 課題 ( ハッシュを用いた英和辞書 )  hash *hash_new(int m);  表のサイズが m のハッシュ表を作る  dlobj *hash_search(hash *H, hashkey_t key);  キーが key である要素を返す  注 : dlist_search も文字列の比較をするように変更する  dlobj を返す理由は，削除を高速にするため  void hash_insert(hash *H, hashkey_t key, value_t value);  kvpair (key, value) を作り，ハッシュ表に入れる  同じものは H に無いと仮定 (search して無かったときだけ入れる )  void hash_delete(hash *H, dlobj *x);  ハッシュ表から要素 x を削除

27 T HE U NIVERSITY OF T OKYO dlobj には文字列のポインタを格納しているので， ファイルから読み込んだ文字列のメモリ管理に注意 ファイルの各行は – 英単語 日本語訳 5/21( 水 ) の正午までに提出 宛先：

28 T HE U NIVERSITY OF T OKYO 余力のある人は 自由に使える英和辞書データとして なお，見出しと訳はタブ文字 (‘ ∖ t’) で区切られており，見出しは 空白文字を含んでいる scanf の %s で文字列を読むと，空白文字で区切られてしまう sscanf(buf, “%[^ ∖ t] %[^ ∖ n]”, buf1, buf2); とすると， buf1 にはタブの直前までの文字列 ( 空白文字を含む ) ， buf2 は行の最後までの文字列が入る 文字列は UNICODE なので注意 –Windows のコマンドプロンプトでは文字化けする –Ubuntu の terminal では UNICODE が標準