iptables --algo 字符串匹配算法 bm kmp

时间:2022-12-28 15:58:15

http://blog.csdn.net/l953972252/article/details/51331001

字符串匹配一直是计算机领域热门的研究问题之一,多种算法层出不穷。字符串匹配算法有着很强的实用价值,应用于信息搜索,拼写检查,生物信息学等多个领域。 
今天介绍几种比较有名的算法: 
1. BF 
2. BM 
3. Sunday 
4. KMP

—,BF算法 
BF(Brute Force)算法又称为暴力匹配算法,是普通模式匹配算法。

其算法思想很简单,从主串S的第pos个字符开始,和模式串T的第一个字符进行比较,若相等,则主串和模式串都后移一个字符继续比较;若不相同,则回溯到主串S的第pos+1个字符重新开始比较。 
依次类推,直到模式串T中每个字符依次和主串S中的一个连续字符串全部相等时,则匹配成功,返回模式串T的第一个字符在主串S中的位置;若主串遍历完也没有成功,则匹配失败。

算法步骤如下:

下标i    0  1  2  3  4  5  6  7  8  9  
主串S a b a b c a b c a c
模式串T a b c a
  • 1
  • 2
  • 3
  • 1
  • 2
  • 3

第一次比较,从左到右,S[0] = T[0],计数器++;比较S[1] = T[1],i++;当s[2] != T[2],主串回溯,从S[1]重新开始比较。

下标i    0  1  2  3  4  5  6  7  8  9  
主串S a b a b b a b c a c
模式串T a b c a
  • 1
  • 2
  • 3
  • 1
  • 2
  • 3

也就是说,主串i从0开始,每次比较失败i++,重新比较,直到

下标i    0  1  2  3  4  5  6  7  8  9  
主串S a b a b b a b c a c
模式串T a b c a
  • 1
  • 2
  • 3
  • 1
  • 2
  • 3

i = 5,匹配成功。返回 i=5。

可推得,BF算法在最坏情况下需要比较,主串长度M 乘以 模式串长度N, 为-O(M * N)。

代码实现如下:

