C言語アルゴリズム-KMP法

KMP法（Knuth-Morris-Pratt algorithm）

KMP法とは

KMP法とは、D.E.Knuth、J.H.Morris、V.R.Prattの3人共同で発表した文字列検索アルゴリズムです。

パターン照合の再開位置を決定するテーブルを予め作成してから検索を行うことで無駄な比較を軽減するアルゴリズムです。

KMP法の性能

KMP法の計算量はO(n)になります。

テキストとパターンの照合において後戻りは発生しないため、力任せ法（Brute Force Search）よりも理論的には高速なアルゴリズムとなります。

しかしながら、現実的には、テーブルを作成するための前処理が複雑であることや、アルゴリズムが複雑な分だけオーバヘッドが大きくなってしまう問題があります。

短い文字列の場合には、結果的に力任せ法の方が効率が良いケースもあります。

KMP法のアルゴリズム

KMP法は「テーブルの作成」と「テーブルを参照した探索」を行います。

テキスト（探索対象文字列）を「abaababababbb」、パターン（探索文字列）を「ababb」とします。

KMP法のテーブル作成

パターンに含まれる各文字について、照合の再開位置（ずらし幅）を調べてテーブルを作成します。

ここではよく使われる例として、パターン自体の文字列をずらしながら照合することで調べる方法を採用します。

テーブルの作成方法は様々であり、よりよい工夫が求められます。

KMP法テーブル作成（一回目）

パターン自体の文字列をずらしながら照合します。

	文字列
パターン元	a	b	a	b	b	-	-	-	-
パターン比較１	-	a	b	a	b	b	-	-	-

この結果、２文字目「b」で不一致が発生した場合には一文字のみ進めることが分かります。

（１文字目で不一致が発生した場合には必ず一文字のみ進めます。）

KMP法テーブル作成（二回目）

パターン自体をさらにずらします。

	文字列
パターン元	a	b	a	b	b	-	-	-	-
パターン比較２	-	-	a	b	a	b	b	-	-

この結果、３文字目「a」まで一致した後に４文字目で不一致が発生した場合には「２文字進める」ことが分かります。

さらに、４文字目「b」まで一致した後に５文字目で不一致が発生した場合には「３文字進める」ことが分かります。

KMP法テーブル作成（三回目）

パターン自体をさらにずらします。

	文字列
パターン元	a	b	a	b	b	-	-	-	-
パターン比較３	-	-	-	-	a	b	a	b	b

この結果、５文字目「b」で不一致が発生した場合には一文字のみ進めることが分かります。

KMP法テーブル作成（結果）

上記の結果、パターンに含まれる各文字のテーブル値は以下の通りになります。

照合の再開位置は「一文字　＋　テーブル値」となります。

	文字列
パターン元	a	b	a	b	b
値	0	0	1	2	0

※一文字分を加算しておき「1,1,2,3,1」とするテーブルの作成方法もあります。

KMP法の探索過程

テキストとパターンを照合して、不一致が発生した場合にはテーブルを参照して、次回の照合位置を進めていきます。照合位置を一文字以上進めることで、比較回数を減らすことができます。

	文字列
テキスト	a	b	a	a	b	a	b	a	b	a	b	b	b
パターン比較１	a	b	a	b	b	-	-	-	-	-	-	-	-
パターン比較２	-	-	a	b	a	b	b	-	-	-	-	-	-
パターン比較３	-	-	-	a	b	a	b	b	-	-	-	-	-
パターン比較４	-	-	-	-	-	a	b	a	b	b	-	-	-
パターン比較５	-	-	-	-	-	-	-	a	b	a	b	b	-

C言語によるKMP法探索プログラム

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <string.h>

/*!
 * @brief      テーブルを出力する。
 * @param[in]  table      テーブルへのポインタ
 * @param[in]  table_len  テーブル長
 */
static void
print_kmp_table(int *table, int table_len)
{
    int i;
    for(i = 0; i < table_len; i++){
        printf("kmp_table[%d]=%d\n",i, table[i]);
    }
}

/*!
 * @brief      KMP法テーブルを解放する
 * @param[in]  table  テーブルへのポインタ
 */
static void
kmp_table_free(int *table)
{
    if(table != NULL) free(table);
}

/*!
 * @brief      KMP法テーブルを作成する
 * @param[in]  pattern  検索文字列
 * @return     テーブルのポインタ。失敗したらNULLを返す。
 * @note       テーブルの最小値をBUFSIZとします。free()でのSEGV対策です。
 */
