6

KMPアルゴリズムを理解しようとしています。それでも、kmp アルゴリズムの背後にある推論を明確に理解することはできませんでした。私のテキストがでbacbababaabcbabあり、パターンがであるとしabababcaます。sub(pattern)の適切な接尾辞と一致するの最長の適切な接頭辞の長さの規則を使用してsub(pattern)、table[].

アババブカ
0 0 1 2 3 4 0 1

ここで、パターンとテーブルを使用してテキストに KMP アルゴリズムを適用し始めました。

上記のテキストのインデックス 4 に到達した後、KMP アルゴリズムに従って、最大 2 文字の長さをスキップして続行することができます を参照length(l)=5;して、 の一致があります。table[l-1]=3;

バクババババブ
----xx|||
アババブカ

ここでは、シフトの背後にあるロジックを理解していません。なぜ私たちはシフトしなければならないのですか？誰かが私の混乱を明確にしてもらえますか?

4

2 に答える 2

5

KMP アルゴリズムの背後にあるロジックを理解するには、まず、この KMP アルゴリズムがブルート フォース アルゴリズムよりも優れていることを理解する必要があります。

Idea

パターンのシフト後、単純なアルゴリズムは、以前に一致したシンボルに関するすべての情報を忘れてしまいました。そのため、テキスト シンボルを異なるパターン シンボルと何度も再比較することが可能です。これにより、最悪の場合の複雑さが Θ(nm) (n: テキストの長さ、m: パターンの長さ) になります。

Knuth、Morris、および Pratt [KMP 77] のアルゴリズムは、以前のシンボル比較によって得られた情報を利用します。パターン シンボルと一致したテキスト シンボルを再比較することはありません。その結果、Knuth-Morris-Pratt アルゴリズムの検索フェーズの複雑さは O(n) になります。

ただし、パターンの構造を分析するには、パターンの前処理が必要です。前処理フェーズの複雑さは O(m) です。m<=n であるため、Knuth-Morris-Pratt アルゴリズムの全体的な複雑さは O(n) です。

テキスト :bacbababaabcbab パターン:abababca

力ずくの方法では、パターンをテキスト上に 1 つずつスライドさせ、一致するかどうかを確認します。一致が見つかった場合は、再び 1 ずつスライドして、後続の一致を確認します。

void search(char *pat, char *txt)
{
    int M = strlen(pat);
    int N = strlen(txt);

    /* A loop to slide pat[] one by one */
    for (int i = 0; i <= N - M; i++)
    {
        int j;

        /* For current index i, check for pattern match */
        for (j = 0; j < M; j++)
        {
            if (txt[i+j] != pat[j])
                break;
        }
        if (j == M)  // if pat[0...M-1] = txt[i, i+1, ...i+M-1]
        {
           printf("Pattern found at index %d \n", i);
        }
    }
}

上記のアルゴリズムの複雑さは O(nm) です。上記のアルゴリズムでは、処理した比較データを使用していません。 

Bacbababaabcbab   //let I be iterating variable over this text

Abababca    //j be iterating variable over pattern

i=0 かつ j=0 の場合、不一致 (text[i+j]!=pat[j]) がある場合、一致するまで i をインクリメントします。i =4 の場合、一致 (text[i+j]==pat[j]) があり、不一致が見つかるまで j をインクリメントします (j= patternlength の場合、パターンが見つかりました)。与えられた例では、j= で不一致が見つかります。 5 i=4 の場合、テキストの idex 4+5=9 で不一致が発生します。一致した部分文字列は ababa , **

  • Why we need to choose longest proper prefix which is also proper suffix :

** 上記から、パターンが部分文字列 ababa で終わる 9 で不一致が発生したことがわかります。ここで、これまでに行った比較を利用したい場合は、i を 1 以上スキップ (インクリメント) することができます。そうすれば、比較の数が減り、時間の複雑さが改善されます。
加工された比較データ「アババ」をどのように活用できるか。注意深く見ると、文字列 ababa のプレフィックスabaはテキストと比較され、一致します。サフィックスabaの場合も同様です。しかし、'a' と 'b' が一致しません</p> 

Bacbababaabcbab
         ||||||            
         ||||| x
        |||| ||
        ababab

しかし、単純なアプローチによれば、i を 5 にインクリメントします。しかし、それを見ると、次の aba の出現が 6 で発生するので、i =6 に設定できることがわかります。したがって、テキスト内のすべての要素を比較する代わりに、パターンを前処理します。適切な接尾辞でもある最長の適切な接頭辞（ボーダーと呼ばれる）を見つけるため。上記の 'ababa' の例では、最長の境界線の長さは 3 (これはabaです) です。したがって、増分: 部分文字列の長さ – 最長の境界線の長さ => 5-3 =2.
比較が aba で失敗した場合、最長の境界線の長さは 1 で j=3 なので、2 ずつインクリメントします。

前処理方法の詳細: http://www-igm.univ-mlv.fr/~lecroq/string/node8.html#SECTION0080 http://www.inf.fh-flensburg.de/lang/algorithmen/pattern /kmpen.htm

于 2014-07-15T08:47:58.040 に答える