int BF(const char *str1, const char *str2)
{
int str1_len = strlen(str1);
int str2_len = strlen(str2);
int i = 0;
int j = 0;

if(str1 == NULL || str2 == NULL){
return -1;
}

while(i < str1_len && j < str2_len){
if(str1[i] == str2[j]){
i++;
j++;
//相等则继续逐个比较
}
else{
i = i -j + 1;
j = 0;
//不相等则主串回溯,重新比较
}
}
if (j == str2_len){

return i - j;
}else{
return -1;
}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

BF算法简单易懂,但是这个算法效率很差,原因在于每次失败后回溯,浪费了之前的比较,导致了很多次的无用比较,时间损耗较大。

二,BM算法 
BM(Boyer Moore)算法是1977年,Robert S.Boyer和J Strother Moore提出了一种在O(n)时间复杂度的匹配算法。时间复杂度要低于BF。

BM算法之所以能够在模式匹配中有更高的的效率,主要是因为BM算法构造了两个跳转表,分别叫做 坏后缀表 ,和 好后缀表 。这两个表涉及了BM算法中的两个规则:

坏字符规则:当文本串中的某个字符跟模式串的某个字符不匹配时,我们称文本串中的这个失配字符为坏字符,此时模式串需要向右移动,移动的位数 = 坏字符在模式串中的位置 - 坏字符在模式串中最右出现的位置。此外,如果”坏字符”不包含在模式串之中,则最右出现位置为-1。

好后缀规则:当字符失配时,后移位数 = 好后缀在模式串中的位置 - 好后缀在模式串上一次出现的位置,且如果好后缀在模式串中没有再次出现,则为-1。

算法步骤如下: 
1. 首先,”文本串”与”模式串”头部对齐,从尾部开始比较。”S”与”E”不匹配。这时,”S”就被称为”坏字符”(bad character),即不匹配的字符,它对应着模式串的第6位。且”S”不包含在模式串”EXAMPLE”之中(相当于最右出现位置是-1),这意味着可以把模式串后移6-(-1)=7位,从而直接移到”S”的后一位。 
iptables --algo 字符串匹配算法 bm kmp 
2. 依然从尾部开始比较,发现”P”与”E”不匹配,所以”P”是”坏字符”。但是,”P”包含在模式串”EXAMPLE”之中。因为“P”这个“坏字符”对应着模式串的第6位(从0开始编号),且在模式串中的最右出现位置为4,所以,将模式串后移6-4=2位,两个”P”对齐。 
iptables --algo 字符串匹配算法 bm kmp 
3. 依次比较,得到 “MPLE”匹配,称为”好后缀”(good suffix),即所有尾部匹配的字符串。注意,”MPLE”、”PLE”、”LE”、”E”都是好后缀。 
iptables --algo 字符串匹配算法 bm kmp
4. 发现“I”与“A”不匹配:“I”是坏字符。如果是根据坏字符规则,此时模式串应该后移2-(-1)=3位。问题是,有没有更优的移法? 
iptables --algo 字符串匹配算法 bm kmp 
5. 更优的移法是利用好后缀规则:当字符失配时,后移位数 = 好后缀在模式串中的位置 - 好后缀在模式串中上一次出现的位置,且如果好后缀在模式串中没有再次出现,则为-1。 
所有的“好后缀”(MPLE、PLE、LE、E)之中,只有“E”在“EXAMPLE”的头部出现,所以后移6-0=6位。 
可以看出,“坏字符规则”只能移3位,“好后缀规则”可以移6位。每次后移这两个规则之中的较大值。这两个规则的移动位数,只与模式串有关,与原文本串无关。 
iptables --algo 字符串匹配算法 bm kmp 
6. 继续从尾部开始比较,“P”与“E”不匹配,因此“P”是“坏字符”,根据“坏字符规则”,后移 6 - 4 = 2位。因为是最后一位就失配,尚未获得好后缀。 
iptables --algo 字符串匹配算法 bm kmp 
匹配完成,可见BM算法根据好坏字符规则,使得失配时,文本串能够后移更多位,使得效率高于BF按部就班的匹配。

BM算法的时间复杂度为-O(N)。

代码实现主要在于构建两表。 
坏字符表:

void BuildBadC(const char* pattern, size_t pattern_length, unsigned int* badc, size_t alphabet_size)  
{
unsigned int i;

for(i = 0; i < alphabet_size; ++i)
{
badc[i] = pattern_length;
}
for(i = 0; i < pattern_length; ++i)
{
badc[pattern[i] - 'A'] = pattern_length - 1 - i;
}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

好后缀表:

void BuildGoodS(const char* pattern, size_t pattern_length, unsigned int* goods)  
{
unsigned int i, j, c;

for(i = 0; i < pattern_length - 1; ++i)
{
goods[i] = pattern_length;
}
//初始化pattern最末元素的好后缀值
goods[pattern_length - 1] = 1;
//此循环找出pattern中各元素的pre值,这里goods数组先当作pre数组使用
for(i = pattern_length -1, c = 0; i != 0; --i)
{
for(j = 0; j < i; ++j)
{
if(memcmp(pattern + i, pattern + j, (pattern_length - i) * sizeof(char)) == 0)
{
if(j == 0)
{
c = pattern_length - i;
}
else
{
if(pattern[i - 1] != pattern[j - 1])
{
goods[i - 1] = j - 1;
}
}
}
}
}
//根据pattern中个元素的pre值,计算goods值
for(i = 0; i < pattern_length - 1; ++i)
{
if(goods[i] != pattern_length)
{
goods[i] = pattern_length - 1 - goods[i];
}
else
{
goods[i] = pattern_length - 1 - i + goods[i];

if(c != 0 && pattern_length - 1 - i >= c)
{
goods[i] -= c;
}
}
}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49

构建完表BM算法就很简单了。

unsigned int BM(const char* text, size_t text_length, const char* pattern, size_t pattern_length, unsigned int* matches)  
{
unsigned int i, j, m;
unsigned int badc[ALPHABET_SIZE];
unsigned int goods[pattern_length];
i = j = pattern_length - 1;
m = 0;

//构建好后缀和坏字符表
BuildBadC(pattern, pattern_length, badc, ALPHABET_SIZE);
BuildGoodS(pattern, pattern_length, goods);

while(j < text_length)
{
//发现目标传与模式传从后向前第1个不匹配的位置
while((i != 0) && (pattern[i] == text[j]))
{
--i;
--j;
}
//找到一个匹配的情况
if(i == 0 && pattern[i] == text[j])
{
matches[m++] = j;
j += goods[0];
}
else
{
//坏字符表用字典构建比较合适
j += goods[i] > badc[text[j]-'A'] ? goods[i] : badc[text[j]-'A'];
}
i = pattern_length - 1;
}

return m;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36

BM算法的思想在字符串匹配中很重要,其中好后缀与KMP算法的思想不谋而合,而坏字符跳跃,跟Sunday算法很相似。总的来说,BM是很高效的匹配算法。

三,Sunday算法 
Sunday算法是Daniel M.Sunday于1990年提出的字符串模式匹配。据网上说,Sunda算法的效率高于BM和KMP(不太明白)。在我看来,Sunday算法是BM算法的优化,逻辑简单易懂,代码也实现更容易(无需构造两表)。

Sunday算法的思想是: 
1. 从文本串S的第pos个字符开始,和模式串T的第一个字符进行比较,若相等,则主串和模式串都后移一个字符继续比较; 
2. 若不相同,则将文本串参与匹配的最末位字符的后一个字符与模式串逆着匹配。 
3. 若匹配完模式串没有该字符,则模式串直接跳过,即移动位数 = 匹配串长度 + 1。 
4. 若模式串匹配到了该字符,则模式串中相同字符移动到文本串该字符下,与该字符对齐。其移动位数 = 模式串中最右端的该字符到末尾的距离+1。

算法步骤如下:

下标i    0  1  2  3  4  5  6  7  8  9  10  11  12
主串S c b a b d c b a c b b a d
模式串T c b b a
  • 1
  • 2
  • 3
  • 1
  • 2
  • 3

从前往后比较,在i = 2处失配,关注i= 4( d )是否包含在模式串T中。遍历比较完发现不包含,将模式T移动到i = 5继续比较。(失配后,主串这轮参与比较的后一位(d)肯定要参与下一轮的比较,T中都没有d,肯定匹配不成功啊!还比什么,直接后移至(d)的下一位。)

下标i    0  1  2  3  4  5  6  7  8  9  10  11  12
主串S c b a b d c b a c b b a d
模式串T c b b a
  • 1
  • 2
  • 3
  • 1
  • 2
  • 3

在i = 7处失配,关注i = 9(b),在模式串中找b,发现i = 6, i = 7处都有b,那应该和谁对齐?? 应该和后面的(i = 7)处的对齐,这就是为什么要倒着在模式串中找b了,找到了直接break,并将此处与i = 9对齐。(为什么和后面的b对齐,大家思考)

下标i    0  1  2  3  4  5  6  7  8  9  10  11  12
主串S c b a b d c b a c b b a d
模式串T c b b a
  • 1
  • 2
  • 3
  • 1
  • 2
  • 3

在i=7处失配,关注i=11(a),匹配到模式串中最后一位为a,break;将模式串中的a与i = 17 处的 a 对齐。继续比较。

下标i    0  1  2  3  4  5  6  7  8  9  10  11  12
主串S c b a b d c b a c b b a d
模式串T c b b a
  • 1
  • 2
  • 3
  • 1
  • 2
  • 3

匹配完成!

可见Sunday算法的核心思想就是失配时,模式串能尽可能多的向后移动,使得匹配次数减少,效率提高。

Sunday和BM不同点在于: 
1. BM从后往前匹配,Sunday从前往后。 
2. BM算法失配关注的是“最后一位”,Sunday关注的是“最后一位的下一位”。 
3. BM有坏字符串好字符串之分,Sunday没有。(但思想比较相似,BM中的好字符 和 坏字符包含在模式串内,可以类比于Sunday算法找到了该字符;好字符和坏字符串没出现,则类比于没在模式串中找到该字符)。

代码实现:

int Sunday(const char *str1, const char *str2)
{
int str1_len = strlen(str1);
int str2_len = strlen(str2);
int i = 0;
int j = 0;
enum{FALSE,TRUE};
int Y = FALSE;

if(str1 == NULL || str2 == NULL){
return -1;
}

while(i < str1_len && j < str2_len){
if(str1[i] == str2[j]){
i++;
j++;
}else{
//关注最后一位的后一位这个字符
int num = i - j + str2_len ;
for(j = str2_len-1; j >= 0; j--){
//该字符与模式串比较,找到相同的则与该字符对齐。
if(str1[num] == str2[j]){
i = num - j;
Y = TRUE;
break;
}
}
if(Y == FALSE){
//没找到模式串就直接跳到该字符的下一位。
i = num + 1;
}
Y = FALSE;
j = 0;
}
}
if(i == str1_len){
return -1;
}else
return i - str2_len;;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41

Sunday算法的应用价值很强,(实际效率高于KMP和BM算法),代码实现也很简单,希望大家能够掌握。

四,KMP算法 
Knuth-Morris-Pratt 字符串查找算法,简称为 “KMP算法”由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表,故取这3人的姓氏命名此算法。 
KMP算法在网上说的非常麻烦,我觉得就是之前介绍的类似于BM算法的好字符后缀匹配规则,和next[]数组的推导两点而已。

算法的思想是:假设现在文本串S匹配到 i 位置,模式串P匹配到 j 位置如果j = -1(标记),或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++,继续匹配下一个字符; 
如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]。意味失配时,模式串P相对于文本串S向右移动了j - next [j] 位。换言之,当匹配失败时,模式串向右移动的位数为:失配字符所在位置 - 失配字符对应的next 值。即移动的实际位数为:j - next[j],且此值大于等于1。

Next数组的值含义是:代表失配前的字符串中,有多大长度的相同的前缀后缀。比如Next[j] = k;表示 j 之前的字符串中有最大长度为k 的相同前缀后缀。 
此也意味着在某个字符失配时,该字符对应的next 值会告诉你下一步匹配中,模式串应该跳到j-Next[j]这个位置上。所以重点在于求Next[]。

如下: 
ABCDAB ABCDABC ABCDABCDABDABD 文本串 
ABCDABD 模式串

最大前缀后缀相同数:

  A               左                         右                     
AB A B 0
ABC A,AB C,BC 0
ABCD A,AB,ABC D,CD,BCD 0
ABCDA A,AB,ABC,ABCD A,DA,CDA,BCDA 1
ABCDAB A,AB,ABC,ABCD,ABCDA B,AB,DAB,CDAB,BCDAB 2
ABCDABD A,AB,ABC,ABCD,ABCDA,ABCDAB D,BD,ABD,DABD,CDABD,BCDABD 0

最大前缀后缀公共元素长度对照表
A B C D A B D
0 0 0 0 1 2 0

Next 数组考虑的是除当前字符外的最长相同前缀后缀,所以通过上步骤求得各个前缀后缀的公共元素的最大长度后,只要稍作变形即可:将第求得的值整体右移一位,然后初值赋为-1,如下表格所示:

 A   B   C   D   A   B   D 
-1 0 0 0 0 1 2

在匹配失配时,只需要用失配位置 j 减去 Next[j],就可以得到模式串移动到什么位置了。

Next[]的求取代码实现如下:

int *get_next(const char* str2)
{
int str2_len = strlen(str2);
int *next = (int *)malloc(sizeof(int)*str2_len);
next[0] = -1;
int left = -1;
int right = 0;

while(right < str2_len - 1){
if(left == -1 || str2[left] == str2[right]){
left++;
right++;
next[right] = left;
}else
left = next[left];
}
return next;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

这段代码是为了求取Next[]对应的值,并没有什么实际意思,能得出正确的Next[]就行(求Next[]的值,网上好像就这一种代码实现办法)。

       0   1   2   3   4   5   6 
next -1 0 0 0 0 1 2
  • 1
  • 2
  • 1
  • 2

我们来根据代码验证下是否准确 
str_len - 1~6 
left = -1 
right = 0 
——————————————

       0   1   2   3   4   5   6 
next -1 0

left = 0
right = 1
next[1] = 0
--------------------------------------------
ABCDABD
right = 1
left = next[0] = -1
--------------------------------------------
left = 0
right = 2
next[2] = 0
0 1 2 3 4 5 6
next -1 0 0

可以看出是正确的(后来的就不用推演了),代码设计的很巧妙,能恰好算出Next[]所对应的值。(这段代码不需理解,记住就行,就是为了求Next[]而专门设计的算法)。

求出Next[]的对应值,KMP算法代码就很容易了。

int KMP(const char* str1, const char* str2)
{
int str1_len = strlen(str1);
int str2_len = strlen(str2);
int *next = get_next(str2);
int i = 0;
int j = 0;

if(str1 == NULL || str2 == NULL){
return -1;
}
while(i < str1_len && j < str2_len){
if(j == -1 || str1[i] == str2[j]){
i++;
j++;
}else{
//关键一步,失配时根据Next[]跳转
j = next[j];
}
}
free(next);
if(j == str2_len){
return (i-str2_len);
}
return -1;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

KMP的时间复杂度: 
我们发现如果某个字符匹配成功,模式串首字符的位置保持不动,仅仅是i++、j++;如果匹配失配,i 不变(即 i 不回溯),模式串会跳过匹配过的next [j]个字符。整个算法最坏的情况是,当模式串首字符位于i - j的位置时才匹配成功,算法结束。 
所以,如果文本串的长度为n,模式串的长度为m,那么匹配过程的时间复杂度为-O(n),算上计算next的-O(m)时间,KMP的整体时间复杂度为-O(m + n)。

四种经典的字符串匹配算法介绍完毕,大家在纸上多画多算,能更好的理解算法思想。