static int *
kmp_table_init(const char *pattern)
{
    int *table = NULL;
    int ptn_len = strlen(pattern); /* パターンの文字列長 */
    int ptn_idx = 1;  /* パターンの参照点 */
    int cmp_idx = 0;  /* 比較パターンの参照点 */

    /* Check pattern size */
    if(ptn_len >= BUFSIZ){
        fprintf(stderr, "ERROR: kmp_table_init(): too long pattern.\n");
        return(NULL);
    }

    /* KMPテーブルの領域を確保する */
    table = (int *)malloc(BUFSIZ);
    if(table == NULL){
        fprintf(stderr, "ERROR: kmp_table_init(): %s\n", strerror(errno));
        return(NULL);
    }

    /* テーブルの先頭は 0 にする。 */
    table[0] = 0;

    while(pattern[ptn_idx] != '\0'){
        /* 文字が一致した場合、加算する */
        if(pattern[ptn_idx] == pattern[cmp_idx]){
            cmp_idx++;
            table[ptn_idx] = cmp_idx;
            ptn_idx++;
        }
        /* 先頭位置から文字が違う場合、tableに 0 をセットして次に進む */
        else if(cmp_idx == 0){
            table[ptn_idx] = 0;
            ptn_idx++;
        }
        /* 途中まで同じだった場合、途中から比較できる点があるか確かめる */
        else{
            cmp_idx = table[cmp_idx - 1];
        }
    }
    table[ptn_len] = '\0';

    return(table);
}

/*!
 * @brief   照合処理の位置を出力する
 */
static void
print_compare_process(const char *text, const char *pattern, int i, int j, int round)
{
    int cnt = 0;

    /* デバッグ用 */
    printf("-----------------------------------\n");
    printf("Round=%d\n", round);
    printf("[compare]:(text i=%d)(pattern j=%d)\n", i, j);
    printf(" text    :%s\n", text);
    printf(" pattern :");
    for(cnt = 0;cnt < (i - j); cnt++) printf(" ");
    printf("%s\n", pattern);
    printf("         :");
    for(cnt = 0;cnt < i; cnt++) printf(" ");
    printf("^\n");
}

/*!
 * @brief      文字列を探索する
 * @param[in]  text     検索対象文字列
 * @param[in]  pattern  検索文字列
 * @param[in]  table    テーブル
 * @return     発見位置のポインタを返す。失敗したらNULLを返す。
 */
static char *
search_by_table(const char *text, const char *pattern, const int *table)
{
    int round = 0;
    int text_idx = 0;
    int ptn_idx = 0;
    int text_len = strlen(text);
    int ptn_len = strlen(pattern);

    /* テキストの末尾まで確認していく */
    for(text_idx = 0; text_idx < text_len; text_idx++){
        /* 残りテキストがパターンより短ければ中断する */
        if((text_len - text_idx) < (ptn_len - ptn_idx)) break;

        /* デバッグ出力 */
        print_compare_process(text, pattern, text_idx, ptn_idx, ++round);

        /* テーブルを参照して、次のパターン位置を取得する */
        while((ptn_idx > 0) && (text[text_idx] != pattern[ptn_idx])){
            ptn_idx = table[ptn_idx - 1];
        }

        /* 文字が一致していればテキストとパターンを進める */
        if(text[text_idx] == pattern[ptn_idx]){
            ptn_idx++;
            if(ptn_idx == ptn_len){
                break;
            }
        }
    }

    /* ポインターが末尾に位置していたら見つからなかったことになる*/
    if(pattern[ptn_idx] != '\0') return(NULL);
    return((char *)text + (text_idx - ptn_idx + 1));
}

/*!
 * @brief      文字列を探索する
 * @param[in]  text     検索対象文字列
 * @param[in]  pattern  検索文字列
 * @return     成功時は0を返し、失敗時には-1を返す。
 */
int
kmp_search(const char *text, const char *pattern)
{
    int *table = NULL;
    char *found_point = NULL;

    /* ずらし表を作成する */
    table = kmp_table_init(pattern);
    if(table == NULL) return(-1);

    /* デバッグ出力 */
    print_kmp_table(table, strlen(pattern));

    /* テーブルを用いて検索を行う */
    found_point = search_by_table(text, pattern, table);

    /* ずらし表を解放する */
    kmp_table_free(table);

    if(found_point == NULL) return(-1);
    return(0);
}

/*!
 * @brief      入力プロンプトを表示する。
 * @param[in]  msg    表示メッセージ
 * @param[out] input  入力文字列格納先
 * @return     成功時は0を返し、失敗時には-1を返す。
 */
static int
prompt(char *msg, char *input)
{
    int length = 0;

    fprintf(stdout,"%s", msg);
    if(fgets(input, BUFSIZ, stdin) == NULL){
        return(-1);
    }

    /* 未入力をエラーとする */
    if(input[0] == '\n'){
        return(-1);
    }

    /* 改行コードを削除する */
    length = strlen(input);
    if(input[length - 1] == '\n'){
        input[--length] = '\0';
    }

    return(0);
}

