アルゴリズムの「文字列マッチングアルゴリズム」

前言
2つの文字列のマッチングといえば,2層のループでマッチングすることを自然に考え,1つの文字列に別の文字列が含まれているかどうかを実現することができ,このアルゴリズムをBFアルゴリズムと呼ぶ.
BFアルゴリズム
BFアルゴリズム、すなわち暴力(Brute Force)アルゴリズムは、一般的なモードマッチングアルゴリズムであり、BFアルゴリズムの思想は、ターゲット列Sの最初の文字とモード列Tの最初の文字をマッチングし、等しければ、Sの2番目の文字とTの2番目の文字を比較し続けることである.等しくなければ、Sの2番目の文字とTの1番目の文字を比較し、最後の一致結果が得られるまで順次比較する.
BFアルゴリズム実装

public static int bruteforce(String s,String t){
    int length = s.length();//        
    int plength = t.length();//      

    //       
    for(int i=0;i

BFアルゴリズムは強力なアルゴリズムであり、最適化されていないが、2層のループで比較することであり、文字列が比較的大きい場合、実行効率が非常に低下し、比較的大きな文字列には適していない.
このアルゴリズムは最悪の場合$M*(N−M)$回の比較を行い,時間的複雑度は$O(M*N)$である.したがって、暴力を使って「m」文字の一連の「n」文字列を検索する場合は、n*m回を試してみる必要があります.
暴力的な検索は容易に実現され、解決策が存在すれば必ず見つかるが、その代価は候補案の数に比例している.このため、多くの実際の問題では、問題の規模が増加するにつれて消費される代価が急速に増加する.従って、問題の規模が限られている場合、または特定の問題に対する管理可能なサイズに候補ソリューションのセットを減少させるために使用可能な啓発的アルゴリズムが存在する場合、暴力的検索が一般的に使用される.また,実現方法の単純度が演算効率よりも重要である場合にも用いられる.
暴力的検索アルゴリズムは文字列を前処理する必要はないが,多くの不要なマッチングを行う必要があるため,より効率的なアルゴリズムが必要であることを示した.
ACオートマチックアルゴリズム
Aho-Corasickアルゴリズムは、Alfred V.AhoとMargaret J.Corasickによって発明された文字列検索アルゴリズムであり、入力された一連の文字列の中で予め構築されたTrieツリーのサブ列に一致するために使用される.通常の文字列と一致する点は、すべての辞書列と同時に一致する点です.アルゴリズムの割り当ての場合、線形に近似した時間的複雑さがあり、文字列の長さにすべてのマッチングの数を加算します.
mがモードの長さ、nが検索する文字列の長さ、kがアルファベットの長さであると仮定する.このアルゴリズムは,変異したTrieツリーを予め構築する必要があるため,$O(mk)$の前処理時間を必要とする.しかし,文字列を本格的に検索する際の時間的複雑度は$O(n)$であり,文字列検索時間を大幅に向上させた.
このアルゴリズムは主に有限状態機械の構築(Trieツリーに不整合ポインタを追加するのと同様)によって実現される.これらの追加の不一致ポインタは、文字列の検索に失敗したときにロールバック(例えば、Trieツリーの単語catマッチングに失敗したが、Trieツリーに別の単語cartが存在すると、不一致ポインタが接頭辞caを指す)を行い、ある接頭辞の他のブランチに転向し、重複した接頭辞を回避し、アルゴリズムの効率を向上させることができる.
辞書列の集合が既知(例えば、コンピュータウイルスライブラリ)である場合、自動機をオフラインで求めて保存して後で使用することができ、この場合、アルゴリズムの時間複雑度は入力文字列の長さとマッチング数の和であり、AC自動機アルゴリズムでよく用いられる場合でもある.
こうぞう
1.単語または内容に基づいてTrieツリーを構築します.これもgoto時計と言います.
2.単語の終わりに、Trieツリーのルートまたは他のブランチに同じ文字を指すことがあります.これは、プレフィックスの重複マッチングを回避し、アルゴリズムの効率を向上させるために、ロールバックポインタです.例えば、下の図の単語hisの末尾のsがsheのsを指すと、元の上で下に検索し続け、接頭辞のマッチング回数を減らすことができます.これもfail表と言います.
検索
現在のノードの「子ノード」を検索し、一致が見つからない場合は接尾辞ノードの子を検索し、まだ存在しない場合は、接尾辞ノードの対応するfailテーブルの接尾辞ノードの子を検索し、ルートノードに到達しても一致が見つからない場合は終了します.
アルゴリズムがノードを検索すると、現在の位置で終了したすべての辞書項目が出力されます.出力ステップは、ノードのディクショナリ接尾辞を最初に見つけ、ノードにディクショナリ接頭辞がないまで再帰的に実行する.また、ノードがディクショナリノードである場合、ノード自体が出力されます.
インプリメンテーション
GitHubにはオープンソースの実現があり、興味のある学生は詳しく読むことができます.https://github.com/robert-bor...
事前にそんなに多くの処理をする必要がなく、後期のマッチングが速いアルゴリズムはありますか?答えはKMPアルゴリズムです.
KMPアルゴリズム
それは3人の発明者の名前で、最初のKは有名な科学者Donald Knuthです.
KMPアルゴリズムの例このアルゴリズムの鍵は部分マッチングテーブル(partial match table、PMTテーブルとも呼ばれる)にあるが、この部分マッチングテーブルはどうやって来たのだろうか.パターン列「ababca」の部分マッチングテーブルを見てみましょう.

char:  | a | b | a | b | a | b | c | a |
index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 
value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |

対応するvalueは、パターン列「abababca」の部分マッチングテーブルです.
部分的な一致テーブルを理解するには、接頭辞と接尾辞を知る必要があります.「接頭辞」は、最後の文字を除いて、1つの文字列のすべてのヘッダの組合せを指す.「接尾辞」は、最初の文字以外の文字列のすべての末尾の組合せを指します.

   ：Knuth
  ：  K, Kn, Knu, Knut
  ：  nuth, uth, th, h

次に、「接頭辞」と「接尾辞」に基づいて、パターン列「ababca」の部分マッチングテーブルを求めます.

1. "a"           ，      ，    0；
2. "ab"     [a]，   [b]，      ，    0；
3. "aba"     [a, ab]，   [ba, a]，     "a",     1；
4. "abab"     [a, ab, aba]，   [bab, ab, b]，     "ab",     2；
...
7. "abababc"     [a, ab, aba, abab, ababa, ababab]，   [bababc, ababc, babc, bc, c]，      ,     0；
8. "abababca"     [a, ab, aba, abab, ababa, ababab, abababc]，   [bababca, ababca, babca, bca, ca, a]，     "a",     1；

どのようにして部分マッチングテーブルに基づいて検索しますか?
部分マッチングを見つけたら、不要な古い比較をやり直すのではなく、部分マッチングテーブルの値を使用してスキップできます.

     =         -         

「abababca」モード列と「bacbabaabcbab」文字列の一致例を示します.

bacbababaabcbab
 |
 abababca

最初のステップは、パターン列の先頭が「a」であり、文字列がループするため、2番目の文字が「a」であり、1つの文字が一致していることを示します.次の文字が一致しないため、移動する必要があります.移動するビット数は、部分一致テーブル(一致する文字数-1)に等しく、つまり、部分一致テーブルの下のテーブルが0の値で0になります.したがって、0文字を後ろにスキップしてループを続ける必要があります.

bacbababaabcbab
    |||||
    abababca

これで5文字が一致し、スキップする文字数は5-3=2で、2ビット後ろに移動する必要があります.

// x        

bacbababaabcbab
    xx|||
      abababca

3文字が一致し、スキップする文字数は3-1=2で、2ビット後ろに移動する必要があります.

bacbababaabcbab
      xx|
        abababca

この場合、私たちのモードはテキストの残りの文字より長いので、一致していないことがわかります.
まとめ
BFアルゴリズムは暴力的な解読方式に属し,貧挙を利用して文字列の検索を実現し,文字列が長すぎると検索速度が非常に遅い.
そこでまたACオートマチックアルゴリズムがあり、Trieツリーのような構造を先に構築し、Trieツリーに基づいて対応する文字列を検索すると、時間の複雑さの差は線形ではないが、事前にTrieツリーを構築する必要がある.
窮屈な方法でもTrieツリーを事前に構築する必要もないアルゴリズムはありませんか.
それは有名なKMPアルゴリズムで、この語が一致しないとき自体に十分な情報を含んでいることを用いて、次のマッチングがどこで始まるかを決定し、以前に一致した文字、つまり私たちの上の部分マッチングテーブル(PMTテーブル)の再検査を避けることができます.
PS:清山の緑の水は塵から始まり、博学多識は勤より高い.微信の公衆番号に注目して最新の文章を取得します.微信公衆番号:「清塵雑談」.一緒に話をして、コードを話してください.