最详细最容易理解的BM算法简介.ppt

《最详细最容易理解的BM算法简介.ppt》由会员分享，可在线阅读，更多相关《最详细最容易理解的BM算法简介.ppt（35页珍藏版）》请在三一办公上搜索。

1、Boyer-Moore算法简介,与之前算法的比较,暴力算法 与 KMP算法 都是基于前缀比较的算法BM算法则是基于后缀比较，而且BM算法其实上包含两个并行的算法：坏字符算法好后缀算法相同点：这些算法都是对文本串从左往右分析的,朴素的思想-坏字符算法,S=“FINDINAHAYSTACKNEEDLEINA”T=“NEEDLE”FINDINAHAYSTACKNEEDLEINA NEEDLE,朴素的思想-坏字符算法,S=“FINDINAHAYSTACKNEEDLEINA”T=“NEEDLE”FINDINAHAYSTACKNEEDLEINA NEEDLE NEEDLE,朴素的思想-坏字符算法,S=“F

2、INDINAHAYSTACKNEEDLEINA”T=“NEEDLE”FINDINAHAYSTACKNEEDLEINA NEEDLE NEEDLE NEEDLE,朴素的思想-坏字符算法,S=“FINDINAHAYSTACKNEEDLEINA”T=“NEEDLE”FINDINAHAYSTACKNEEDLEINA NEEDLE NEEDLE NEEDLE NEEDLE,朴素的思想-好后缀算法,CASE 1S=*BABCDE*T=ABCDEFGBCDE,朴素的思想-好后缀算法,CASE 1S=*BABCDE*T=ABCDEFGBCDET=ABCDEFGBCDE,朴素的思想-好后缀算法,CASE 2S=

3、*BABCDE*T=CDECDEGBCDE,朴素的思想-好后缀算法,CASE 2S=*BABCDE*T=CDECDEGBCDET=CDECDEGBCDE,坏字符算法,FINDINAHAYSTACKNEEDLEINA NEEDLE NEEDLE NEEDLE NEEDLE上面的N,S,N是坏字符，显然在该算法中存在两种情况：1.坏字符不在模式串中 2.坏字符在模式串中,Case 1,坏字符不在模式串中*TLE*NEEDLE NEEDLEShift=strlen(模式串)-position(坏)Shift=6-2,Case 2a,坏字符在模式串中*NLE*NEEDLE NEEDLEShift=最右

4、的坏字符位置position(坏)Shift=5-2,Case 2b,坏字符在模式串中*ELE*NEEDLE,Case 2b,坏字符在模式串中*ELE*NEEDLE NEEDLE 会有倒退 NEEDLE 不能预处理上面两种设计思想都可行，各有优缺点,预处理-坏字符,Shift=bmBcSi-（m-1-i)void preBmBc(char*S,int m,int bmBc)int i;for(i=0;i ASIZE;+i)/ASIZE=256 bmBci=m;for(i=0;i=m-1;+i)bmBcSi=m-i-1;,m-i,-1,预处理-坏字符,void preBmBc(char*S,in

5、t m,int bmBc)int i;for(i=0;i ASIZE;+i)/ASIZE=256 bmBci=m;for(i=0;i=m-1;+i)bmBcSi=m-i-1;这是会有倒退的算法设计，优点在于能够对模式串预处理,预处理-坏字符,void preBmBc(char*S,int m,int bmBc)int i;for(i=0;i ASIZE;+i)/ASIZE=256 bmBci=m;for(i=0;i=m-1;+i)bmBcSi=m-i-1;这是会有倒退的算法设计，优点在于能够对模式串预处理,O(M),思考题,为什么坏字符算法虽然倒退但是我们还是用这个算法呢？解答：坏字符算法虽然

6、倒退，但是BM算法中好后缀算法是确保不后退的，我们每次移动是取两个算法的最大值。这样一结合就保证了模式串不会倒退。而坏字符算法虽然后退但是有着能够预处理，代码实现简单，时间复杂度低的特点，所以被广为接受。在后面的SUNDAY 算法等改进算法中有的是使用了不后退的思路。,好后缀算法,当好后缀在模式串中重复出现时S=*BABCDE*T=ABCDEFGBCDE,好后缀算法,当好后缀在模式串中重复出现时S=*BABCDE*T=ABCDEFGBCDET=ABCDEFGBCDE,好后缀算法,模式串中没有子串匹配好后缀S=*BABCDE*T=CDECDEGBCDE,好后缀算法,模式串中没有子串匹配好后缀S=

