串匹配算法_BM

喜欢ヅ旅行 2022-05-21 06:05 171阅读 0赞

## 串匹配算法\_BM ##

[KMP][]算法的思路可以概括为：当前比对一旦失配，即利用此前的比对所提取的信息，尽可能长距离的移动模式串。其精妙之处在于，无需显示地反复保存或更新比对的历史，而是独立于具体的文本串，事先根据模式串预测出所有可能出现的适配情况，并将这些信息浓缩成一张next表。  
在这里介绍的BM算法与KMP算法类似，区别仅仅在于预测和利用“历史”信息的具体策略与方法。BM算法中，模式串P与文本串T的位置依然“自左向右”推移，而在每一对准位置确是“自右向左”的逐一比对。为了实现高效率，BM算法同样需要充分利用以往的比对所提供的信息，使得P可以“安全地”向后移动尽可能原的距离。

## **坏字符策略** ##

如下图所示，若模式串P当前在文本串T中的对齐位置为i，且在这一轮自右向左的比对过程中，在P\[j\]处首次发现失配：T\[i+j\] = ‘X’ != ‘Y’ = P\[j\]。  
![这里写图片描述][70]  
**此时所面临的问题是，应该选择P中的哪个字符对准T\[i+j\]，然后开始下一轮自右向左的比对？**  
一种可行的想法是，若P与T的某一（包含T\[i+j\]在内的）子串匹配，则必然在T\[i+j\]=‘X’处匹配；所以可以如上图所示，找到P中的字符X，并使之与T\[i+j\]对准，然后再次自右向左扫描比对。与KMP算法类似，我们这里得出一张BC表来方便处理。

--------------------

bc\[\]表  
当P中包含多个’X’时，是不需要进行逐一尝试的，而是仅尝试P中最靠右的那个（存在的话），与KMP算法类似，如此可以在确保不遗漏的前提下，始终单向的滑动模式串，具体如下图所示：  
![这里写图片描述][70 1]  
如上图所示，P中最靠右的字符’X’为P\[k\]=’X’，则P的右移量为j-k。并且对于任一给定的模式串P，k值只取决于字符T\[i+j\] = ‘X’，因此可将其视作从字符表到整数的一个函数：

> 1、P中含有字符c时  
> bc(c)=k （P\[k\]=c ，且对所有的 i>k 都有P\[i\]!=c）  
> 2、P中不含有字符c时  
> bc(c) = -1

**因此，一旦出现坏字符，即重新对齐于：i=i+j-bc\[T\[i+j\]\]。**

除了上述之外，bc表还要处理特殊情况：  
**1、若P中不含字符’X’时**  
当P中不含有字符‘X’时，应该将P整体移过字符‘X’，如下图所示：  
![这里写图片描述][70 2]  
在对应的bc表中，将此项置位-1，与KMP算法处理的方法类似，效果等同于在模式串最左侧加上了一个通配符。  
**2、P中含有字符‘X’，但是位置太靠右**  
另外一种情况就是，P中含有字符‘X’，但是位置太靠右，导致k=bc\[‘X’\]>=j，导致移动的距离j-k不再是正数，如果还是按照上述移动就会出现以下情况：  
![这里写图片描述][70 3]  
这时，处理的方法如上图所示，将P右移一个单位，开始下一轮的比对。

//bc表的实现
     //*****************************************************************************************
     //    0                       bc['X']                                
     //    |                       |                                      |
     //    ........................X***************************************
     //                            .|<------------- 'X' free ------------>|
     //*****************************************************************************************
     int* buildBC ( char* P ) { //构造Bad Charactor Shift表：O(m + 256)
        int* bc = new int[256]; //BC表，与字符表等长
        for ( size_t j = 0; j < 256; j ++ ) bc[j] = -1; //初始化：首先假设所有字符均未在P中出现
        for ( size_t m = strlen ( P ), j = 0; j < m; j ++ ) //自左向右扫描模式串P
           bc[ P[j] ] = j; //将字符P[j]的BC项更新为j（单调递增）——画家算法
        return bc;
     }

--------------------

**bc策略性能分析**  
根据上述的分析，在bc表的构建时，时间消耗主要在于两个部分对字符表N进行初始化，需要O(N)时间，后一轮对模式串进行一趟扫描需要O(m)时间，因此构建bc表花费O(N+m)的时间，以及O(N)的空间。  
复杂度：若暂且不计构造BC表的过程，BM算法本身进行串模式匹配所需要的时间与具体的输入十分相关，下面加入文本串的长度文n，模式串的长度为m。  
1、查找时间：最好=O(n/m)  
![这里写图片描述][70 4]  
此时，可以一次移动m个字符。这种情况在字符集越大的情况下出现的概率最高。

