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 - - - -
パターン比較1 - a b a b b - - -

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

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


KMP法テーブル作成(二回目)

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

パターン元 a b a b b - - - -
パターン比較2 - - a b a b b - -

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

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


KMP法テーブル作成(三回目)

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

パターン元 a b a b b - - - -
パターン比較3 - - - - a b a b b

この結果、5文字目「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
パターン比較1 a b a b b - - - - - - - -
パターン比較2 - - a b a b b - - - - - -
パターン比較3 - - - a b a b b - - - - -
パターン比較4 - - - - - a b a b b - - -
パターン比較5 - - - - - - - a b a b b -

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

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

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

/*!
 * @brief      KMP法テーブルを作成する
 * @param[in]  pattern  検索文字列
 * @return     テーブルのポインタ。失敗したらNULLを返す。
 */
static int *
kmp_table_init(const char *pattern)
{
    int *table = NULL;
    int i, j;                      /* パターンの文字参照点 */
    int ptn_len = strlen(pattern); /* パターンの文字列長 */

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

    /* テーブルの値を設定する */
    table[0] = 0;
    for(i = 1, j = 0; i < ptn_len; i++){
        if(pattern[i] != pattern[j]){
            table[i] = 0;
            j = 0;
        }else{
            table[i] = ++j;
        }   
    }
    table[ptn_len] = '\0';

    for(i = 0; i < ptn_len; i++) printf("[kmp]:table[%d]=%d\n",i, table[i]);
    return(table);
}

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

    /* デバッグ用 */
    printf("-----------------------------------\n");
    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  検索文字列
 * @return     発見位置のポインタを返す。失敗したらNULLを返す。
 */
char *
kmp_search(const char *text, const char *pattern)
{
    int *table = NULL;
    int i = 0;
    int j = 0;

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

    /* 比較処理 */
    while((text[i] != '\0') && (pattern[j] != '\0')){
        print_compare_process(text, pattern, i, j);

        /* 文字の比較 */
        if(text[i] == pattern[j]){
            i++;          /* テキストの位置を1文字進める */
            j++;          /* パターンの位置を1文字進める */
        }else if(j == 0){
            i++;          /* テキストの位置を1文字進める */
        }else{
            j = table[j -1]; /* ずらし表を参照して進める */
        }
    }

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

    if(pattern[j] != '\0') return(NULL);
    return((char *)text + (i - j));
}

int
main(void)
{
    char *text    = "abaababababbb";
    char *pattern = "ababb";

    printf("[text]   :%s\n", text);
    printf("[pattern]:%s\n", pattern);

    if(kmp_search(text, pattern) == NULL){
        printf("[result] : not found\n");
    }else{
        printf("[result] : found\n");
    }
   
    return(EXIT_SUCCESS);
}

実行結果

見やすくするために少し省略しています。

[text]   :abaababababbb
[pattern]:ababb
[kmp]:table[0]=0
[kmp]:table[1]=0
[kmp]:table[2]=1
[kmp]:table[3]=2
[kmp]:table[4]=0
-----------------------------------
[compare]:(text i=0)(pattern j=0)
 text    :abaababababbb
 pattern :ababb
         :^
-----------------------------------
[compare]:(text i=3)(pattern j=1)
 text    :abaababababbb
 pattern :  ababb
         :   ^
-----------------------------------
[compare]:(text i=3)(pattern j=0)
 text    :abaababababbb
 pattern :   ababb
         :   ^
-----------------------------------
[compare]:(text i=7)(pattern j=2)
 text    :abaababababbb
 pattern :     ababb
         :         ^
-----------------------------------
[compare]:(text i=9)(pattern j=2)
 text    :abaababababbb
 pattern :       ababb
         :           ^
[result] : found

関連ページ



スポンサード リンク