サーチ：条件に合うものを探す

サーチ(検索)は、大量あるデータの中から、目的に合致したものを探し出す作業です。ものを探すという場合

などの場合があります。「だいたい」というのは、その判断基準が難しいので、ここでは「ピッタリ」と「一番近い」ものを考えます。おそらく、多くの人は WWW でサーチエンジン、「検索」といったものを使ったことがあるかと思います。これらも、大量の情報の中からデータを探し出す作業です。数秒かかるだけで「おせ〜」などと思うかも知れませんが、莫大なデータから秒単位で出てくるだけでも、あれらのシステムは物凄く高機能なんです。

「一致するものを探す」のと、「部分的に一致するもの」は違うようで実は一緒です。と、いうのは、一致しているかどうかの判定に「全部を調べるか」「一部を調べるか」という違いがあるのみで、最終的にはYes/Noしかでてきません。また、複数が該当する可能性があります。それに対して、３つ目の「近いものを探す」は「どの程度近いか」という評価数値を必要とします。ここでは、指定した点からの距離を評価に使うことにします。もちろん、「最も」なので、該当は一つです(二つ「最も」がある可能性もありますが、今回は無視します)。

前提プログラム作成

今回のプログラムでは、前回作成したmap2.datを構造体変数crossに読み込んで使用することが前提です。しかし、データの形式としては下記のようなセットを用意する方が実用的であることも覚えておいてください（できる人はmap2.datを少し加工して、下記のようなやりかたで全体のデータを読み込むように改造してみてください）

/* 簡易型 地図データ */
typedef struct {
    double x,y;
    char *jname,*ename;
} MAPDATA;

MAPDATA data[] = {
    { 0.00, 0.00, "駅前青葉", "Ekimae-Aoba"},
    { 0.86, 7.55, "七北田入口", "Nanakita-Iriguchi"},
    { 0.62, 6.72, "泉中央駅", "Izumi-Chuoh-Station"},
    /* 省略 */
    { 0.65, -11.90, "植松", "Uematsu"},
    {-1.96, -4.35, "西多賀", "Nishitaga"},
    { 1.66, -4.93, "長町IC", "Nagamachi-IC"},
    { 0.00,  0.00, NULL, NULL},
};

一つのデータは、交差点の位置 (x,y) とその日本語名 jname、ローマ字表記enameからなります。（多少ややこしい理由で、char jname[200]; ではなく *jname という形になっています。これはデータの用意の仕方の都合の関係です。）

また、このデータ形式の特徴は一番最後の「{0,0,NULL,NULL},」という行です。座標の(0,0)は有り得る数値ですが、そのあとのjname,enameのNULLが重要な意味をもってます。これはよく「何もない」ことを意味するために使われるもので、数値としてみると、（普通は）0です。普通に文字列が入っている限り、このNULLに一致することはありません。そのため、ここではデータの終りを示す目的でこのNULLをつかっています。こうすると、データを増やすたびにデータ数を数える必要がないという利点があります。いま使っているmap2.datは先頭行にデータ数の記述が必ず必要です。

一致するものを探す　

一致するものを探す、という場合、一致したかどうかを判断する必要があります。たとえば、今回のデータの場合

などです。もちろん、これらの「どれか一つ」とか、「全部満たす」とかいろいろ条件をつけることも出来ますが、ここでは、一つずつ考えます。

文字列が一致したかどうか、は strcmp(s1,s2); で調べることができます。この関数は文字列(char * ... or char ...[] or "..." )を２つ渡すと、それらが完全に一致した場合に0を返してくれます。そのため、データ群と比較対象の文字列をstrcmpに与え、 0なら一致した、ということができます。この関数は、実際には、文字列を辞書順(アルファベット順、ASCII順)で比較し、どちらが前かで正負の数字を返します。そのため、ソートでも使うことができます。

三つ目の場合は、プログラムは簡単です。ただ、 ==で比較するだけです。ただし、細かく規定された座標を間違いなく入力するという可能性はそれほど高くありません。そのため、たとえば、入力された場所から、ある距離内にある場合に一致したと見なす、という手法を取ることができます。

さて、入力されたローマ字表記の交差点を探すプログラムを見てみましょう。