2、查找时间：最坏= O(n\*m)  
![这里写图片描述][70 5]  
在这种情况时，每一轮迭代都要扫描整个P，才可以确定右移一个字符。在字符集约小时，局部匹配的概率越高。

**bc策略不足**  
上面的复杂度分析，已经说明了在最坏的情况下，时间复杂度会退化成蛮力算法一样，这有何办法避免这种情况？具体的先看下面例子：  
![这里写图片描述][70 6]  
在P\[4\] = ‘A’ 与 T\[4\] = ‘C’ 失配后，P 只右移 1 个字符。实际上，此前（成功）的比对已经给出了足够的信息。根据这些信息，完全可以将 P 右移 4 个字符，如下所示：  
![这里写图片描述][70 7]  
下面将具体讲解这种方法，因为其利用成功比对的信息，所以将其称为好后缀策略。

## **好后缀策略** ##

**好后缀**  
每轮比对中的若干次(连续的)成功匹配，都对应于模式串P的一个后缀，称作好后缀，必须充分利用好后缀所提供的信息，一般的如下图所示：  
![这里写图片描述][70 8]  
进一步的如下图所示，存在某一整数k，使得将p右移j-k个单元，并且使得P\[k\]与T\[i+j\]相互对齐之后，P能够与文本串T的某一子串匹配。  
![这里写图片描述][70 9]  
根据上面可以得到，为了可以做新的一轮的匹配，则P的子串u’必须与自己的后缀u相互匹配，此外还有一个条件P\[K\]！=P\[j\]，否则绝对不会出现与P整体的匹配。当然，若模式串P中同时存在多个满足上述条件的子串u’，则选择其中的最靠右者，使得移动的距离最小，这样保证不遗漏任何匹配位置，也可以避免模式串回退。此外，若P中没有任何子串u’可以与好后缀u完全匹配，此时需要从P的所有前缀中，找出可以与u的某一真后缀相匹配的最长者，如下所示：

![这里写图片描述][70 10]

--------------------

**gs表构造算法**  
可以仿照KMP算法的做法，通过预处理，将模式串P事先转换成一张查找表gs\[0, m)，其中gs\[j\] = j-k分别记录对应的位移量。

为了构造出gs表，首先要引入ss\[\]表和MS\[\]串。如下图所示，对于任一整数j属于\[0,m)，在P\[0,j\]的所有后缀中，考察与P的某一后缀匹配者。将其中的最长者记为MS\[j\]，则ss\[j\]就是该串的长度| MS\[j\] |。特别地，当MS\[j\]不存在时，取ss\[j\] =0。可以描述为：P\[i-s, i\] == P\[m-s, m\]的最大长度s。  
![这里写图片描述][70 11]  
可以实现如下：

int * bulidss(const string & pat)
    {
        const int len = pat.length();
        int num;
        int *suff = new int[len];
        suff[len - 1] = len;
        for (int i = len - 2; i >= 0; --i)
        {
            for (num = 0; num <= i && pat[i-num] == pat[len-num-1]; ++num);
                suff[i] = num;
        }
        return suff;
    }

上面构造SS\[\]表的方法时间复杂度为O(m^2)，较为直接，下面再书上看到一种O(m)的方法，但是不太明白意思……这里还是列出。。

int* buildSS ( char* P ) { //构造最大匹配后缀长度表：O(m)
        int m = strlen ( P ); int* ss = new int[m]; //Suffix Size表
        ss[m - 1]  =  m; //对最后一个字符而言，与之匹配的最长后缀就是整个P串
     // 以下，从倒数第二个字符起自右向左扫描P，依次计算出ss[]其余各项
        for ( int lo = m - 1, hi = m - 1, j = lo - 1; j >= 0; j -- )
           if ( ( lo < j ) && ( ss[m - hi + j - 1] < j - lo ) ) //情况一
              ss[j] =  ss[m - hi + j - 1]; //直接利用此前已计算出的ss[]
           else { //情况二
              hi = j; lo = __min ( lo, hi );
              while ( ( 0 <= lo ) && ( P[lo] == P[m - hi + lo - 1] ) ) //二重循环？
                 lo--; //逐个对比处于(lo, hi]前端的字符
              ss[j] = hi - lo;
           }
        return ss;
     }

