高速文字列マッチング1:毛片を見るアルゴリズム(KMP)

前言
敏感なキーワードを迅速にマッチングするサービスが必要であるため、効率的で、正確で、低エネルギー消費のキーワードマッチングサービスを提供するために、私は長い探求を行った.ここではプロセスをシリーズブログに記録して、参考にしてください.
最初は、クイック敏感語マッチングを受け取った時に、KMPを翻訳して「毛片を見る」というアルゴリズムを思いつきました.大学の時から習っていたので.その効率は非常に高いそうです.元の文字列マッチング効率O(n*m)をO(n+m)に短縮し、✖️になる➕,大変ですね.
KMPアルゴリズムを振り返るたびに、自分がシロであることに気づいたり、振り返るたびに、前回の振り返りで書いたまとめが間違っていることに気づいたりします.そこで、高速文字列マッチングを学び、再びKMPを温めるために、KMPアルゴリズムを使って試してみることにしました.あとで面接でKMPを完全に書けるようになったらすごいんじゃないですか?
孔子が言った「温故知新」は本当に理にかなっている.今回の回顧を経て、私はそのために新しいブログを書く時だと思った.今回の理解は間違いなく正しいからだ.
KMPが速いのは何のためですか? の共通接尾辞の特性を利用してマッチング速度を速めたからだが、敏感なキーワードの共通接尾辞が等しいことは考えてみれば少ないだろう.では、KMPを使う必要はありますか?
もちろん必要ですが、技の多さは身を押さず、アルゴリズムを身につけるのに間違いないことを理解し、KMPとC#のString.Contains()の効率を比較して、自分の視野を広げることができます.
KMP
以前KMPを勉强していた时、私もネット上の多くのブログを见て、このアルゴリズムについて说明するブログはとても多くて、しかも说明するのはすべてとても详しいです.どうして私は一度見たことがあるたびに、一度忘れてしまいますか.だから今回の温故、私は完全に紙の上で絵を描いて、自分で理解しました.結局、自分の考えは忘れにくいが、他人の考えはいつも忘れやすい.そして、アルゴリズムを理解するには、自分に合った角度を見つけなければなりません.
だから私はKMPアルゴリズムの角度を理解して、文字列の接頭辞と接尾辞で、私の頭の中で、接頭辞と接尾辞でKMPを理解するのは簡単です.
共通の接尾辞の長さ
接頭辞と接尾辞は、文字列の前半と後半に分かりやすい.例えば文字列a b c x y a b cの接頭辞にはa a b a b cなど、接尾辞にはc b c a b cなど.
では、 とは、接頭辞と接尾辞が等しいことを意味します.上記の例では、共通の接尾辞はa b cであり、長さは3である.共通の接尾辞と文字列が違うので注意してくださいね.a b c x y c b aの共通プリアンブルは、aではなくa b cにすぎません.
元の文字列の一致
共通の前接尾辞を理解した後.しばらく横に置いて、元の文字列が一致していることを理解してみましょう.
まず、一致する文字列を と呼び、一致する文字列を と呼びます.例えば、a b c x y a b c x y aにa b c x y a b c yが存在するかどうかを一致させます.
するとテキスト文字列Sは、a b c x y a b c x y a一致文字列Pは、a b c x y a b c yである
肉眼的に見ると、マッチング文字列の最後のアルファベットyが一致しないため、マッチングは失敗したに違いない.
では、元の文字列マッチング過程は暴力の一人一人の割合です.まず、1位から比較します.

   0   1   2   3   4   5   6   7   8   9  10
   ↓
S  a   b   c   x   y   a   b   c   x   y   a
P  a   b   c   x   y   a   b   c   y
   ↑

1位、2位と比較して8位まで

   0   1   2   3   4   5   6   7   8   9  10
                                   ↓
S  a   b   c   x   y   a   b   c   x   y   a
P  a   b   c   x   y   a   b   c   y
                                   ↑

違いが見つかり、マッチングに失敗したため、マッチング文字列を右に1つ移動しました.

   0   1   2   3   4   5   6   7   8   9  10
       ↓