int
main(void)
{
    int rc = 0;
    char text[BUFSIZ] = "\0";
    char pattern[BUFSIZ] = "\0";

    if(prompt("Input text    : ", text) != 0){
        fprintf(stderr, "ERROR: Invalid text\n");
        return(EXIT_FAILURE);
    }

    if(prompt("Input pattern : ", pattern) != 0){
        fprintf(stderr, "ERROR: Invalid pattern\n");
        return(EXIT_FAILURE);
    }

    rc = kmp_search(text, pattern);
    if(rc == 0){
        printf("[result] : found!!\n");
    }else{
        printf("[result] : not found\n");
    }

    return(EXIT_SUCCESS);
}

実行結果

テキスト「abaababababbb」とパターン「ababb」を比較しますと下記の通りになります。

Input text    : abaababababbb
Input pattern : ababb
kmp_table[0]=0
kmp_table[1]=0
kmp_table[2]=1
kmp_table[3]=2
kmp_table[4]=0
-----------------------------------
Round=1
[compare]:(text i=0)(pattern j=0)
 text    :abaababababbb
 pattern :ababb
         :^
-----------------------------------
Round=2
[compare]:(text i=1)(pattern j=1)
 text    :abaababababbb
 pattern :ababb
         : ^
-----------------------------------
Round=3
[compare]:(text i=2)(pattern j=2)
 text    :abaababababbb
 pattern :ababb
         :  ^
-----------------------------------
Round=4
[compare]:(text i=3)(pattern j=3)
 text    :abaababababbb
 pattern :ababb
         :   ^
-----------------------------------
Round=5
[compare]:(text i=4)(pattern j=1)
 text    :abaababababbb
 pattern :   ababb
         :    ^
-----------------------------------
Round=6
[compare]:(text i=5)(pattern j=2)
 text    :abaababababbb
 pattern :   ababb
         :     ^
-----------------------------------
Round=7
[compare]:(text i=6)(pattern j=3)
 text    :abaababababbb
 pattern :   ababb
         :      ^
-----------------------------------
Round=8
[compare]:(text i=7)(pattern j=4)
 text    :abaababababbb
 pattern :   ababb
         :       ^
-----------------------------------
Round=9
[compare]:(text i=8)(pattern j=3)
 text    :abaababababbb
 pattern :     ababb
         :        ^
-----------------------------------
Round=10
[compare]:(text i=9)(pattern j=4)
 text    :abaababababbb
 pattern :     ababb
         :         ^
-----------------------------------
Round=11
[compare]:(text i=10)(pattern j=3)
 text    :abaababababbb
 pattern :       ababb
         :          ^
-----------------------------------
Round=12
[compare]:(text i=11)(pattern j=4)
 text    :abaababababbb
 pattern :       ababb
         :           ^
[result] : found!!

テキスト「abaabaaab」とパターン「abaaab」を比較しますと下記の通りになります。

Input text    : abaabaaab
Input pattern : abaaab
kmp_table[0]=0
kmp_table[1]=0
kmp_table[2]=1
kmp_table[3]=1
kmp_table[4]=1
kmp_table[5]=2
-----------------------------------
Round=1
[compare]:(text i=0)(pattern j=0)
 text    :abaabaaab
 pattern :abaaab
         :^
-----------------------------------
Round=2
[compare]:(text i=1)(pattern j=1)
 text    :abaabaaab
 pattern :abaaab
         : ^
-----------------------------------
Round=3
[compare]:(text i=2)(pattern j=2)
 text    :abaabaaab
 pattern :abaaab
         :  ^
-----------------------------------
Round=4
[compare]:(text i=3)(pattern j=3)
 text    :abaabaaab
 pattern :abaaab
         :   ^
-----------------------------------
Round=5
[compare]:(text i=4)(pattern j=4)
 text    :abaabaaab
 pattern :abaaab
         :    ^
-----------------------------------
Round=6
[compare]:(text i=5)(pattern j=2)
 text    :abaabaaab
 pattern :   abaaab
         :     ^
-----------------------------------
Round=7
[compare]:(text i=6)(pattern j=3)
 text    :abaabaaab
 pattern :   abaaab
         :      ^
-----------------------------------
Round=8
[compare]:(text i=7)(pattern j=4)
 text    :abaabaaab
 pattern :   abaaab
         :       ^
-----------------------------------
Round=9
[compare]:(text i=8)(pattern j=5)
 text    :abaabaaab
 pattern :   abaaab
         :        ^
[result] : found!!

関連ページ

• C言語
• C言語アルゴリズム-スタック
• C言語アルゴリズム-待ち行列(キュー)
• C言語アルゴリズム-連結リスト
• C言語アルゴリズム-線形探索法
• C言語アルゴリズム-二分探索法
• C言語アルゴリズム-力まかせ探索
• C言語アルゴリズム-KMP法
• C言語アルゴリズム-BM法
• C言語アルゴリズム-ハッシュチェイン法
• C言語アルゴリズム-オープンアドレス法
• C言語アルゴリズム-二分探索木