文字列マッチングアルゴリズム(KMP、BM、Sunday)、Python実装

主に3種類の文字列マッチングアルゴリズム(KMP
、
BM
、
Sunday)
まとめます.この3つの文字列マッチングアルゴリズムの主な違いは、マッチング中に不整合ビットに遭遇した場合、どのようなポリシーでシフトするかということです.たとえば、次の2つの文字列があります.
 
文字列:ABCADAB ABCDABCDABD
検索文字列:ABCDA
 
3つのアルゴリズムの例を次に示します
KMP:このアルゴリズムでは、移動後の検索時に最初の不一致:A->Dに遭遇した場合、検索文字列から何ビット移動するかを決定します.KMPアルゴリズムの初期段階では、pi[0,...,4]={0,0,0,0,0,1}の検索文字列で生成されるテーブルが生成されます.この表は上記のシフトを決定します.このときのシフトは、3-pi[2](3文字が一致しているため)です.KMPアルゴリズムの鍵は,マッチング文字の初期生成テーブルであり,移動後から検索することである.
BM:このアルゴリズムでは、文字列検索は最初からではなく、最後から始まります.例えば、上記の例では、まずDとAを比較しています.違いがあるので、検索文字の中で後ろから前へマッチング検索を行い、右端のマッチング文字を見つけてからシフトします.見つからない場合、シフト長はマッチング文字と同じ長さです.以下のようになります.
文字列:ABCADAB ABCDABCDABD
検索文字列:ABCDA(2桁移動)
この場合は比較を継続するが、この場合の比較は上記の2つの過程を考慮し、もう1つは一致した文字列(DA)であり、検索文字列の接頭辞(A)が含まれており、このとき1~3ビット移動することは意味がないことが分かる.したがって、BMアルゴリズムの鍵は、2つのシフトのうちの最大シフトを見つけることであり、それを行うことである.
Sunday:上記の2つの文字列マッチングアルゴリズムは、検索文字の前処理に関連していますが、Sundayアルゴリズムはまったく異なると予想されています.同様に上記の例では,一致しない文字列が見つかった場合,Sundayアルゴリズムは全く異なる判定法を採用した.文字列のK+1文字目が先に見つかり、Kは検索文字の長さです.検索文字列にK+1文字目が含まれていない場合は、K+1ビットを直接移動します.そうでなければ、BMアルゴリズムに従って検索列の最右端の文字から末尾までの距離+1ビットを移動する.

    class StringPatternt(object):
        def __init__(self,chr,p):
            self.chr = chr;
            self.p = p;
            self.p_len = len(p);
            self.pi = [0 for i in range(self.p_len)];
        def set_pattern(self,p):
            self.p = p;
            self.p_len = len(p);
        def set_chr(self,chr):
            self.chr = chr;
            
        '''KMP'''
        def __kmp_partial_match_table__(self):
            k=0;q = 1;
            #self.pi[0] = 0;
            while q < self.p_len:
                while (k > 0) and (self.p[k] != self.p[q]):
                    k = self.pi[k-1];
                if self.p[k] == self.p[q]:
                    k = k+1;
                self.pi[q] = k;
                q = q+1;
            return 0;
        
        def string_pattern_kmp(self):
            self.__kmp_partial_match_table__();
            print(self.pi);
            list_size = len(self.chr);
            pi_len = len(self.pi);
            k=0;
            for q in range(list_size):
                while (k > 0) and (self.p[k] != self.chr[q]):
                    k = self.pi[k-1];
                if self.p[k] == self.chr[q]:
                    k = k+1;
                if k == pi_len:
                    return q-pi_len+1;
                #q = q+1;
            return 0;
        
        '''BM'''
        def __calc_match__(self,num):
            k=num;j=0;
            while k>=0:
                if self.p[-k] == self.p[j]:
                    k = k-1; j=j+1;
                    if k<=0:
                        self.pi[num-1] = num;
                        return 0;
                else:
                    if num == 1:
                        return 0;
                    self.pi[num-1] = self.pi[num-2];
                    return 0;
            
        def __init_good_table__(self):
            i=1;
            while i <= self.p_len:
                self.__calc_match__(i);
                i=i+1;
            print (self.pi);
            return 0;
        
        def __check_bad_table__(self,tmp_chr):
            i=1;
            while self.p_len-i >= 0:
                if self.p[-i] == tmp_chr:
                    return i;
                else:
                    i = i+1;
            return self.p_len+1;
        
        def __check_good_table__(self,num):
            if not num:
                return self.p_len;
            else:
                return self.pi[num];
        
        def string_pettern_bm(self):
            self.__init_good_table__();
            tmp_len = self.p_len;
            i = 1;
            while tmp_len <= len(self.chr):
                if self.p[-i]==self.chr[tmp_len-i]:
                    i = i+1;
                    if i > self.p_len:
                        return tmp_len-self.p_len;
                else:
                    tmp_bad = self.__check_bad_table__(self.chr[tmp_len-i])-i;
                    tmp_good= self.p_len-self.__check_good_table__(i-1);
                    tmp_len = tmp_len+ max(tmp_bad,tmp_good);
                    print(tmp_bad,tmp_good,tmp_len);
                    i=1;
            return 0;
        
        '''sunday'''
        def __check_bad_shift__(self,p):
            i=0;
            while i