BM 算法

Love The Way You Lie 2022-02-05 09:29 442阅读 0赞

看完上次的kmp后准备看BM算法， 但是一直都没有时间，感觉，看网上的一些原理解释并不能看的很懂，然后看了就迷迷糊糊的，现在总结一下，顺便是理清思路！不知道自己会不会讲的清楚一点！( 至于代码，自己写的还在测试，不知道有没有错，现在贴上来的是参照snort中的代码！虽然网上的很多代码都是这个！不过后来会写上自己的代码的 )

BM 算法思路：

1：

BM算法是整体字串是从左往右移动，但是一旦字串停在某个位置时候，实际的匹配是从右往左的，例如：

原串：A B C E C A B E

字串：A B C A B

停在此处，那么匹配从右往左开始，即：

原串：A B C E C A B E

字串：A B C A B

<<<---------------------

一旦一个字符不匹配的时候，(我们称这个字符为“坏字符”)，我们采取两种办法即

坏字符规则 和好后缀规则来确定字串到底要整体往右移动几个距离，然后再来进行从右往左的比较！所以编程的时候肯定是有两个函数分别返回当前情况需要向右移动几个单位，我们取两个中的较大的移动长度即可！

下面，来详细介绍一下坏字符规则 和好后缀规则

“坏字符规则“：

例如：

原串：A B C E C A B E

字串：A B C A B              （图一）

有个坏字符！

我们需要怎么处理呢？

**有两条规则：**

《1》. 在原串中，若那个坏字符在字串中没有，那么在原串中从此字符开始的strlen(子串)个长度的串不可能与字串匹配！**所以直接跳过该坏字符**，即需要移动的长度是字串首字符到字串中对应的坏字符长度！(具体见下面第二个例子)

《2》. **若那个坏字符在未进行匹配的剩余子串中能找到**，那么在剩余子串中找到最右边的那个字符，然后与该字符对齐。

对于上面的例子：

C在字串中从右开始的第三个位置出现的，那么移动长度为5 – 3 = 2

A  B   C   E   C   A   B   E

\-------  A   B   C    A   B                          （图二）

此时我们发现：

A B  C  E  C A  B  E                            （图三）

\--------- A  B  C  A  B

又出现坏字符，若使用“坏字符规则”，那么我们寻找E是否在字串中出现，我们发现没有找到，那么移动后为：

A B  C  E  C A  B  E                             （图四）

\------------- A  B  C  A  B

即：跳过此坏字符即可！！！

(  在看代码的时候注意一下就ok！ )

特别注意：在算法中有这么一段，之前得到了“坏字符表”，在处理往后移动的时候是：

i +=  max( bad\_char\_table\[(unsigned char)str\[tmp\]\] -x, good\_suffix\_table\[j\] );

(x是后缀已经匹配的长度)

(str是原串)

(bad\_char\_table是坏字符表)

(good\_suffix\_table是好后缀表)

(tmp是当前指针所在原串中的下标，即坏字符下标)

(j是字串中当前匹配坏字符的那个位置)

不清楚代码没有关系，随后再看。

看代码的时候注意：此处要减去一个x是必须的。因为上面说的很清楚了，是在尚未进行匹配的的剩余子串中！

**===》那么我们在编程的时候需要怎么做？**

从上面我们知道，字串中没有出现的字符若是坏字符，那么直接向右移动strlen(子串)长度即可！对于出现的字符，我们知道是以最右边出现的第一个字符为基准的(也就是说，字串中有几个相同的字符，那么也是要以最右边的那个字符位置来定移动长度)，所以，对于所有的字符，以及其移动的长度，我们都是可以提前预测到的！

我们知道：字符共256个，那么定义个int数组a\[256\]  (所以的ASCII码都包含在内)，对于字串中没有出现的直接赋值为strlen(子串)，对于字串中有的字符，按照右边位置进行处理即可！

下面看看：

“好后缀规则”

对于串：

A B  C  E  C  A  B   E A  B  C

\------ A  B  C  A  B

所谓好后缀，就是后面有一部分小串是匹配的，前面有不匹配的而已！

**那么需要遵循什么规则呢？也有2点规则**

