一般的なパターンマッチング(文字列マッチング)アルゴリズム

はテキスト処理において、キーワードマッチングは非常に一般的で重要な機能である.キーワードをモードストリングと呼び、テキストTでモードストリングPの出現するすべての位置を探します.このような問題を解決するアルゴリズムを文字列マッチングアルゴリズムといいます.文字列マッチングアルゴリズムは、コンピュータ科学において最も古く、最も広範な問題の一つであり、文字列マッチングの応用も随所に見られ、特に情報検索分野と計算生物学分野である._; パターンマッチングアルゴリズムはたくさんあります.有名なアルゴリズムはKMPアルゴリズム、BMアルゴリズム、Sundayアルゴリズム、Horspoolアルゴリズムがあります.次に,モードマッチングにおけるいくつかの一般的なアルゴリズムを簡単に紹介する.
1.シンプルなマッチングアルゴリズム
  素朴なマッチングアルゴリズムは、テキストの先頭から順に比較することによって、パターンの列を後方にマッチングさせる暴力的なマッチング方法である.シンプルなマッチングアルゴリズムは、テキストTの長さをmと仮定し、パターン列Pの長さをnと仮定して、比較的容易な方法である.アルゴリズムは、テキストの第1位から左から右に向けてモード串Pとマッチし、マッチングに成功したかどうかにかかわらず、モード列は後に1ビット移動して再マッチングを開始し、合計m-n＋1回のマッチを行います.アルゴリズムは極めて簡単であり、従って効率は極めて限られており、時間の複雑さはO(m＊n)であるため、あまり使われない.ここでは詳細に紹介しない.
2.KMPアルゴリズム
位置
0
1
2
3
模式文字列
円
円
大きい
先生
部分マッチング値
0
1
0
0
  KMPアルゴリズムは3人の科学者(Knuth、Morris、Prat)によって共同で提案されたモードマッチング方法です.KMPは相対的に効率的なモードマッチングアルゴリズムであり、文字列マッチング中の失敗情報を利用してモードマッチングの回数を減少させてマッチング性能を向上させることができるため、高性能である.  KMPアルゴリズムは補助構造の助けを借りています.部分マッチングテーブルはモードストリングに対して生成された補助情報テーブルです.このテーブルを通じて、マッチング失敗時に無駄なマッチング回数を低減できます.部分マッチングテーブルの長さはモード列の長さと同じで、部分的には現在の文字に対応する「プレフィックス」と「サフィックス」の最も長い共通要素の個数である.   今は「輪大師」があると仮定して、一部の整合表を以下のような過程で得ることができます.(2)「丸」については、プレフィクスは「丸」であり、後は「輪」となり、要素の数は1であるため、第二の「丸」の部分マッチング値は1である.(3)「丸が大きい」に対しては、プレフィクスは「丸」、「丸」、後は「大」、「丸が大きい」とし、要素の数は0であるため、第3の単語の部分マッチング値は0である.(4)「輪大師」に対して、その接頭語は「輪」、「輪」、「輪大」であり、後は「師」、「大師」、「輪大師」と続く.共有要素の数は0です.したがって、4番目の単語の部分マッチング値は0です.以上で、私たちは次のような部分的なマッチングテーブルを得ることができます.
位置
0
1
2
3
模式文字列
円
円
大きい
先生
部分マッチング値
0
1
0
0
  部分マッチング表はKMPアルゴリズムによる文字列検索の重要な参考となりますので、一部のマッチテーブルがありましたら、テキストの「丸を描く輪の大師匠」に対してモード串「丸師匠」のマッチングを行うことができます.マッチング方式は、前kビットマッチングが成功した場合、後シフト数s＝現在一致している文字数k−最後の一致ワードの部分マッチング値である.マッチングのプロセスは以下の通りです.

step1：
         
    

step2：
         
     

step3：
         
        

step4：
         
         

  KMPアルゴリズムは二つのステップに分けられ、まずPを通じて部分マッチングテーブルを計算し、時間複雑度はO(n)である.この表を通して整合変位を行います.時間の複雑さはO(m)です.したがって、理論上の全時間複雑度はO(m＋n)で、線形効率になります.理論の効率は高いが、実際には特に目立っていない.KMPコードの実現は以下の通りです.

3.Boyer-Moore

  Boyer-Moore BM ， KMP 。BM KMP ， 。
   KMP ：
  ① ， ，BM ， 。
  ② ： 。

step1:
HERE IS A SIMPLE EXAMPLE
EXAMPLE

   ， ， ， “S” “E”， ， ， 。
   BM ， ， ； “S” “E” ， “S”。 ， “S” ：

step2:
HERE IS A SIMPLE EXAMPLE
       EXAMPLE

   ， “P” “E” ， “P”， ， “P” ：

step3:
HERE IS A SIMPLE EXAMPLE
         EXAMPLE

   ，“E” ，“L” ，“P” ，“M” ，“I” “A” ！ ， “E” ， “E” ：

step4:
HERE IS A SIMPLE EXAMPLE
               EXAMPLE

   ， “P” “E” ， “P”， ， “P” ：

step5:
HERE IS A SIMPLE EXAMPLE
                 EXAMPLE

   ， ， ， ！
   BM ， KMP ， ， KMP 3~5 。
BM (JAVA)：

4.Sunday

step1:
HERE IS A SIMPLE EXAMPLE
EXAMPLE

   ， “T” “E” ， （ “IS” ） ， ， 。 ， “A”：

step2:
HERE IS A SIMPLE EXAMPLE
        EXAMPLE

   “A” “E” ， “E” ， ， ：

step3:
HERE IS A SIMPLE EXAMPLE
         EXAMPLE

   “E” ， “ ” ， “E”：

step4:
HERE IS A SIMPLE EXAMPLE
                 EXAMPLE

   ， ！
   Sunday ： ， ， ， ， ； ， ， 。
Sunday (JAVA)：

public static List Sunday(String txt, String part){
        List locs = new ArrayList();
        final int tlen = txt.length();
        final int plen = part.length();
        
        for(int start = 0, newS = 0; start + plen <= tlen; ){
            if(isPattern(start, txt, part)){
                locs.add(start);
                start += plen;
            }else{
                newS = start + plen;
                if(newS >= tlen)
                    break;
                int lIndex = part.lastIndexOf(txt.charAt(newS));
                if(lIndex == -1){
                    start = newS ++;
                }else{
                    start += plen - lIndex;
                }
            }
        }
        return locs;
    }
    
    private static boolean isPattern(int start, String txt, String part){
        boolean isPattern = true;
        
        //      
        if(null == txt || null == part || start >= txt.length() || start + part.length() > txt.length()){
            isPattern =  false;
        }
        
        //         
        for(int i = 0; isPattern && i < part.length(); i++){
            if(txt.charAt(i + start) != part.charAt(i)){
                isPattern = false;
                break;
            }
        }
        return isPattern;
    }

：
（1）https://www.cnblogs.com/Franky-ln/p/5890201.html

142