教科書には本になった辞書から単語を探す手順が紹介されています。
ファイルから読み込んだ辞書データから単語をコンピュータに検索させる手順を考えます。
ejdic2k.txtの内容は次のようなものです。2001件あります。
英単語と意味の間はタブで区切ってあります。
a 一つの,ある ability 能力 able できる,有能な about について,およそ,around above の上方へ,の上に,前に abroad 海外へ(で),外国に(で),広く,広まって absence るす,欠席,ないこと absent 欠席した,放心した absolute まったくの,絶対的な力を持った accept 受け取る,認める,引き受ける accident 偶然,事故 .....................省略.........
上記のejdic2k.txtを読み込むプログラムです。
このプログラムはいままでに勉強していないものがたくさん含まれています。細かな所まで分からなくてもしかたありません。
1: #include <stdio.h>
2: #include <string.h>
3:
4: #define WORDS_NUM 2001 /*最大数(レコード数)*/
5: #define WORD_SIZE 20 /*単語のサイズ*/
6: #define JIMI_SIZE 200 /*説明のサイズ*/
7: #define SBUF_SIZE 256 /*文字列バッファのサイズ*/
8:
9: int main()
10: {
11: FILE *fp;
12: char istr[SBUF_SIZE];
13: char word[WORDS_NUM][WORD_SIZE];
14: char jimi[WORDS_NUM][JIMI_SIZE];
15: char *tmp;
16: int len, ct, i, dataerr;
17: int wlenmax=0;
18: int jlenmax=0;
19:
20: fp=fopen("ejdic2k.txt", "r");
21: if(fp==NULL){
22: printf("ファイル(ejdic2k.txt)を開けません\n");
23: return 1;
24: }
25: i=0;
26: while(fgets(istr, sizeof(istr), fp)!=NULL)
27: {
28: dataerr=0;
29: tmp=strtok(istr, "\t");
30: if(tmp!=NULL){
31: len=strlen(tmp);
32: if (len>wlenmax) wlenmax=len;
33: if(len>=WORD_SIZE) len=WORD_SIZE-1;
34: strncpy(word[i], tmp, len);
35: word[i][len]='\0';
36: }
37: else{
38: dataerr=1;
39: }
40: tmp=strtok(NULL, "\n");
41: if(dataerr==0 && tmp!=NULL){
42: len=strlen(tmp);
43: if (len>jlenmax) jlenmax=len;
44: if(len>=JIMI_SIZE) len=JIMI_SIZE-1;
45: strncpy(jimi[i], tmp, len);
46: jimi[i][len]='\0';
47: }
48: else{
49: dataerr=1;
50: }
51: if(dataerr==0) i++;
52: if(i>=WORDS_NUM) break;
53: }
54: ct=i;
55: fclose(fp);
56:
57: /* 読込んだデータの表示 */
58: for(i=0; i<ct; i++){
59: printf("%2d: %s\t%s\n", (i+1), word[i], jimi[i]);
60: }
61: printf("件数=%d\n", ct);
62: printf("w max=%2d: j max=%d\n", wlenmax,jlenmax);
63: return 0;
64: }
実行結果はこうなります。
........省略.......... 1997: yet まだ,もう,それにもかかわらず 1998: yield 産出する,明け渡す,作物がてきてる,屈する 1999: you あなた[がた]は(を) 2000: young 若い,年下のほうの 2001: youth 若さ,青年時代,青年 件数=2001 w max=14: j max=121
k0902.cのreturn 0;の前(k0902.cの62:と63:の間)に挿入し、k0903.c として保存、コンパイルすること
63: /* 検索 */
64: printf( "検索する単語を入力してください \n" );
65: scanf("%s", istr);
66: printf("%s\n", istr);
67: i=0;
68: while (strcmp(istr,word[i])!=0){
69: i++;
70: if (i>ct) break;
71: }
72: if (i>ct){
73: printf( "ありません\n" );
74: }else{
75: printf( "%s \n",jimi[i] );
76: printf( "%d 回比較しました\n",i );
77: }
78: /*この後に return 0; が来ます*/
「検索する単語を入力してください」に「you」と入れると、実行結果はこうなります。
........省略.......... 件数=2001 w max=14: j max=121 検索する単語を入力してください you you あなた[がた]は(を) 1998 回比較しました
最後に出ているのは、見つかるまでの比較回数です。最近のコンピュータの能力が高いので、時間の差をあまり感じません。そこで比較回数を表示しました、比較回数が少ないほうが効率の良い検索という事になります。
単語はabc順に並んでいますから、aに近い単語は比較回数が少なく、zに近い単語は比較回数が多くなります。
辞書に存在する単語のみ引いたとすると、平均して登録単語数の半分の比較回数で見つかることになります。
探索方法を二分法探索に替えてやってみます。(Binary Search)
k0902.cのreturn 0;の前(62:と63:の間)に挿入し、k0904.c として保存、コンパイルすること
63:
64: /* 検索 */
65: printf( "検索する単語を入力してください \n" );
66: scanf("%s", istr);
67: printf("%s\n", istr);
68: i=0;
69: int first = 0;
70: int last = ct-1;
71: int found = -1;
72: int mid, scmp;
73: while ( last>=first ){
74: mid = (first+last)/2;
75: i++;
76: scmp = strcmp(istr,word[mid]);
77: printf("%4d %4d %4d %4d %s %s \n",first,last,mid,scmp,istr,word[mid]);
78: if (scmp==0){
79: found = mid;
80: }
81: if(scmp>0){
82: first = mid+1;
83: }
84: else{
85: last = mid-1;
86: }
87: if (scmp==0)break;
88: }
89: if (0>found){
90: printf( "ありません\n" );
91: printf( "%d 回比較しました\n",i );
92: }else{
93: printf( "%s \n",jimi[found] );
94: printf( "%d 回比較しました\n",i );
95: }
96: /*この後に return 0; が来ます*/
実行結果は
........省略.......... 件数=2001 w max=14: j max=121 検索する単語を入力してください you you 0 2000 1000 13 you lodge 1001 2000 1500 6 you scarce 1501 2000 1750 5 you tall 1751 2000 1875 4 you urgent 1876 2000 1938 2 you when 1939 2000 1969 2 you with 1970 2000 1985 2 you wound 1986 2000 1993 10 you yellow 1994 2000 1997 6 you yield 1998 2000 1999 -110 you young 1998 1998 1998 0 you you あなた[がた]は(を) 11 回比較しました
比較回数は最大で全体数を2で割りつづけて、1になる程度と言えます。ちょうど1/2のところにあったという幸運がであればもっと少なくなります。2001ならば大体 1000,500,250,125,64,32,16,8,4,2,1 ですから11回程度で見つかります。
二分探索をするには単語が文字コード順に並んでいる必要があります。
約2000件のデータから探索する場合、単純前方探索は平均で1000回程度、二分法探索では11回程度の比較で見つけられることがわかりました。データの数が多くなるとこの差はますます広がります。
| データ数 | 単純前方探索 | 二分法探索 |
|---|---|---|
| 2000 | 1000 | 11 |
| 20000 | 10000 | 14 |
| 200000 | 100000 | 18 |
| n | O(n) | O(log2 n) |
これだけから考えると、二分法探索が優れているようですが、ちょっと待ってください。二分法探索はデータが大きさの順に並んでいる必要があります。並んでいない場合は並べかえる手間も考慮に入れる必要があります。
また、複数のデータが合致する場合には二分法探索では対処が難しくなります。
聖愛中学高等学校