《1》. 在子串中，若当前的后缀在前面也是有的( **但是还有一个条件是之前的一个字符不再匹配！**如下面的D和E )，例如

XX X X  X X  X  X M  A  B C  D

E  A  B  C  D   D D  A  B  C  D

那么，将前面的串移动到后面既可以：

XX X X  X X  X  X X  A  B  C  D

E  A  B  C  D  D  D A  B  C  D

很好理解，若之前一个字符还是相同的，那么和本次的情况还是一样的，没有好转，若不相同，那么还是有机会匹配到这个坏字符的！

《2》.如果上面的没有结果，那么就找**子串中尚未进行匹配的部分的前缀**尽可能大的匹配 **"好后缀" 的后缀**！

例如：

原串：A  B  C  E  C  A  B E

子串：         A  B  C  A  B

可以很清楚的看到，C A B 在前面没有匹配了，那么只能是第二种情况，看到未匹配的前缀和已经匹配的后缀最大的匹配就是 A B，那么移动：

原串：A  B  C E  C   **A  B**  E

子串：                     **A  B ** C  A  B

**===》那么我们在编程的时候需要怎么做？**

我们知道只要字串确定了，那么所有的什么前后所谓的匹配也是确定了的，所有也可以建立一个表，预先得到：当遇到那个后缀的时候，怎么去移动！那么需要定义一个数组

b\[\], 其长度就是字串的长度，为什么呢，因为b\[0\]保存的是后面整个长度后缀时候需要移动的长度，…..b\[len-1\]保存的就是最后一个字符长度的后缀时候需要移动的距离！

然后在遇到不匹配的时候，从两个数组中取相应的值，取两个中较大的一个进行移动即可！

上面就是原理，不知道有没有说清楚~

好的，最后冷静一下，总结一下：其实总体的思路就是提前建好“坏字符”表和“好后缀”， 然后进行BM算法，当遇到字符不匹配时候， 就需要决定整体字串应该向右边移动几位，所以需要查两个表，然后取其中大的值，就是字串移动的距离！

