电路设计

BM算法的个人理解

2019-07-14 11:53发布

站内文章 / 电路设计
10499 0 975
抄来的BM算法思想 BM算法实际上包含两个并行的算法，坏字符算法和好后缀算法。 这两种算法的目的就是让模式串每次向右移动尽可能大的距离（j+=x，x尽可能的大）。 几个定义： 例主串和模式串如下： 主 串:   mahtavaatalomaisemaomalomailuun 模式串:  maisemaomaloma 好后缀：模式串中的aloma为“好后缀”。 坏字符：主串中的“t”为坏字符。   首先明确两个概念, 坏字符跳转BadSkip,好后缀移位GoodShift;(这个两个英文我觉得算比较好帮助理解的了) BM算法就是取坏字节跳转和好后缀移位中较大的进行偏移的…  
什么叫坏字符跳转呢? 先说明下,这个是一个空间换时间的简单算法. 建立一张包含所有目标字符串中字符的表,一般来说例如ASCII. 这样就有一个含有256个数据的数组了,其中特别的,数组的下标使用字符来标记的(0-255(字符的表示)). 这样是为了方便直接通过字符直接获取跳转量…特别的,当模式串中不存在此字符时,可以直接跳过剩下的所有字符的比较,Sunday算法就是基于这样的方式(但是它是匹配后面一个字符的) 上图:  1.bmp ~~~
 2.bmp
   一般的理解,是各个字符相对最后一个字符的位置偏移位置. 如上图中P c的跳转对应的是c排除最后字符的b(其实可以看做0 )…从后往前数第一个c 的位置..(2) 特别的,b的跳转值应该为3而不是0.. a的跳转值为1而不是a… 公式如下: 3.bmp
 实现代码可以自己写个了…    
下面介绍 好后缀移位 GoodShift. 这个是BM算法比较难的一点,但也是核心的部分. 好后缀移位用于从后往前匹配时已经部分匹配,但最近的一次不匹配的情况下的偏移量. 类似KMP算法.但是它是从后往前匹配的. (因为发现字符串整体是从前往后匹配,那么后面的字符必然会要取匹配,当发生前面匹配而后面不匹配的情况很多的时候,实为浪费)   设模式字符串P[len], 在i(正方向计数 用下标表示的) 位置发生了不匹配,(当然,前面步骤中都是匹配的)  那么匹配的字符串为P[i+1 ~ len ],   那么往前(从i-1开始)寻找一个等于 P[ i+1~ len ]的子串 , (如果模式串没有匹配这个子串,那其实整个匹配的部分都可以跳过去的) (len-i-1)用来表示匹配的串长度 如果模式串中存在 一个P[ x-(len-i-1) ~ x ](x-m+i+1>0)(按照搜索方向得到的x值) 和 P[ i+1 ~ len ] 一致  那么检查P[ x-(len-i-1) ~ x ] 前面一个字符 P[x-(len-i-1)-1] 与 P[i]是否相同.(这个和KMP的改进方式是一致的原理) 如果相同,则跳过此次子串,继续往前搜寻. 如果不同,则需要的偏移为 (总长度 减去 匹配的长度)i 再减去 (前面剩余的长度)   偏移量为 len – (len - i) – (x-(len-i-1))= len – x –1; 11.bmp 
第二种情况,如果没有找到这样一个子串,那么就用另外的一种方式:叫做 模式串前缀串中匹配串的最长后缀子串...看图好理解.   偏移量为 len – 2*x 222.bmp 
第三种情况,当然就是第二种情况也没发生后的结果…即整个串移过匹配串的位置.. 偏移量为 len 333.bmp

上代码: int* MakeShift(char* pStart,int pLen) { //为好后缀表申请pLen个int的空间 int *shift =(int*)malloc(pLen*sizeof(int)); int *pShiftCurrent = shift +pLen - 1;//方便给好后缀表进行赋值的指标 char *pCurrent = pStart + pLen - 1;//记录好后缀表边界位置的指标 char c; if(shift == NULL) { fprintf(stderr,"malloc failed!"); return 0; } c = *(pStart + pLen - 1);//保存模式串中最后一个字符，因为要反复用到它 *pShiftCurrent = 1;//以最后一个字符为边界时，确定移动1的距离 pCurrent--;//边界移动到倒数第二个字符（这句是我自己加上去的，因为我总觉得不加上去会有BUG，大家试试“abcdd”的情况，即末尾两位重复的情况） while(pShiftCurrent-- != shift)//该最外层循环完成给好后缀表中每一个单元进行赋值的工作 { char *p1 = pStart + pLen - 2, *p2,*p3; //该do...while循环完成以当前pCurrent所指的字符为边界时，要移动的距离 do{ while(p1 >= pStart && *p1-- != c){};//该空循环，寻找与最后一个字符c匹配的字符所指向的位置 //找到了这么一个与尾字符匹配的字符. p2 = pStart + pLen - 2; //p2 貌似指向已经匹配的子串的尾字符 p3 = p1; //p3指向找到的字符串的尾字符 //开始干活了...从后往前 连续比较... while( (p3 >= pStart && *p3-- == *p2--) && p2 >=pCurrent){};//该空循环，判断在边界内字符匹配到了什么位置 }while(p3 >= pStart && p2 >= pCurrent); //*pShiftCurrent *pShiftCurrent = shift + pLen - pShiftCurrent + p2 - p3;//保存好后缀表中，以pCurrent所在字符为边界时，要移动的位置 /* PS:在这里我要声明一句，*pShiftCurrent= （shift + pLen- pShiftCurrent） + p2 - p3; 大家看被我用括号括起来的部分，如果只需要计算字符串移动的距离，那么括号中的那部分是不需要的。 因为在字符串自左向右做匹配的时候，指标是一直向左移的，这里*pShiftCurrent保存的内容，实际是指标要移动距离，而不是字符串移动的距离。 我想SNORT是出于性能上的考虑，才这么做的。 */ pCurrent--;//边界继续向前移动 } return shift; }
未完待续...
 后面介绍suff[]方法,求BmGc的过程...其实它本身的发展应该 类似 KMP中 next到nextval的过程吧...纯属猜测...

热门文章