トップC-Tips > 文字列探索

文字列探索

1.strstr関数による文字列探索

いたるところで、文字列の探索が必要となる。 例えば、Windowsプログラムで使用するライブラリ関数は "msvcrt.dll", "kernel32.dll", "user32.dll", "gdi32.dll" などのDLL関数に 含まれている。 コンパイラを開発する場合、 ある関数がどのdllファイルに所属するかを調べる必要がある。 上の4DLLに合計約2500関数が含まれている。

文字列の探索は通常はバイナリサーチとかハッシュ関数が用いられるが、 原理的には、strstr関数で、簡単に行える。 下にリンクを張ったプログラムでは、8つの関数名がどのDLL関数に含まれるかを strstr関数で判定している。 100回繰り返したときの探索時間は 0.013秒、 1000回繰り返したときの探索時間は 0.067秒であった。 通常のアプリケーションプログラムで使われるDLL関数は精々数10であるから、 このような簡単なアルゴリズムでも実用上十分な性能と言える。

search01.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <time.h>

char *LIBDIR = "c:/mh/www/mcc/lib";
char *dllname[] = {"msvcrt", "kernel32", "user32", "gdi32"};
                  // 780       760           650       330  計約2500関数
char *szDef[4];
char *func[] = {
        "printf", "exit", "MessageBoxA", "ExitProcess", "CreateWindowExA", 
        "CreatePen", "DeleteDC", "CreateFontA", 
};

int main(int argc, char *argv[]) {
    int n, k, m;
    char path[260], word[32], *p;
    FILE *fp;
    struct _stat st;
    double tmLoad, tmSearch, tmBgn = clock()/1000.0;

    for (n = 0; n < 4; n++) {
        sprintf(path, "%s/%s.def", LIBDIR, dllname[n]);
        if (_stat(path, &st) != 0) {
            fprintf(stderr, "ファイル<%s>が見つかりません\n", path);
            return;
        }
        szDef[n] = calloc(st.st_size + 1, sizeof(char));
        fp = fopen(path, "r");
        fread(szDef[n], sizeof(char), st.st_size, fp);
        fclose(fp);
    }
    tmLoad = clock()/1000.0;
    printf("ファイル読み込み時間=%.4f\n", tmLoad-tmBgn);
for (m = 0; m < 100; m++)
    for (k = 0; k < sizeof(func)/sizeof(char*); k++) {
        sprintf(word, "\n%s\n", func[k]);
        for (n = 0; n < 4; n++) {
            if (strstr(szDef[n], word) != NULL) {
                //printf("%s\t%s\n", func[k], dllname[n]);
                break;
            }
        }
        if (n == 4) {
            //printf("%sはDLL関数ではありません\n", func[k]);
        }
    }
    tmSearch = clock()/1000.0;
    printf("文字列探索時間=%.4f\n", tmSearch-tmLoad);
    for (n = 0; n < 4; n++) {
        if (szDef[n] != NULL) free(szDef[n]);
    }
}

2.bsearch関数による文字列探索

昇順に並んだ配列の並び替えには、 シンプルで効率のよいアルゴリズムとしてバイナリサーチ(binary search)がよく知られている。

C言語の標準ライブラリ関数bsearchの実装はコンパイラ依存で、 必ずしもアルゴリズムはバイナリサーチとは限らない。

search02.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <windows.h>

char *dllname[4] = {"msvcrt", "kernel32", "user32", "gdi32"};
char **expt[4];
int  nExpt[4];

char *func[] = {
        "printf", "exit", "MessageBoxA", "ExitProcess", "CreateWindowExA", 
        "CreatePen", "DeleteDC", "CreateFontA", 
};

void load(int n, void *hModule) {
    int i;
    IMAGE_DOS_HEADER* pDOSHeader = hModule;
    IMAGE_NT_HEADERS* pPEHeader = hModule + pDOSHeader->e_lfanew;
    IMAGE_DATA_DIRECTORY* pDataDirectory = pPEHeader->OptionalHeader.DataDirectory;
    IMAGE_EXPORT_DIRECTORY* pImageExportDir = hModule + pDataDirectory[0].VirtualAddress;
    char** ppszFunctionName = hModule + (int)pImageExportDir->AddressOfNames;
    nExpt[n] = pImageExportDir->NumberOfNames;
    expt[n] = malloc(nExpt[n] * sizeof(char*));
    for (i = 0; i < nExpt[n]; i++) {
        expt[n][i] = strdup((char*)(hModule + (int)ppszFunctionName[i]));
    }
}

int compare(const void *a, const void *b){
    return strcmp(*((char**)a), *((char**)b));
}

int main(int argc, char *argv[]) {
    int n, k;
    double tmLoad, tmSearch, tmBgn = clock()/1000.0;

    for (n = 0; n < 4; n++) {
        HMODULE hModule = (void*)LoadLibrary(dllname[n]);
        if (hModule == 0) continue;
        load(n, (void*)hModule);
        FreeLibrary(hModule);
        qsort(expt[n], nExpt[n], sizeof(char *), compare);
    }
    tmLoad = clock()/1000.0;
    printf("DLL読み込み時間=%.4f\n", tmLoad-tmBgn);

    for (k = 0; k < sizeof(func)/sizeof(char*); k++) {
        for (n = 0; n < 4; n++) {
            char** wd = bsearch(&func[k], expt[n], nExpt[n], sizeof(char *), compare);
            if (wd != NULL) {
                printf("%s\t%s\n", *wd, dllname[n]);
                break;
            }
        }
        if (n == 4) {
            printf("%sはDLL関数ではありません\n", func[k]);
        }
    }
    tmSearch = clock()/1000.0;
    printf("文字列探索時間=%.4f\n", tmSearch-tmLoad);

    for (n = 0; n < 4; n++) {
        if (expt[n] == NULL) continue;
        for (k = 0; k < nExpt[n]; k++)
            if (expt[n][k]) free(expt[n][k]);
        free(expt[n]);
    }
}