7、*BABCDE*T=CDECDEGBCDET=CDECDEGBCDE此时需要寻找模式串的一个最长前缀CDE，并让该前缀等于好后缀BCDE的后缀，寻找到该前缀后，让该前缀和好后缀对齐即可。,好后缀算法,模式串中没有子串匹配上好后缀，并且在模式串中找不到最长前缀，让该前缀等于好后缀的后缀时S=*BABCDE*T=AACDEFGBCDE,好后缀算法,模式串中没有子串匹配上好后缀，并且在模式串中找不到最长前缀，让该前缀等于好后缀的后缀时S=*BABCDE*T=AACDEFGBCDET=AACDEFGBCDE,预处理-好后缀,模式串的预处理定义一个数组suffix，其中suffixi=s 表示以i为边界

8、，与模式串后缀匹配的最大长度，如下图所示，用公式可以描述：满足Ti-s,i=Tm-s,m的最大长度s。,预处理-好后缀,suffixm-1=m;for(i=m-2；i=0；-i)q=i;while(q=0,预处理-好后缀,void preBmGs(char*x,int m,int bmGs)int i,j,suffXSIZE;suffixes(x,m,suff);/对模式串进行预处理 for(i=0;i=0;-i)if(suffi=i+1)/如果找到一个最大前缀 for(;j m-1-i;+j)if(bmGsj=m)bmGsj=m-1-i;for(i=0;i=m-2;+i)bmGsm-1-su

9、ffi=m-1-i;,预处理-好后缀,void preBmGs(char*x,int m,int bmGs)int i,j,suffXSIZE;suffixes(x,m,suff);/对模式串进行预处理 for(i=0;i=0;-i)if(suffi=i+1)/如果找到一个最大前缀 for(;j m-1-i;+j)if(bmGsj=m)bmGsj=m-1-i;for(i=0;i=m-2;+i)bmGsm-1-suffi=m-1-i;,模式串中没有子串匹配上好后缀，但找不到一个最大前缀的情况,预处理-好后缀,void preBmGs(char*x,int m,int bmGs)int i,j,s

10、uffXSIZE;suffixes(x,m,suff);/对模式串进行预处理 for(i=0;i=0;-i)if(suffi=i+1)/如果找到一个最大前缀 for(;j m-1-i;+j)if(bmGsj=m)bmGsj=m-1-i;for(i=0;i=m-2;+i)bmGsm-1-suffi=m-1-i;,模式串中没有子串匹配上好后缀，但找不到一个最大前缀的情况,模式串中没有子串匹配上好后缀，但找得到一个最大前缀的情况,预处理-好后缀,void preBmGs(char*x,int m,int bmGs)int i,j,suffXSIZE;suffixes(x,m,suff);/对模式串进

11、行预处理 for(i=0;i=0;-i)if(suffi=i+1)/如果找到一个最大前缀 for(;j m-1-i;+j)if(bmGsj=m)bmGsj=m-1-i;for(i=0;i=m-2;+i)bmGsm-1-suffi=m-1-i;,模式串中没有子串匹配上好后缀，但找不到一个最大前缀的情况,模式串中没有子串匹配上好后缀，但找得到一个最大前缀的情况,模式串中有子串匹配上好后缀,预处理-好后缀,void preBmGs(char*x,int m,int bmGs)int i,j,suffXSIZE;suffixes(x,m,suff);/对模式串进行预处理 for(i=0;i=0;-i)

12、if(suffi=i+1)/如果找到一个最大前缀 for(;j m-1-i;+j)if(bmGsj=m)bmGsj=m-1-i;for(i=0;i=m-2;+i)bmGsm-1-suffi=m-1-i;,O(M),算法主体,Int BM_Search(char*S,char*T)j=0；while(j=0-i)if(i 0)match；else j+=max(bmGsi,bmBcTi-（m-1-i)；,算法主体,Int BM_Search(char*S,char*T)j=0；while(j=0-i)if(i 0)match；else j+=max(bmGsi,bmBcTi-（m-1-i)；,最好时O(strlen(S)/strlen(T)最坏时O(strlen(S)*strlen(T),总结,BM算法的关键主要在于对于两个数组的预处理。坏字符串 与 好后缀 都是尽可能的将模式串尽可能地往右移动。,