下面就是代码(参考snort)，后期会贴上自己的代码

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <assert.h>
    
    // max函数
    // 
    int get_max( int a, int b )
    {
    	return ( a > b ? a : b );
    }
    
    // 得到坏字符表
    // 
    // 参数:
    //		sub_str：匹配串
    //		len：匹配串长度
    //		bad_char_table：保存坏字符表
    //
    void get_bad_char_table( char sub_str[], int len, int bad_char_table[] )
    {
    	int i = 0;
    	int tmp_len = len;
    
    	// 初始化坏字符表，256个单元全部初始化为len
    	// 
    	for( i = 0; i < 256; ++i )
    	{
    		bad_char_table[i] = len; // 即不在的字符跳过此区域，也就是向后移动匹配串长度个字符(即pLen)
    	}				 // 存在的字符下面在处理
    	
    	while( len )
    	{
    		bad_char_table[(int)*sub_str++] = --len;	// (int)*sub_str转化成字符的ASCII码而已
    	}												// 下面就是遇到不匹配，但是在字串中，需要移动几个单位
    }
    
    // 下面计算 "好后缀" 好后缀表
    //
    // 参数:
    //		sub_str：匹配串
    //		len：匹配串长度
    //		good_suffix_table：保存好后缀表
    //
    void get_good_suffix_table( char sub_str[], int len, int good_suffix_table[] )
    {
    	
    	int  *sptr = good_suffix_table + len - 1;	// 方便为好后缀表进行赋值的指针
    	char *pptr = sub_str + len - 1;			// 记录好后缀表边界位置的指针
    	char c;						// 保存最后一个字符
    	char *p1, *p2, *p3;
    
    	c = *( sub_str + len - 1 );	
    	*sptr = 1;
    	pptr--;										// 边界移动到倒数第二个字符
    
    	while( --sptr >= good_suffix_table )		//该最外层循环完成给好后缀表中的每一个单元进行赋值的工作
    	{
    		p1 = sub_str + len - 2;			// 倒数第二个字符
    		
    		do
    		{
    			while( p1 >= sub_str && *p1-- != c );	// 该空循环，寻找与最后一个字符c匹配的字符所指向的位置
    		
    			if( p1 < sub_str )			// 没有找到
    			{
    				*sptr = len;			// 没有找到那么只能是len长度
    				break;
    			}
    
    			p2 = sub_str + len - 2;		// 倒数第二个字符
    			p3 = p1;			// 当前第一个匹配的字符位置( 从右往左的 )
    
    			while( p3 >= sub_str && *p3-- == *p2-- && p2 >= pptr );	// 该空循环，判断在边界内字符串匹配到什么位置
    																	// 即得到最长匹配 
    			if( p2 < pptr )	// 这是当前要求长度的后缀已经匹配完成
    			{
    				if( *++p3 == *++p2 )				// 
    				{
    					*sptr = p2 - p3;
    					break;
    				}
    				
    				if( *p2 == *p3 )// 注意为什么会有这一步：对应原理中：后缀完全匹配，但是要求，之前的一个字符是不相同的才OK
    				{
    					continue;
    				}
    			}
    
    			if( p3 < sub_str )		// 原串匹配到头
    			{
    				*sptr = p2 - p3;
    				break;
    			}
    
    		}while( p3 >= sub_str );
    		
    		pptr--;				 // 边界继续向前移动
    	}
    	
    }
    
    // 下面就是BM处理
    // 参数：见上面两个函数
    // 
    int bm_search( char str[], int len1, char sub_str[], int len2, int bad_char_table[], int good_suffix_table[] )
    {
    	int i = len2;		// 用来计算移动的距离
    	int j, tmp, x;
    
    	if ( len2 == 0 )
    	{
    		return -1;
    	}
    
    	while( i <= len1 )	// 匹配尚未结束
    	{
    		j = len2;
    		tmp = i;		// 又一次开始匹配的位置
    		x = 0;
    
    		while ( str[--tmp] == sub_str[--j] )	// 看当前是否匹配
    		{
    			++x;
    
    			if ( j == 0 )			// 匹配串匹配结束
    			{
    				return i - len2;	// 第一个字符匹配位置
    			}
    		}
    		
    		i += get_max( bad_char_table[(unsigned char)str[tmp]] - x, good_suffix_table[j] );	// 计算应该向后移动多少位置
    	}								// 
    	
    	return -1;
    }
    
    // MAIN函数
    // 
    int main()
    {
    	char	str[1000];//="9634ghvecn  eirfqo fhoroe o e ovqherf938g4fh00000000@#$%^&*wo dwef";
    	char	sub_str[100];//="ovqher";
    	int		*bad_char_table = NULL;
    	int		*good_suffix_table = NULL;
    	int		idx;
    	
    	printf("\n输入原串：");
    	gets( str );
    
    	printf("\n输入匹配串：");
    	gets( sub_str );
    	
    	// 下面为256个字符分配坏字符表空间
    	//
    	bad_char_table = ( int* )malloc( 256 * sizeof( int ) );
    	assert( bad_char_table != NULL );
    
    	// 下面为"好后缀"分配表空间
    	// 
    	good_suffix_table = ( int* )malloc( strlen( sub_str ) * sizeof( int ) );
    	assert( good_suffix_table != NULL );
    
    	// 下面计算 "坏字符" 坏字符表
    	// 
    	get_bad_char_table( sub_str, strlen( sub_str ), bad_char_table );
    
    	// 下面计算 "好后缀" 好后缀表
    	//
    	get_good_suffix_table( sub_str, strlen( sub_str ), good_suffix_table );
    
    	// 下面就是BM处理
    	// 
    	idx = bm_search( str, strlen( str ), sub_str, strlen( sub_str ), bad_char_table, good_suffix_table );
    
    	if ( idx == -1 )
    	{
    		printf("没有可以匹配的串！\n");
    	}
    	else
    	{
    		printf("第一个匹配的位置是(下标从0开始)：%d\n", idx);
    	}
    	
    	// 下面回收资源
    	// 
    	if ( bad_char_table )
    	{
    		free( bad_char_table );
    		bad_char_table = NULL;
    	}
    
    	if ( good_suffix_table )
    	{
    		free( good_suffix_table );
    		good_suffix_table = NULL;
    	}
    
    	return 0;
    }