字符串匹配算法总结
Contents
字符串匹配算法总结
KMP虽然经典,但是理解起来极其复杂,好不容易理解好了,便起码来巨麻烦！
老子就是今天图书馆在写了几个小时才勉强写了一个有bug的、效率不高的KMP,特别是计算next数组的部分。
其实,比KMP算法速度快的算法大把大把,而且理解起来更简单,为何非要抓住KMP呢？笔试出现字符串模式匹配时直接上sunday算法,既简单又高效,何乐而不为？
说实话,想到sunday算法的那个人,绝对是发散思维,绝对牛。当我在被KMP折磨的够呛的时候,我就琢磨,有没有别的好算法呢？？琢磨了半天也没想出个所以然来。笨啊,脑子不够发散。
下面贴上一位兄弟写的算法总结,很简单 (建议KMP部分就不用看了,看了费脑子) 。
参见: http://hi.baidu.com/willamette/blog/item/02bd0b5599c8b4c0b645ae06.html
趁着做Presentation的功夫,顺便做一个总结
字符串匹配:
-willamette
在匹配串中寻找模式串是否出现,注意和最长公共子序列相区别(LCS: Longest Common Substring)
**-: ** Brute Force(BF或蛮力搜索) **算法: **
这是世界上最简单的算法了。
首先将匹配串和模式串左对齐,然后从左向右一个一个进行比较,如果不成功则模式串向右移动一个单位。
速度最慢。
那么,怎么改进呢？
我们注意到Brute Force 算法是每次移动一个单位,一个一个单位移动显然太慢,是不是可以找到一些办法,让每次能够让模式串多移动一些位置呢？
当然是可以的。
我们也注意到,Brute Force 是很不intelligent 的,每次匹配不成功的时候,前面匹配成功的信息都被当作废物丢弃了,当然,就如现在的变废为宝一样,我们也同样可以将前面匹配成功的信息利用起来,极大地减少计算机的处理时间,节省成本。^_^
注意,蛮力搜索算法虽然速度慢,但其很通用,文章最后会有一些更多的关于蛮力搜索的信息。
**-: KMP算法
**
首先介绍的就是KMP 算法。
原始论文: Knuth D.E., Morris J.H., and Pratt V.R., Fast pattern matching in strings, SIAM Journal on Computing, 6(2), 323-350, 1977.
这个算法实在是太有名了,大学上的算法课程除了最笨的Brute Force 算法,然后就介绍了KMP 算法。也难怪,呵呵。谁让Knuth D.E. 这么world famous 呢,不仅拿了图灵奖,而且还写出了计算机界的Bible ( 业内人士一般简称TAOCP). 稍稍提一下,有个叫H.A.Simon 的家伙,不仅拿了Turing Award ,顺手拿了个Nobel Economics Award ,做了AI 的爸爸,还是Chicago Univ 的Politics PhD ,可谓全才。
KMP 的思想是这样的:
利用不匹配字符的前面那一段字符的最长前后缀来尽可能地跳过最大的距离
比如
模式串ababac 这个时候我们发现在c 处不匹配,然后我们看c 前面那串字符串的最大相等前后缀,然后再来移动
下面的两个都是模式串,没有写出来匹配串
原始位置 ababa c
移动之后 aba bac
因为后缀是已经匹配了的,而前缀和后缀是相等的,所以直接把前缀移动到原来后缀处,再从原来的c 处,也就是现在的第二个b 处进行比较。 这就是KMP 。
**-: Horspool算法
**
Horspool 算法。
当然,有市场就有竞争,字符串匹配这么大一个市场,不可能让BF 和KMP 全部占了,于是又出现了几个强劲的对手。
第一个登场的是
论文: Horspool R.N., 1980, Practical fast searching in strings, Software - Practice & Experience, 10(6):501-506
Horspool 算法的思想很简单的。不过有个创新之处就是模式串是从右向左进行比较的。很好很强大,为后来的算法影响很大。
匹配串: abcbc sdxzcxx
模式串: cbcac
这个时候我们从右向左进行对暗号,c-c ,恩对上了,第二个b-a ,不对啊,我们应该怎么办？难道就这么放弃么。于是,模式串从不匹配的那个字符开始从右向左寻找匹配串中不匹配的字符b 的位置,结果发现居然有,赶快对上赶快对上,别耽误了。
匹配串: abcbcsd xzcxx
模式串: cbcac
然后继续从最右边的字符从右向左进行比较。这时候,我们发现了,d-c 不匹配啊,而且模式穿里面没有噢,没办法,只好移动一个模式串长度的单位了。
匹配串: abcbcsdxzcxx
模式串: cbcac
-: Boyer-Moore算法
第二个上来的是Boyer-Moore 算法。
是一个很复杂的算法,当然,虽然理论上时间复杂度和KMP 差不多,但是实际上却比KMP 快数倍,可见实践是检验真理的唯一标准。
原始论文: R.S.Boyer, J.S.Moore, A fast string searching algorithm , Communications of the ACM,20(10):762-772 ,1977
分为两步预处理,第一个是bad-character heuristics ,也就是当出现错误匹配的时候,移位,基本上就是做的Horspool 那一套。
第二个就是good-suffix heuristics ,当出现错误匹配的时候,我还要从不匹配点向左看啊,以前匹配的那段子字符串是不是在模式串本身中还有重复的啊,有重复的话,那么我就直接把重复的那段和匹配串中已经匹配的那一段对齐就是了。再比较
匹配串: abaccba bbazz
模式串: cbadcba
我们看到已经匹配好了cba ,但是c-d 不匹配,这个时候我们发现既可以采用bad-character heuristics ,也可以使用good-suffix heuristics( 模式串: cba dcba ) ,在这种情况下,邪不压正。毅然投奔good 。移动得到
匹配串: abaccbabbaz z
模式串: cbadcba
可是,我们有时候也发现,已经匹配好的那一部分其实并没有再有重复了的啊。这个时候,我们发现已经匹配好的那串字符串有一部分在开头重新出现了,那么,赶快,对齐吧。
匹配串: abacccb bbazz
模式串: cbadccb
然后得到
匹配串: abacccbbbazz
模式串: cbadccb
当两种Good-Suffix 出现的时候,取移动距离最大的那个。
(
对于BM算法,好规则和坏规则,这里讲的不够明确,下面推荐一个讲解非常优秀的文章,可谓图文并茂啊,而且还是个MM写的。
Boyer-Moore 经典单模式匹配算法
http://blog.csdn.net/iJuliet/archive/2009/05/19/4200771.aspx
)
-: Sunday算法
最后一个是Sunday 算法,实际上比Boyer-Moore 还快,呵呵。长江后浪推前浪。
原始论文: Daniel M. Sunday, A very fast substring search algorithm, Communications of the ACM, v.33 n.8, p.132-142, Aug. 1990
看原始论文的题目,D.M. Sunday 貌似是故意想气气Boyer-Moore 两位大牛似的。呵呵。不过实际上的确Sunday 算法的确比BM 算法要快,而且更简单。
Sunday 的算法思想和Horspool 有些相似,但是。当出现不匹配的时候,却不是去找匹配串中不匹配的字符在模式串的位置,而是直接找最右边对齐的右一位的那个字符在模式串的位置。
比如:
匹配串: abcbc zdxzc
模式串: zbcac
恩,这里我们看到b-a 没有对上,我们就看匹配串中的z 在模式串的位置,然后,嘿嘿。
匹配串: abcbczdxzc
模式串: zbcac
如果模式串中的没有那个字符怎么办呢？很简单,跳过去呗。
匹配串: abcbc edxzcs
模式串: zbcac
e 不在模式串中出现
那么我们就
匹配串: abcbcedxzcs
模式串: zbcac
(2009/10/20补充)
RK算法
某一天在图书馆的一本算法分析设计书上翻到的。思路很新颖！和大家分享下。
在串匹配的简单算法中,把文本每m个字符构成的字符段作为一个字段,和模式进行匹配检查。如果能对一个长度为m的字符
串赋以一个Hash函数。那么显然只有那些与模式具有相同hash函数值的文本中的字符串才有可能与模式匹配,这是必要条件
,而没有必要去考虑文本中所有长度为m的字段,因而大大提高了串匹配的速度。因此RK算法的思想和KMP,BM,Sunday等思
路迥然不同！
(事实上,之前的串匹配方法,是将模式串的一个一个字符作为小的特征去分别进行匹配,而RK算法则是将串整体作为一个
特征！难就难在单个字符的特征很容易想得到,整体作为一个特征就没那么容易想得到了)
如果把整体作为一个特征,那么如何快速的求出这个整体特征的特征值？？
模式串的特征值仅需求一次即可。对于文本中的任意m个字符构成的字串如何快速的求特征就是个难点了。
抛砖引玉,这里给出一个简单的特征计算。 将字符串的每一个字符看做一个数,那么这个字符串的就是一个数字数组,通
过积分向量可以快速任意一个长度子字符串的向量和。可以把字符串的对应的字符数组的元素和看做这个字符串整体特征。
这个特征是可以再O (1) 的时间内求出的。其实原始的RK算法里面是把字符串看做一个26进制数在计算特征的。这里就不啰
嗦了,有兴趣的可以深入查找
aabsee sds 模式串 ees
ees
发现 see向量和 == ees的向量和
然后就对see和ees做逐个字符的比较。发现不匹配继续往下走
aabsees ds 模式串 ees
ees
发现 ees向量和 == ees的向量和
然后就对ees和ees做逐个字符的比较。发现匹配OK。
另外还有 字符串匹配自动机 后缀树算法 (分在线和非在线两种) 等 见如下文章。不能说那个比那个更好,各个算法都有自己的优势及最佳应用场合。参考:
http://blog.csdn.net/yifan403/archive/2009/06/16/4272793.aspx
另外,关于多模式字符串匹配 有AC算法 (字符串匹配自动机思想) WM算法 (BM在多模式的推广应用)
参考:
http://blog.csdn.net/ijuliet/category/498465.aspx 该女子的blog有很多好文章。
/******\*华丽分割线*************/
附上sunday代码:
http://hi.baidu.com/kmj0217/blog/item/6f837f2f3da097311e3089cb.html
一种比KMP 和 BM 更高效的匹配算法 (如果想看原英文介绍,看下面分割线后的网址)
适用于: 模式串较短的情况,最坏时间复杂性为O(N*M),不过一般没这么坏
Sunday 算法其实思想跟BM算法很相似,只不过Sunday算法是从前往后匹配,在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符。如果该字符没有在匹配串中出现则直接跳过,即移动步长= 匹配串长度+ 1；否则,同BM算法一样其移动步长=匹配串中最右端的该字符到末尾的距离+1。
代码如下:
/*
Sunday-字符串匹配算法 - 一种优于 KMP 的算法
思想类似于BM 算法,只不过是从左向右匹配
遇到不匹配的看大串中匹配范围之外的右侧第一个字符在小串中的最右位置
另外: 采用BM/KMP 的预处理的做法,事先计算好移动步长 ,等到遇到不匹配的值直接使用
*/
#include<iostream>
#include<string.h>
using namespace std;
//一个字符8位 最大256种
#define MAX_CHAR_SIZE 256
/*设定每个字符最右移动步长,保存每个字符的移动步长
如果大串中匹配字符的右侧一个字符没在子串中,大串移动步长= 整个串的距离 +1
如果大串中匹配范围内的右侧一个字符在子串中,大串移动距离= 子串长度 - 这个字符在子串中的位置
*/
int *setCharStep(char *subStr)
{
int *charStep=new int[MAX_CHAR_SIZE];
int subStrLen=strlen(subStr);
for(int i=0;i<MAX_CHAR_SIZE;i++)
charStep[i]=subStrLen+1;
//从左向右扫描一遍 保存子串中每个字符所需移动步长
for(int i=0;i<subStrLen;i++)
{
charStep[(unsigned char)subStr[i] ]=subStrLen-i;
}
return charStep;
}
/*
算法核心思想,从左向右匹配,遇到不匹配的看大串中匹配范围之外的右侧第一个字符在小串中的最右位置
根据事先计算好的移动步长移动大串指针,直到匹配
*/
int sundaySearch(char *mainStr,char *subStr,int *charStep)
{
int mainStrLen=strlen(mainStr);
int subStrLen=strlen(subStr);
int main_i=0;
int sub_j=0;
while(main_i<mainStrLen)
{
//保存大串每次开始匹配的起始位置,便于移动指针
int tem=main_i;
while(sub_j<subStrLen)
{
if(mainStr[main_i] == subStr[sub_j])
{
main_i++;
sub_j++;
continue;
}
else{
//如果匹配范围外已经找不到右侧第一个字符,则匹配失败
if(tem+subStrLen > mainStrLen)
return -1;
//否则 移动步长 重新匹配
char firstRightChar=mainStr[tem+subStrLen];
main_i =tem + charStep[(unsigned char)firstRightChar];
sub_j=0;
break;//退出本次失败匹配 重新一轮匹配
}
}
if(sub_j == subStrLen)
return main_i-subStrLen;
}
return -1;
}
int main()
{
char *mainStr="absaddsasfasdfasdf";
char *subStr="dd";
int *charStep=setCharStep(subStr);
cout<<"位置: "<<sundaySearch(mainStr,subStr,charStep)<<endl;
system("pause");
return 0;
}
/*************************************************华丽的分割线***************************************/
算法介绍以及实现伪码: http://www-igm.univ-mlv.fr/~lecroq/string/node19.html
void preQsBc(char *x, int m, int qsBc[]) {
int i;
for (i = 0; i < ASIZE; ++i)
qsBc[i] = m + 1; for (i = 0; i < m; ++i) qsBc[x[i]] = m - i; }
void QS(char *x, int m, char *y, int n) {
int j, qsBc[ASIZE];
/* Preprocessing */
preQsBc(x, m, qsBc);
/* Searching */
j = 0; while (j <= n - m) { if (memcmp(x, y + j, m) == 0) OUTPUT(j); j += qsBc[y[j + m]]; /* shift */ } }
// 第三个代码实现,貌似比较高效
http://hi.baidu.com/azuryy/blog/item/10d3d3460b97af0e6b63e5cd.html 头文件定义: /* Sunday.h */ class Sunday { public: Sunday(); ~Sunday();
public:
int find(const char* pattern, const char* text);
private:
void preCompute(const char* pattern);
private:
//Let’s assume all characters are all ASCII static const int ASSIZE = 128; int _td[ASSIZE] ; int _patLength; int _textLength; };
源文件
/* Sunday.cpp */
Sunday::Sunday()
{ }
Sunday::~Sunday()
{ }
void Sunday::preCompute(const char* pattern)
{ for(int i = 0; i < ASSIZE; i++ ) _td[i] = _patLength + 1;
const char* p;
for ( p = pattern; *p; p++) _td[*p] = _patLength - (p - pattern); }
int Sunday::find(const char* pattern, const char* text)
{ _patLength = strlen( pattern ); _textLength = strlen( text );
if ( _patLength <= 0 || _textLength <= 0)
return -1;
preCompute( pattern );
const char *t, *p, *tx = text;
while (tx + _patLength <= text + _textLength)
{ for (p = pattern, t = tx; *p; ++p, ++t) { if (*p != *t) break; } if (*p == 0) return tx-text; tx += _td[tx[_patLength]]; } return -1; }
简单测试下:
int main()
{
char* text = “blog.csdn,blog.net”; char* pattern = “csdn,blog” ; Sunday sunday;
printf("The First Occurence at: %d/n",sunday.find(pattern,text));
return 1;
}
////////////////////////////////////////////
strstr的实现。 需要说明的是strstr是c语言提供的使用Brute Force实现的字符串匹配,简单、通用是其最大的优点。时间复杂度是O(mn) // 下面是Microsoft的实现 //经典算法 //比KMP算法简单,没有KMP算法高效 char * __cdecl strstr ( const char * str1, const char * str2 ) { char *cp = (char *) str1; char *s1, *s2; if ( !*str2 ) return((char *)str1); while (*cp) { s1 = cp; s2 = (char *) str2; while ( *s1 && *s2 && !(*s1-*s2) ) s1++, s2++; if (!*s2) return(cp); cp++; } return(NULL); }
http://blog.csdn.net/whoismickey/archive/2009/02/08/3869367.aspx
strstr
glibc里的strstr函数用的是brute-force(naive)算法,它与其它算法的区别是strstr不对pattern(needle)进行预处理,所以用起来很方便。理论复杂度O
(mn), 实际上,平均复杂度为O(n), 大部分情况下高度优化的算法性能要优于基于自动机的匹配算法,关于串匹配算法可参考http://www-igm.univ-mlv.fr/~lecroq/string/ 。 glibc中使用了 (1) Stephen R. van den Berg的实现,在他的基础上, (2) Tor Myklebust http://sources.redhat.com/ml/libc-alpha/2006-07/msg00028.html 给出了更复杂的实现,当然也更高效。
BF有一个重要性质是事先不用知道串的长度,而基于跳跃的算法是需要用字符串长度来判断结束位置的。如何快速的确定字符串结束位置,可参考http://www.cppblog.com/ant/archive/2007/10/12/32886.html ,写的很仔细。
将两种思想结合起来,可以做出更快的strstr (3) 。约定 (1) 为strstrBerg; (2) 为strstrBergo, (3) 为lstrstr, (4) 为glibc中的strstr,简单测试了一下:
从长度为2k的文本中查找长度为1、2、9的模式串,结果如下
1 2 9
(1) 0.000006 0.000006 0.000012
(2) 0.000007 0.000004 0.000008
(3) 0.000002 0.000002 0.000005
(4) 0.000005 0.000005 0.000011
下载strstr和测试程序 , 下载后执行 : unzip testStrstr.zip cd testStrstr make test
基于sse2的strstr函数 是用sse2指令集对strstr的优化
Author lcf
LastMod 2012-11-27