穷举法又叫暴力法。大多数程序员眼里,它是幼稚的,但大师们不这么认为。
Rob Pike, 最伟大的C 语言大师之一, 在《Notes on C Programming》中阐述了一个原则:花哨的算法比简单算法更容易出bug、更难实现,尽量使用简单的算法配合简单的数据结构。而Ken Thompson——Unix 最初版本的设计者和实现者,禅宗偈语般地对Pike 的这一原则作了强调:拿不准就穷举(When in doubt , use brute force)。而对于装13爱好者来说,更是自豪的称其使用的是BF算法。
穷举法用在字符串匹配上,简单的描述就是,检查文本从0到n-m的每一个位置,看看从这个位置开始是否与模式匹配。这种方法还是有一些优点的,如:不需要预处理过程,需要的额外空间为常数,每一趟比较时可以以任意顺序进行。
尽管它的时间复杂度为O(mn),例如在文本"aaaaaaaaaaaaaaaaaaaaaaaaaaa"中寻找"aaaaab"时,就完全体现出来了。但是算法的期望值却是2n,这表明该算法在实际应用中效率不低。
C代码如下:
-
voidBF(char*x,intm,char*y,intn){
-
inti,j;
-
-
for(j=0;j<=n-m;++j){
-
for(i=0;i<m&&x[i]==y[i+j];++i);
-
if(i>=m)
- OUTPUT(j);
- }
- }
如果我们注意到C库函数是汇编优化过的,并通常能提供比C代码更高的性能的话,我们可以用memcmp来完成每一趟比较过程,从而达到更好的性能:
-
#defineEOS'\0'
-
voidBF(char*x,intm,char*y,intn){
-
char*yb;
-
-
for(yb=y;*y!=EOS;++y)
-
if(memcmp(x,y,m)==0)
- OUTPUT(y-yb);
- }
自动机的方法其实和穷举法有点相似,都是用最简单直白的方式来做事情。区别在于穷举法是在计算,而自动机则是查表。尽管自动机的构造过程有一点点难解,要涉及到DFA的理论,但是自动机的比较过程那绝对是简单到无语。
简单说来,根据模式串,画好了一张大的表格,表格m+1行σ列,这里σ表示字母表的大小。表格每一行表示一种状态,状态数比模式长度多1。一开始的状态是0,也就是处在表格的第0行,这一行的每个元素指示了当遇到某字符时就跳转到另一个状态。每当跳转到最终状态时,表示找到了一个匹配。
语言表述起来还是比较啰嗦,看代码就知道了:
-
#defineASIZE256
-
intpreAut(constchar*x,intm,int*aut){
-
inti,state,target,old;
-
for(state=0,i=0;i<m;++i){
- target=i+1;
- old=aut[state*ASIZE+x[i]];
- aut[state*ASIZE+x[i]]=target;
-
memcpy(aut+target*ASIZE,aut+old*ASIZE,ASIZE*sizeof(int));
- state=target;
- }
-
returnstate;
- }
-
voidAUT(constchar*x,intm,constchar*y,intn){
-
intj,state;
-
-
int*aut=(int*)calloc((m+1)*ASIZE,sizeof(int));
-
intTerminal=preAut(x,m,aut);
-
-
for(state=0,j=0;j<n;++j){
- state=aut[state*ASIZE+y[j]];
-
if(state==Terminal)
- OUTPUT(j-m+1);
- }
- }
(注:原文的代码使用一个有向图的数据结构,我遵循大师的指引,改用了更简单一点的数组)
从代码上我们很容易看出,自动机的构造需要时间是O(mσ),空间也是O(mσ)(严格来说这份代码使用了O((m+1)σ)),但是一旦构造完毕,接下来匹配的时间则是O(n)。
匹配的过程前面已经说了,太简单了没什么好说的,这里就解释一下构造过程吧!
我们构造的目标是对应模式长度,构造出同样多的状态,用0表示初始状态,然后第一个字符用状态1表示,第二个用状态2表示,依次类推,直到最后一个字符,用m表示,也是最终状态。
一开始,数组全都置0,,这个时候的自动机遇到任何字符都转到初始状态。然后给它看模式的第一个字符,假设这是'a'吧,告诉它,状态0遇到'a'应该到一个新的状态——状态1,所以把第0行的第'a'列修改为1。而这个时候状态1还是空白的,怎么办呢?
这时候状态0就想呀,在我被告知遇到'a'要去状态1之前,我原本遇到'a'都要去状态0的,也就是修改之前第'a'列所指的那个状态,称为old状态吧;而现在我遇到'a'却要去一个新的状态,既然以前old状态能处理遇到'a'之后的事情,那么我让新的状态像old状态一样就好了。于是状态0把old状态拷贝到状态1。
现在轮到状态1了,给它看第二个字符,它也如法炮制,指向了状态2,又把old状态拷贝给了状态2。
于是,状态机就在这种代代传承的过程中构造完毕了。
虽然理论上自动机是最完美的匹配方式,但是由于预处理的消耗过大,实践中,主要还是用于正则表达式。
结语:穷举法与自动机各自走了两个极端,因此都没能达到综合性能的最佳,本文之后介绍的算法,可以看成是在穷举和自动机两者之间取舍权衡的结果。
分享到:
相关推荐
字符串匹配算法:穷举、KMP、BM.ppt
简单介绍了字符串匹配相关算法,如穷举、KMP、BM,做个大致的了解
穷举算法经典案例及其C语言实现.穷举算法经典案例及其C语言实现.
穷举算法讲义穷举算法讲义.doc
MIMO天线选择算法中,基于最优选择算法和范数选择算法和随机选择算法的程序,能够简化硬件结构,降低通信算法的复杂度,提高通信的可靠性。穷举法,递减,递增等。
MATLAB优化算法案例分析与应用(进阶篇)1-10章程序下载
ACM培训时候的穷举算法详解PPT 包括一些穷举的思想和例题
Simulated Annealing Algorithm and Exhaustive Approach to Optimize shuttle routes (Travel Salesman Problem) using MATLAB programming.
用matlab实现的穷尽块匹配算法进行二维运动估计
算法分析与设计课件:穷举法.ppt
算法与程序设计:第2章 穷举法与迭代法.ppt
详细介绍穷举、遗传、变异等算法原理,是科学计算、设计的可靠依据。
选择排序、字符串匹配、穷举查找:包括背包问题和分配问题; 最近对和凸包问题的蛮力算法、深度优先查找和广度优先查找 第4章 插入排序、拓扑排序、计算中值和选择问题 第5章 合并排序、快速排序、大整数乘法 第6章 ...
数据结构与算法_枚举(穷举)算法(视频),Dev-C++语言环境!信息学奥赛基础算法!
穷举法 高精度 动态规划 回溯 贪心 排列组合 排序
结合粒子群算法和穷举法的配电网故障诊断方法.pdf
穷举算法 回溯算法 介绍 几篇文章,还是值得一看的
【老生谈算法】穷举法求解0-1整数规划的matlab程序.txt
穷举密码算法 在许多情况下我们需要穷举组合的算法,比如密码词典。 这个算法的关键是密码...另外本例子中的写文件语句效率比较低,为了降低算法复杂度没有优化。 如果要提高写文件的效率,可以使用缓冲区,分批写入。
用堆栈做的24点程序,里面用到了后缀表达式求值。