第37章 速読法

 今回からは文字列照合について話したいと思います。話が話なので長くなってしまうかもしれませんが、ご勘弁を。


 それでは、今回の要点です。


 では、いってみましょう。


 今回は文字列照合についてのお話です。文字列照合というのは、ある文字列と目的の文字列を照らし合わせて、同じものを探すことです。簡単にいえば、文字列の検索です。メモ帳、ブラウザ、果てはVC++まで、文書を扱うプログラムには欠かせないものですね。

 最初ということで、今回は特別なアルゴリズムを使わずに文字列照合を行っていきたいと思います。


 では、文字列照合を行う方法について考えてみましょう。先ずは、検索を行う文章を用意します。

Match.txt
tomatu
tomati
tomata
tomate
tomato

 tomato の最後の母音を変えていっているだけです。後々のアルゴリズムの説明に便利なようにちょいと特徴づけています。この文字列を src と呼ぶことにします。

 では、この中から "ato" を探してみます。この文字列は pat と呼ぶことにします。

 先ず、src の先頭に pat がないかを確かめます。2つの文字列を並べてみましょう。

src : tomatu[\n]tomati[\n]tomata[\n]tomate[\n]tomato
pat : ato

 src の先頭に pat があるかどうかは、両者の先頭から順に比べていけばいいですね。先ず、src の先頭は t で、pat の先頭は a なので、先頭からして違うことが分かります。

 先頭の1つを比較しただけで src の先頭に pat がないことが分かります。ということで、次は src の2番目に pat がないかを確かめます。

src : tomatu[\n]tomati[\n]tomata[\n]tomate[\n]tomato
pat :  ato

 これもだめです。そして、これを続けていきます。

src : tomatu[\n]tomati[\n]tomata[\n]tomate[\n]tomato
pat :    ato

 src の4番目は pat と "at" の2文字が同じになりました。しかし、3文字目が異なるのでまだ先に進みます。

src : tomatu[\n]tomati[\n]tomata[\n]tomate[\n]tomato
pat :                          a to

 今度は "a" の1文字が同じになりました。しかし、以降が異なるので、まだ先に進みます。

src : tomatu[\n]tomati[\n]tomata[\n]tomate[\n]tomato
pat :                                            ato

 ここにきて、ようやく "ato" の3文字の等しくなるところが現れました。

 このようにすれば、簡単ですが文字列照合ができるわけです。pat が現れるところをしらみつぶしに探しているだけですね。


 では、これをプログラムにしてみましょう。後のプログラムのために、再利用可能な形にしておきます。

プログラム1
// Match2.h
#ifndef __MATCH2_H__010414_2259_57951860__INCLUDED__
#define __MATCH2_H__010414_2259_57951860__INCLUDED__

// 文字列照合関数の型
// 関数ポインタ(第9章参照)ですね
typedef int (*FPMATCH)(const char* src, int nBufSize,
                       int nFirst, const char* pat);

// 「見つかりませんでした」を表す値
const int MATCH_NOTFOUND = -1;

void Match(const char* pszFile, FPMATCH fpMatch);

#endif // #ifndef __MATCH2_H__010414_2259_57951860__INCLUDED__
プログラム2
// Match2.cpp
#include <iostream.h>
#include <stdio.h>
#include <string.h>
#include "Match2.h"

static int Input(const char* src, int nSize, FPMATCH fpMatch);

// ファイルの検索を行います
// 検索するファイルは pszFile に、
// 文字列照合関数は fpMatch に指定します
void Match(const char* pszFile, FPMATCH fpMatch)
{
    FILE* file = NULL;  // ファイル
    char* src  = NULL;  // 検索する文字列(動的)
    int   nSize;        // ファイルサイズ

    // 検索するファイルを開きます
    // テキストモードでファイルを開くと
    // fseek や ftell の動作がややこしくなるので、
    // バイナリモードでファイルを開きます
    file = fopen(pszFile, "rb");
    if(file == NULL)
        goto ON_ERROR;

    // fseek : ファイルポインタを移動する関数です
    // この場合、ファイルの最後に移動します
    fseek(file, 0, SEEK_END);
    // ftell : ファイルポインタを取得する関数です
    // ファイルの最後に移動してファイルポインタを取得するということは
    // ファイルサイズを取得することになります
    nSize = ftell(file);
    // rewind : ファイルの先頭に戻る関数です
    rewind(file);

    // 動的に確保
    src = new char[nSize + 1];
    if(src == NULL)
        goto ON_ERROR;

    // 検索するファイルのデータを読み込みます
    fread(src, 1, nSize, file);
    src[nSize] = 0;  // ヌルターミネータ

    // ファイルを閉じます
    fclose(file);
    file = NULL;

    // 検索を行います
    while(Input(src, nSize, fpMatch));

ON_ERROR:
    if(file != NULL)
        fclose(file);
    if(src != NULL)
        delete [] src;
}

