2014-6 - Researchmap

THE UNIVERSITY OF TOKYO
数理情報工学演習第一Ｃ
プログラミング演習 (第6回 )
2014/05/19
DEPARTMENT OF MATHEMATICAL INFORMATICS
1
THE UNIVERSITY OF TOKYO
今日の内容:
 文字列
 ハッシュ
 課題：ハッシュを用いた辞書
2
THE UNIVERSITY OF TOKYO
文字列
• 文字列は char の配列
• char name[] = “ABC”;
– nameは “ABC” を格納するのに十分な長さの配列
– 長さは，文字列の長さ + 1 (終端記号用)
• char name[4] = {‘A’, ‘B’, ‘C’, 0}; と書くのと同じ
• C言語の標準ライブラリでは，文字列の長さは明示的には格納せず，
終端記号 (0) で文字列の終わりを表現する
• char *name = “ABC”;
– nameはcharのポインタで，メモリ上のどこかに格納された “ABC\0” の
アドレスが代入される
3
THE UNIVERSITY OF TOKYO
文字列処理のライブラリ
• #include <string.h>
• char *strcpy(char *p, char *q);
– アドレス p から始まる領域に，q 以降の文字列をコピーする
– p 側の領域は，q を格納するために必要なサイズがなければならない
（無いとセキュリティホールになる）
– つまり，p 側のメモリはあらかじめ確保しておく必要がある
• char *strcat(char *p, char *q);
– 文字列 p の直後の領域に文字列 q をコピーする
• int strlen(char *s);
– 文字列 s の長さを返す．長さは終端記号は含まない．
4
THE UNIVERSITY OF TOKYO
• 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
THE UNIVERSITY OF TOKYO
ファイルから文字列を読み込む方法
• ファイル中の文字列の長さは任意であるため，注意しないとメモリを破壊して
しまう
– 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);
6
THE UNIVERSITY OF TOKYO
• 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);
7
THE UNIVERSITY OF TOKYO
ハッシュ表
• 辞書操作 (insert, delete, search) を効率よく実現するデータ構造
– insert(S, x): 集合 S に x を入れる
– delete(S, x): 集合 S から x を削除
– search(S, x): 集合 S から x を取り出す
• ハッシュ表は実際的な場面では極めて速い
– 妥当な仮定の下で，SEARCHの時間の期待値は O(1)
– リストで辞書を実現すると O(n)
– ただし，ハッシュも最悪の場合は (n)
8
THE UNIVERSITY OF TOKYO
連想配列
• 配列の添え字が整数以外のもの
– ID[“coffee”] = “コーヒー”; ID[“milk”] = “牛乳”;
• 実装法
– 配列に入れて線形探索 (全部見る)
– key の辞書順にソートして配列に格納し，2分探索
– 2分探索木に入れる
– ハッシュ
• ハッシュを使えば効率的に実装できる
9
THE UNIVERSITY OF TOKYO
直接アドレス表
出現する可能性のあるキーの全集合 (普遍集合, 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 と呼ぶ
10
THE UNIVERSITY OF TOKYO
T
1
U
(キーの普遍集合)
0
4
9 7 6
K (実際 2
のキー)
5
3
8
11
0
1
2
3
4
5
6
7
8
9
キー付属データ
2
3
5
8
THE UNIVERSITY OF TOKYO
辞書操作の実現
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 にオブジェクトそのものを格納してもいい
12
THE UNIVERSITY OF TOKYO
直接アドレス表の欠点
キーの普遍集合 U が大きい場合は非現実的
表 T をメモリに格納できない
T に割り付けた領域のほとんどが無駄になる
辞書に格納されているキーの集合 K が U に比べて十分に小さい場合は
ハッシュ表が有効
13
THE UNIVERSITY OF TOKYO
ハッシュ表
直接アドレス表では，キー k はスロット k に格納
ハッシュ表 T[0..m1] では，スロット h(k) に格納
h: ハッシュ関数 (hash function)
h: U  {0,1,,m1}
必要な領域: (|K|)
要素の探索: O(1) (平均時間)
14
THE UNIVERSITY OF TOKYO
ハッシュ関数の衝突
衝突 (collision): 2つのキーが同じスロットにハッシュされること
T
U
(キーの普遍集合)
h(k2)
h(k1)
K (実際 k1
のキー)
k3
k4
k2
15
h(k3) = h(k4)
THE UNIVERSITY OF TOKYO
衝突の回避方法
別のハッシュ関数を用いる
|U| > m なので完全に回避することは不可能
チェイン法
オープンアドレス法
16
THE UNIVERSITY OF TOKYO
チェイン法による衝突解決
同じスロットにハッシュされたすべての要素を連結リストに格納
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) 時間
17
THE UNIVERSITY OF TOKYO
リストの要素
• キーとバリューのペア (key, value) を格納
• key に従って要素を検索
• key は付属した値 value を持つ
• hashkey_t と value_t は自分で typedef する
typedef struct kvpair_ kvpair;
typedef struct dlobj_{
typedef struct kvpair_{
struct dlobj_ *next;
hashkey_t key;
struct dlobj_ *prev;
value_t value;
kvpair *x;
} kvpair;
} dlobj;
dlistではkvpairの中身の処理はしない
18
THE UNIVERSITY OF TOKYO
typedef struct dlobj_{
typedef struct kvpair_{
struct dlobj_ *next;
hashkey_t key;
struct dlobj_ *prev;
value_t value;
kvpair *x;
typedef char *hashkey_t;
typedef char *value_t;
} kvpair;
} dlobj;
head(L)
kvpair
coffee
19
コーヒー
milk
牛乳
sugar
砂糖
THE UNIVERSITY OF TOKYO
ハッシュ関数の選び方
• h: ハッシュ関数 (hash function)
– h: U  {0,1,,m1}
• x  y  h(x)  h(x) になるのが理想だが，|U| > m なら無理
• キーが文字列 (typedef char *hashkey_t) のとき，例えば
int hash_func(hashkey_t key) {
int h = 0;
while (*key != 0) {
h = h * 101 + tolower(*key++); // 小文字に変換してからハッシュ値を計算
}
return abs(h); // 非負の値にする
}
• この値を m (ハッシュ表のサイズ) で割った余りをハッシュ値とする
20
THE UNIVERSITY OF TOKYO
ハッシュの構造体
typedef struct {
int n; // ハッシュに格納されている要素数
int m; // ハッシュ表のサイズ
dist **T; // 双方向リストのポインタの配列(のポインタ)
} hash;
21
THE UNIVERSITY OF TOKYO
• 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;
}
22
THE UNIVERSITY OF TOKYO
dlist.cで使われる外部関数
• int kvpair_cmp(kvpair *x, kvpair *y);
– x のキーと y のキーが等しければ 0 を返す
– dlist_search() 内で使われる
• int kvpair_free(kvpair *x);
– x のメモリを開放する
– dlist_free() 内で使われる
• dlist.cでこれらの関数のプロトタイプ宣言をしておく
23
THE UNIVERSITY OF TOKYO
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を表示する
24
THE UNIVERSITY OF TOKYO
hash.h で定義するもの
• typedef char *hashkey_t; // キーは文字列
• typedef char *value_t; // valueも文字列
• typedef struct kvpair_ {
hashkey_t key;
value_t value;
} kvpair;
typedef struct {
int n;
int m;
dist **T;
} hash;
• hash の構造体
• hash.c で定義される関数のプロトタイプ宣言
25
THE UNIVERSITY OF TOKYO
課題 (ハッシュを用いた英和辞書)
 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);
26 ハッシュ表から要素 x を削除
THE UNIVERSITY OF TOKYO
• dlobj には文字列のポインタを格納しているので，
ファイルから読み込んだ文字列のメモリ管理に注意
• ファイルの各行は
– 英単語
日本語訳
• 5/21(水) の正午までに提出
• 宛先：[email protected]
27
THE UNIVERSITY OF TOKYO
余力のある人は
• 自由に使える英和辞書データとして
http://kujirahand.com/web-tools/EJDictFreeDL.php
• なお，見出しと訳はタブ文字 (‘∖t’) で区切られており，見出しは
空白文字を含んでいる
• scanfの %s で文字列を読むと，空白文字で区切られてしまう
• sscanf(buf, “%[^∖t] %[^∖n]”, buf1, buf2); とすると，
buf1 にはタブの直前までの文字列 (空白文字を含む)，
buf2 は行の最後までの文字列が入る
• 文字列はUNICODEなので注意
– Windows のコマンドプロンプトでは文字化けする
– UbuntuのterminalではUNICODEが標準
28
THE UNIVERSITY OF TOKYO

Download Report