void search_cross(void) {
    int i;
    char buff[256];
    int f = 0;      /* 見つかったかどうかのフラグ */
    printf("交差点名を入力してください (ローマ字): ");
    scanf("%s", buff);

    for (i = 0; i < crossing_number; i++) { /* データを最後までループ　*/
        if (strcmp(cross[i].ename,buff) == 0) {  /* 一致したら*/
            printf("交差点名 %s(%s)  座標 %.2lf,%.2lf  駅からの距離 %.2lf\n",
            cross[i].jname,cross[i].ename,
            cross[i].pos.x,cross[i].pos.y,
            hypot(cross[i].pos.x, cross[i].pos.y));
            /* hypot は sqrt(x*x+y*y) を計算します */
            f = 1;
        }
    }
    if (f == 0)
        puts("見つかりませんでした");
}

最初に、交差点名をbuffに入れ、ループの中で strcmp() で比較しています。ループの部分は、先週のmap_readでデータ数も教えている部分を使いましょう。

プログラム自体は非常に簡単です。一つ、工夫があるとすれば、fの存在です。一致検索の場合、複数見つかることもあれば、全く見つからないこともあります。全く見つからなかったことを判定するため、最初に fを0にしておき、見つけたら1を代入します。1は何度代入しても1ですが、一度も代入しなければ0です。このことを使って見つからなかったことを知らせることができます。（putsは、改行(\n)込で文字列をただ表示するものです。）

部分的に一致するものを探す

部分的に一致したものを探す、という場合、一致したかどうかを判断する部分さえ、そのように変えれば済みます。たとえば、部分毎に判断式をつくり、それを「||」で結合すれば、そのどこか一部分が一致する、という条件ができます。

ただ、文字列が部分的に一致、というのは便利な方法があるので、特別扱いしておきます。

void search_cross_aprox(void) {
    int i;
    char buff[256];
    int f=0;  /* 見つかったかどうかのフラグ */
    printf("交差点名を入力してください (ローマ字): ");
    scanf("%s", buff);

    for (i = 0; i < crossing_number; i++) {  /* データを最後までループ */
        if (strstr(cross[i].ename, buff) != NULL) { /* 含んでいたら */
            printf("交差点名 %s(%s)  座標 %.2lf,%.2lf  駅からの距離 %.2lf\n",
            cross[i].jname,cross[i].ename,
            cross[i].pos.x,cross[i].posy,
            hypot(cross[i].pos.x, cross[i].pos.y));
            f = 1;
        }
    }
    if (f == 0)
        puts("見つかりませんでした");
}

これは上の例と1行だけ異なります。先ほど一致の確認に strcmpを使いましたが、ここではstrstr(s1,s2)を使いました。このstrstr(s1,s2)は s1 に s2 が含まれている場合、 s1 の中で s2 が見つかった場所(ポインタ)を返す、という関数です。見つからない場合は NULL を返します。そのため、「strstr(s1,s2) != NULL」という条件は「s1にs2を含む場合」という意味になります。これで「入力した文字列を含む交差点名」を探すことができます。 この関数を使用する場合にはstring.hをincludeしてください。

最も近いものを探す

最も近いものを探す、といった条件は、その近さを表す評価数値が最小になるものを探す、といいかえることが出来ます。逆に、評価数値さえ算出できれば、「最も◯◯」を探すことが出来るわけです。

この考え方をプログラムにすると、以下のようになります。

/* 最短距離検索 */
void search_min_distance(int crossing_number) {
    int i;
    int minindex = 0;  /* 暫定トップの位置 */
    double dist, mdist;
    double x, y;

    printf("検索地点座標を入力してください(%%lf %%lf 形式): ");
    scanf("%lf %lf", &x, &y);

    for (i = 0; i < crossing_number; i++) {  /* データ最後までループ */
        /* 現在の暫定トップの評価数値 */
        mdist = hypot(cross[minindex].pos.x-x, cross[minindex].pos.y-y);
        /* 挑戦者の評価数値 */
        dist = hypot(cross[i].pos.x-x, cross[i].pos.y-y);

        if (dist < mdist) /* 挑戦者の方が近い */
            minindex = i;
    }

    printf("座標( %.2lf, %.2lf )の地点から最も近い交差点 (距離 %.2lf):\n",
           x, y, hypot(cross[minindex].pos.x-x, cross[minindex].pos.y-y));
    printf("交差点名 %s(%s)  座標 %.2lf,%.2lf  駅からの距離 %.2lf\n",
            cross[minindex].jname, cross[minindex].ename,
            cross[minindex].pos.x, cross[minindex].pos.y,
            hypot(cross[minindex].pos.x, cross[minindex].pos.y));
}