由ss表构造出对应的gs表，可以分为两种情况如下图所示：  
![这里写图片描述][70 12]  
第一种情况如上图a所示，该位置j满足：ss\[j\] = j+1。也就是说，MS\[j\]就是整个前缀P\[0,j\]。对于P\[m-j-1\]左侧的每个字符P\[i\]而言，都对应于上面最后一种情况，即下图：  
![这里写图片描述][70 10]  
此时，m-j-1都应该是gs\[i\]取值的一个候选者。

第二种情况，如图b所示，设该位置j满足：ss\[j\]<=j。也就是说MS\[j\]只是P\[0, j\]的一个真后缀。同时，MS\[j\]是极长的，所以，P\[m-ss\[j\]-1\]!=P\[j-ss\[j\]\]。所以此时P\[m-ss\[j\]-1\]恰好对应上面的第一种情况，如下图：  
![这里写图片描述][70 9]  
此时，m-j-1应该是gs\[m-ss\[j\]-1\]取值的一个候选者。

进一步地，gs\[i\]的候选者应该是上面候选者中的最小者，因此可以实现如下：

int* buildGS ( char* P ) { //构造好后缀位移量表：O(m)
        int* ss = buildSS ( P ); //Suffix Size table
        size_t m = strlen ( P ); int* gs = new int[m]; //Good Suffix shift table
        for ( size_t j = 0; j < m; j ++ ) gs[j] = m; //初始化
        for ( size_t i = 0, j = m - 1; j < UINT_MAX; j -- ) //逆向逐一扫描各字符P[j]
           if ( j + 1 == ss[j] ) //若P[0, j] = P[m - j - 1, m)，则
              while ( i < m - j - 1 ) //对于P[m - j - 1]左侧的每个字符P[i]而言（二重循环？）
                 gs[i++] = m - j - 1; //m - j - 1都是gs[i]的一种选择
        for ( size_t j = 0; j < m - 1; j ++ ) //画家算法：正向扫描P[]各字符，gs[j]不断递减，直至最小
           gs[m - ss[j] - 1] = m - j - 1; //m - j - 1必是其gs[m - ss[j] - 1]值的一种选择
        delete [] ss; return gs;
     }

--------------------

综合以上情况，可以得到BM采用好后缀与坏字符结合的策略，加快了模式串相对于文本串向右的移动速度，可以实现为：

int match ( char* P, char* T ) { //Boyer-Morre算法（完全版，兼顾Bad Character与Good Suffix）
        int* bc = buildBC ( P ); int* gs = buildGS ( P ); //构造BC表和GS表
        size_t i = 0; //模式串相对于文本串的起始位置（初始时与文本串左对齐）
        while ( strlen ( T ) >= i + strlen ( P ) ) { //不断右移（距离可能不止一个字符）模式串
           int j = strlen ( P ) - 1; //从模式串最末尾的字符开始
           while ( P[j] == T[i + j] ) //自右向左比对
              if ( 0 > --j ) break;
           if ( 0 > j ) //若极大匹配后缀 == 整个模式串（说明已经完全匹配）
              break; //返回匹配位置
           else //否则，适当地移动模式串
              i += __max ( gs[j], j - bc[ T[i + j] ] ); //位移量根据BC表和GS表选择大者
        }
        delete [] gs; delete [] bc; //销毁GS表和BC表
        return i;
     }

结合了好后缀与坏字符之后的BM算法，最坏的运行时间也可以保持线性O(n+m)。

[KMP]: https://blog.csdn.net/xc13212777631/article/details/80874057
[70]: /images/20220521/65894ed345cd4629b02708562910cc01.png
[70 1]: /images/20220521/9f203a90fdad4977b2880fccef2f3618.png
[70 2]: /images/20220521/4faf8a75231541b8b7438d9fd9902609.png
[70 3]: /images/20220521/8f76e30bbf9a4857b08c2997881267d6.png
[70 4]: /images/20220521/bbbc9926237540e48fd1252ec4fc28e4.png
[70 5]: /images/20220521/47ad765e90644223acda3db97565edc9.png
[70 6]: /images/20220521/06d8ed586e5548f8b7f22aa0b72ea002.png
[70 7]: /images/20220521/a4f25133c48b4a91be4bee91377b303d.png
[70 8]: /images/20220521/5911bfc74e2743048fc81eb87672b777.png
[70 9]: /images/20220521/ac47a6ca92a143dfb2305fa6a238a56b.png
[70 10]: /images/20220521/49c55851a73743e4a46f055420ef417d.png
[70 11]: /images/20220521/4e671708607f43ed85e0b94775f08d83.png
[70 12]: /images/20220521/55f2ffae29dd452da2f65d53aef4dfb0.png