S  a   b   c   x   y   a   b   c   x   y   a
P      a   b   c   x   y   a   b   c   y
       ↑

テキスト文字列がすべて遍歴されるまで、上記の手順を繰り返します.この方法の効率が最も悪いのはO(n*m)で,毎回最後の文字が一致しない場合である.
高速移動
もっと速い方法はありませんか?あるに違いない.しかし、焦らないで、私たちはやはり上の手順に従って、歩き続けます.
一致文字列が右に移動して5位に移動すると、やっと頭文字が一致していることがわかりました.次のように

   0   1   2   3   4   5   6   7   8   9  10
                       ↓
S  a   b   c   x   y   a   b   c   x   y   a
P                      a   b   c   x   y   a   b   c   y
                       ↑

実際には、テキスト文字列の1位以降のb c x yは、一致文字列の頭文字とは異なるので、直接スキップできれば良いことがわかりました.
では、直接スキップできる根拠はありますか?もちろん、以前の共通の接尾辞が機能していました.a b c x y a b c yのサブストリングa b c x y a b cの共通接尾辞はa b cであり、
最初は8位が一致していないことに気づきました

    0   1   2   3   4   5   6   7   8   9  10
                                    ↓
 S  a   b   c   x   y   a   b   c   x   y  a
 P  a   b   c   x   y   a   b   c   y
                                    ↑

一致する文字列を直接右に5番目に移動し、8番目から判断を続けることができます.

   0   1    2   3   4   5   6   7   8   9  10
                        |           ↓
S  a   b   c    x   y   a   b   c   x   y   a
P                       a   b   c   x   y   a   b   c   y
                        |           ↑

どうしてですか.a b c=a b cでしょう.0-7ビットの文字列には、共通の接尾辞a b cがあるので、一致する文字列を共通の接尾辞の開始位置、つまり5番目に直接移動することができます.
前は見に行かなくてもいいので、きっと合わない!、5位でマッチングを開始してこそ、成功する可能性があります.
移動の結果、最初は文字列の接頭辞部分を接尾辞部分と位置合わせに移動します.これはマッチングに成功する前提です.マッチング文字列のサブストリングが自分の接尾辞を探していて、それに寄りかかってマッチングしていることを想像することができます.
次のように

                          
a b c x y a b c
          a b c  x y a b c
            

このように移動すると、最初からやり直さなくても8位から下にマッチングすることができます.したがって、この方法では、テキスト文字列は一度だけ巡回され、後退しません.
これが私が理解しているKMPアルゴリズムの核心思想です.**KMPは文字列の接頭辞と接尾辞で文章を作る**
具体的なプロセス
KMPアルゴリズムの物理的コア思想は理解され,次はコード実現である.一致する文字列の共通接尾辞情報と、そのサブ列の共通接尾辞情報を保存するとしますか?マッチングが成功しないと、マッチング文字列のサブストリングが何ビット移動し、接尾辞にぴったり合うかどうかをどのように判断しますか?
最初の質問は、1つの配列でメンテナンスできます.これはよく知られているNext です.
Next配列,Next[i]は0からiまでの子串の最長の共通前接尾辞の長さを表しており,栗を挙げるとよく理解できる.例えば、次の文字列s:

a   b   a   b   c   a   b

Next [ 0 ] => aは、文字が1文字しかなく、接頭辞と接尾辞の概念はここでは存在しないので、Next [ 0 ] = 0Next [ 1 ] => a b、接頭辞aは接尾辞bに等しくないので、0Next[ 1 ] = 0でもあるNext [ 2 ] => a b a、接頭辞aは接尾辞bに等しいが、接頭辞a bは接尾辞b aに等しくないので、Next[ 2 ] = 1Next [ 3 ] => a b a b、接頭辞a bは接尾辞a bに等しいので、Next[ 3 ] = 3上の栗を通ると、ネクスト配列が何をしているのかわかるでしょう.前の一致文字列Pに戻る:

P  a b c x y a b c y