このプログラムは「ユーザが入力した座標から最も近い交差点を探す」プログラムです。入力座標から、各データの交差点までの距離を出すために、「hypot(data[i].x-x,data[i].y-y)」という関数を使っています。hypot(a,b)はsqrt(a*a+b*b)を演算するもので、こういうときに便利なので覚えておくと良いでしょう。

さて、このプログラムは汎用性を重視したので、多少効率がわるいです。先ほどのstrcmpなどを使って相対評価しか出来ないのであれば、近さの比較のif文に直接書く必要もあります。しかし、距離という数値で絶対評価できるので、「暫定トップの評価値」の演算を減らすことが簡単にできます。たとえば、「minindex=i;」と一緒に計算するなど。そのときは、一番最初に適当な初期値を設定しなければなりません（最初から０やマイナスだと、ifが成立しなくなります）。最小値を求めるので、たとえば 1e100 など、「すごく大きな値」にしておくとよいでしょう。

逆に、「大きな値」を選ぶ場合は、評価値にマイナスをつけたり、ifの不等号の向きを逆にしたりすればいいわけです。また、この例では、「評価値の同じデータが２個ある場合」には、先に最小値を出した方が優先になります。

検索演習

キーボードから交差点名のローマ字名を入力して、map2.datに格納されている

を表示するプログラムを作成してください。ファイル map2.dat はここに、先週やってもらった readfile.c の改訂版はここにありますので、参考にする人はして下さい。

このプログラムは先の二つと違って、該当する交差点が複数出てくる可能性があります。これがうまく表示できるように考えてください。該当した交差点の数を入れる変数、該当したcross[i]のiを格納しておく変数、それらを全て表示させる、ループを利用した繰り返し表示など。

以下にプログラムのひな形を用意しています。こちらからもダウンロードできます。

/* ex8-1.c:
 * 交差点検索（ローマ字で交差点名をキーボードから入力して画面に交差点情報を出力するプログラム
 */
#include <stdio.h>
#include <math.h>
#include <string.h>

#define CROSSING_SIZE 100     /* 交差点数=100 */
#define MAX_NAME_SIZE 50      /* 最大文字数50文字(半角) */

typedef struct {
  double x, y;                /* 位置 x, y */
} Position;                   /* 位置を表す構造体 */

typedef struct {
  int id;                     /* 交差点番号 */
  Position pos;               /* 位置を表す構造体 */
  double wait;                /* 平均待ち時間 */
  char jname[MAX_NAME_SIZE];  /* 日本語交差点名 */    /* 名前が二つに*/
  char ename[MAX_NAME_SIZE];  /* ローマ字交差点名 */  /* なってます */
  int points;                 /* 交差道路数 */
  int next[5];                /* 隣接する交差点番号 */
} Crossing;

Crossing cross[CROSSING_SIZE];

int map_read(char *filename) {

/* すでに用意してありますので
     * int map_read(char *filename) のみ
     * readfile.c からコピーして下さい
     */

}

void print_cross(int i) {  /* i 番目の交差点 の表示関数 好きに改造してください*/
    int j;
    printf("交差点番号:%2d, 座標(%5.2lf,%5.2lf), 名前: %s ( %s ),",
           cross[i].id, cross[i].pos.x, cross[i].pos.y,
           cross[i].jname,cross[i].ename);

    printf("\n               待ち時間:%5.1lf, 隣接交差点 :%d個 ( ",
           cross[i].wait, cross[i].points);

    /* 交差道路数だけ繰り返し */
    for (j = 0; j < cross[i].points; j++)
        printf("%d ", cross[i].next[j]);

    printf(")\n\n");
}

/* この辺りから入力していません */

int search_cross(int num) {  /* 完全一致サーチのプログラムをこの行以降に入力して下さい */
    int i;
    int f = -1;
    char input[200];
    printf("交差点名を入力してください(ローマ字): ");
    scanf("%s", input);

    puts("");
    for (i = 0; i < num; i++) {

        /* i番目の交差点名(ename)と入力したinput が一致したら: 考えてください */

        {
            print_cross(i);  /* 表示 */
            f = i;             /* 見つけた番号保持 */
        }
    }
    if (f < 0)
        printf("%s はみつかりませんでした\n", input);

    return f;  /* 見つかっていたら、それを、なければ -1 を返します */
}

int main(void) {
    int crossing_number;  /* 交差点数 */

    /* ファイルの読み込み */
    crossing_number = map_read("map2.dat");

    printf("loaded %d crossings\n", crossing_number);

    search_cross(crossing_number);
    return 0;
}