// 検索を行います
// src には検索する文字列を、
// nSize にはその文字列のサイズを、
// fpMatch には文字列照合関数を指定します
static int Input(const char* src, int nSize, FPMATCH fpMatch)
{
    static int  nFound = MATCH_NOTFOUND;  // 見つかった場所
    static char szPrev[1024];  // 前に検索した文字列
    char szMatch[1024];        // 検索される文字列

    cout << "検索する文字列を入力してください > " << flush;
    cin >> szMatch;

    // "end" の場合は終了
    if(strcmp(szMatch, "end") == 0)
        return false;
    // "next" の場合は次を検索
    else if(strcmp(szMatch, "next") == 0)
    {
        // 検索したことがない場合
        if(szPrev[0] == 0)
        {
            cout << "まだ一度も検索していません!" << endl;
            return true;
        }
        // 前に検索に失敗していた場合は先頭から検索されます
        // そのためにも MATCH_NOTFOUND は -1 にしてあります
        nFound = fpMatch(src, nSize, nFound + 1, szPrev);
    }
    // それ以外の場合は先頭から検索
    else
    {
        strcpy(szPrev, szMatch);
        nFound = fpMatch(src, nSize, 0, szPrev);
    }

    // 見つからなかった場合
    if(nFound == MATCH_NOTFOUND)
        cout << "見つかりません" << endl;
    // 見つかった場合
    else
    {
        cout << nFound << " バイト目に発見しました!" << endl;

        // 見つかった場所と、その後16バイトを表示します
        int nLimit = strlen(szPrev) + 16;
        for(int i = 0; i < nLimit; i++)
        {
            char letter = src[nFound + i];
            if(letter == 0)
                break;
            cout << letter;
        }
        cout << endl;
    }

    return true;
}
プログラム3
// Match3.cpp
#include "Match2.h"

static int SimpleMatch(const char* src, int nBufSize,
                       int nFirst, const char* pat);

int main()
{
    Match("Match.txt", SimpleMatch);
    return 0;
}

// 単純な文字列照合関数です
// src には検索対象を、
// nBufSize には src のサイズを、
// nFirst には開始バイト数を、
// pat には検索文字列を指定します
static int SimpleMatch(const char* src, int nBufSize,
                       int nFirst, const char* pat)
{
    // エラーチェック
    if(pat[0] == 0        ||
       src[nBufSize] != 0 ||
       nFirst > nBufSize)
        return MATCH_NOTFOUND;

    // 開始位置をずらします
    src += nFirst;

    // src[0] から順に照合していきます
    for(int i = 0; src[i] != 0; i++)
    {
        // src と pat の照合
        int j;
        for(j = 0; pat[j] != 0; j++)
            if(src[i + j] != pat[j])
                break;
        // 等しかった場合、見つかった場所を返します
        if(pat[j] == 0)
            return i + nFirst;
    }
    // 最後まで見つかりませんでした
    return MATCH_NOTFOUND;
}
実行結果例
検索する文字列を入力してください > ato
31 バイト目に発見しました!
ato
検索する文字列を入力してください > next
見つかりません
検索する文字列を入力してください > tomat
0 バイト目に発見しました!
tomatu
tomati
tomata

検索する文字列を入力してください > next
7 バイト目に発見しました!
tomati
tomata
tomate

検索する文字列を入力してください > tomato
28 バイト目に発見しました!
tomato
検索する文字列を入力してください > end

 文字列照合関数は main のある Match3.cpp にある SimpleMatch です。その他の部分は、ファイルからデータを読んで、検索文字列を入力させて、結果を表示するというだけのものです。その他の部分は本題と関係ないので、コメント以上のことは解説しません。気になる人は、沢山書いたコメントを頼りに各自読み解いていってください。

 では、SimpleMatch を見ていきましょう。

 最初に nBufSize と nFirst の値に不正がないか、簡単なチェックを行っています。これは特にいうことはありません。次に、nFirst だけ src を進めています。検索開始位置をずらしているだけですね。これも特にいうことはありません。

 次が文字列照合の本体です。先ず、i は src 用のループ変数です。src[0], src[1], src[2], ... と、pat と照合する位置を変えていきます。

 次の j のループは、pat と照合するためのループです。src[i] と pat[0] から順に、src[i + 1] と pat[1] 、src[i + 2] と pat[2] 、... と、順に照合していきます。全部同じだった場合はループ終了時に pat[j] が0になっているので、それを検索終了の目印にします。

 実は、文字列照合は strstr という関数でできます(strstr がこの手法を用いている保証はないのですが、おそらくはこの手法だと思います)。strstr は、2つの引数を取ります。1つ目の文字列の中から2つ目の文字列を探し、その位置をポインタで返します見つからなかった場合は NULL を返します。

 ということで、今回の検索法を生で使うことはそうはないと思います。文字列以外のデータになら使うことがあるかもしれませんね。


 では、今回の要点です。


 最後に出てきた strstr が要点になってます。実際はこっちを使ってくださいね、ということです。

 今回の文字列照合をじっと見てみると、いろいろ無駄があることが分かります。その無駄を取り除いていく方法を次回から考えていきたいと思います。それでは。


第36章 魔法の数 | 第38章 速読法2

Last update was done on 2001.4.15

この講座の著作権はロベールが保有しています