そのNext配列は何ですか?文字列アルゴリズムを見ているとすぐに得られます

Next[9]= { 0 , 0 , 0 , 0 , 0 , 1 , 2 , 3, 0 }

8番目、つまり最後の文字に一致すると、一致しないことがわかります.

    0   1   2   3   4   5   6   7   8   9  10
                                    ↓
S   a   b   c   x   y   a   b   c   x   y   a
P   a   b   c   x   y   a   b   c   y
                                    ↑

一致する文字列を直接右に5ビット移動することができます

   0   1    2   3   4   5   6   7   8   9  10
                        |           ↓
S  a   b   c    x   y   a   b   c   x   y   a
P                       a   b   c   x   y   a   b   c   y
                        |           ↑
                        0   1   2   3   4   5   6   7   8

この過程は実は、S[8]!=P[8]の場合,S[8]は直接P[3]と比較し続け,Next[7]の値が3であることによる.
サブストリングP[0-7]の最大共通接尾辞長は3であるため、S[8]は、共通接頭辞の次の文字P[Next[7](Next[i]と同様に共通接頭辞の次の文字の下付き文字であることがよく理解できる)と比較すれば、すなわちP[3]であり、これは、P[0],P[1],P[2]およびS[5],S[6],S[7]が共通接尾辞であるため、同じだ!
以上が,古典的なKMPアルゴリズムの全過程である.
コード実装
まずNext[]配列を要求しますが、どうやって求めますか?簡単です.ダイナミックな計画の思想を利用します.Next[i]の値は、最も長い共通接尾辞を持つ文字列に+1を加えるか、サブストリングが1つも一致していないか、自分で別のかまどを作ります.
Next[i]の値には2つのケースがあります.

Next[i-1]は0ではなく、サブストリングに共通の接尾辞があることを示すので、文字列の共通接頭辞の次の文字列P[Next[i-1]]に行き、P[i]==P[Next[i-1]]であれば、共通の接尾辞の長さは+1、すなわちNext[i]=Next[i-1]+1となる.もし等しくなければ?それではP[Next[i-1]]のNext値を探して、上の過程を繰り返して、少し再帰的な意味があります.実はこの過程は文字列の中の共通接頭辞を探して、条件に合っている(すなわちP[i]==P[Next[k])があるかどうかを見て、なければ接頭辞の中で接頭辞を探して、見つけるまで、あるいはすでに共通接頭辞を使っていないことに気づいたら、飛び出します.

子串が条件を満たしていないことを発見して、自分を+1させて、そこで自分から始めて、P[i]==P[0]が等しければ、それは1で、等しければ、それは0になるしかありません.

コードは以下のように実現され、理解しても簡単で、いつでも手書きで書くことができ、忘れません.

    void getNext(string str)
    {
        next[0]=0;
        for(int i=1;i

これが私のNext配列に対する理解で、私はこのように理解して、私は覚えていると思います.
もう一つの非常にシンプルなNext配列実装は、私は貼るつもりはありません.私の心を混乱させて、私は私が理解することができて、理解できるコードを使います.
Next配列を求めると、文字列が一致します.簡単ですよ.

int KMP(string content,string str)
    {
        getNext(str);
        
        int i=0,j=0;
        while(i=str.length())
        {
            return i-str.length();
        }
        else
            return -1;
    }

j = next [j-1]は私の上のすべてで、移動の過程で、他のもよく理解しています.
その後、KMPでLeetCodeの問題を通じて、自分が書いたコードが正しいかどうかを検出することができます.https://leetcode.com/problems/implement-strstr/
まとめ
KMPアルゴリズムはここまで紹介されていますが、KMPについてはアップグレードされたバージョンがたくさんあります.
文字列がすばやく一致し、第1弾、毛片を見ます.振り返ってみると、これからも忘れないような気がします.
冒頭でKMPとC#のStringをContainsはPKを行い、次のブログに残します.次のブログでは、文字列のマッチングのパフォーマンスを大きくソートし、マイクロソフトのブラックテクノロジーを見てみましょう.