読み物: 検索を高速化するには

その１：並べておく

予め、評価数値があるようなものは、その数値で順番にならべておく、という方法があります。並べる手間は係りますが、おおよその場所の見当をつけられるため*、すばやく見つかります。同じデータ群から同じ方法でたくさん検索するときに向いてます。

病院のカルテなんかはこうなってますよね。あとは事務室の成績表の引き出しとか(だれもかき回してなければ)。

(*) たとえば、先頭を調べて、最後を調べて、真ん中を調べると、目的のデータが前半にあるか、後半にあるか分かります。これを繰り返すと、目的のデータが見つかります。

その２：ハッシュ

相対評価をしないといけない場合には、どうしようもないのですが、数値化可能で、完全に一致したものを検索する場合には、ハッシュという手法がつかえます。これは、各データ毎にハッシュ値という値を計算しておき、それでデータをグループ分けしておくわけです。上の例では、たとえば、ローマ字読みの先頭の一文字のアルファベット（A-Z）でグループ分けします。実際に検索する場合には、検索対象のハッシュ値を算出して（この例だと先頭の一文字をとる）、おなじハッシュ値のグループを選び、そこで探します。そうすると、検索時間が減らせるわけです。

ここで重要なのは、いかに均等にグループ分け出来るかです。偏りが大きいと、大きなところで時間をくいます。そのためには、本当は「先頭の文字」なんてやってはいけませんし、文字列の長さそのものもいけません。文字列の長さやすべての文字を数値にして加算したりして、出来た数値を何らかの素数で割って余りをえる、などします。もちろん、このハッシュの最大数（グループ数）をどんどん大きくすると、最終的には、一発で引き当てるようになります。ただ、それだと、何もないグループもかなりの数になり、記憶領域を無駄に使うので、どこで手を打つかは難しいところです。

読み物: もうひとつの main 関数と return の値

これまで、main 関数は int main(void) と教えてきました。なぜこう書くか、というとこれがＣ言語の約束だからです。教科書にはvoid main(void)とありますが、非常に昔の話です。

実はこの他にも main 関数には使える形式があります。それが今回のサンプルで使用した int main(int argc, char **argv) という形式です。

として、あるプログラムを起動した場合、argc には 3が、argv[0], argv[1], argv[2]にはそれぞれ、 "./program", "abcdefg", "1234" が入ります。つまり、argc にはプログラム名を含めた個数が、argv[0] - [argc-1] には、その後ろにスペースで区切って入力した文字列が入ります。cc なども、これをみてコンパイルすべきファイル名を知るなどしているわけです。

使用上の注意点としては、argv は [0]から[argc-1]までしかありませんので、必ず argc を確認してください。そうでないと Segmentation fault がでたりします。また、例え数値を与えても、「数値の文字列」にしかならず、int などには直接代入できません(すると得たいの知れない数字になる)。ので、整数に直すときは atoi(argv[i]) と atoi()をつかってください。また、実数に直すときはatof()というものがあります。

次に、「普通の関数の return は呼出元にもどるが、main の return 0; はどこに行くのか？」という疑問です。何人かから質問されましたので、ここで紹介しておきます。この main で return された値は、プログラムの呼出元に帰ります。普通にターミナル (の上のtcsh)でプログラムを実行した場合は、「echo $status」というコマンドで知ることができます。この数字は、プログラムの終了状態などをしらせることで、手順ファイル(シェルスクリプト)にしたがってコマンドを連続して実行する場合、次に実行すべきコマンドを切替たり、続行を停止したりするなどの使い道があります。

これらを使うと、便利なこと*もあるので、興味がある人は覚えておくとよいでしょう。

#include <stdio.h>

int main(int argc, char **argv) {
    int i;
    for (i = 0; i < argc; i++)
        printf("argv[%d]= '%s' \n", i, argv[i]);
    return argc;   /* argc を return */
}

$ cc -o argtest argtest.c
$ ./argtest abcdef 12345
argv[0]= './argtest'
argv[1]= 'abcdef'
argv[2]= '12345'
$ echo $status
3

(*) たとえば、処理内容を切替たり、検索対象を scanf() で取るのではなく、argv をつかうなど。

サーチ(search)：検索

前提プログラム作成

一致するものを探す

部分的に一致するものを探す

最も近いものを探す

検索演習

読み物: 検索を高速化するには

その１：並べておく

その２：ハッシュ

読み物: もうひとつの main 関数 と return の値

一致するものを探す　

読み物: もうひとつの main 関数と return の値