《三种模式匹配算法的比较和分析》由会员分享，可在线阅读，更多相关《三种模式匹配算法的比较和分析（9页珍藏版）》请在金锄头文库上搜索。
1、算法作业三种模式匹配算法051073 闵洪波 作业要求：分别用 KMP、MonteCarlo、LasVegs 算法编制三个程序，随机生成不小于5000 对长度不等的 01 串(三个程序使用相同的串)，然后统计算法的执行时间和MonteCarlo算法的出错比率，并根据运行结果 对三种算法进行深入的比较。1、算法思路KMP 算法的主要特点是指向主串的指针不需要回溯，只向右移动，即模式串在与主串失配时，并不 回溯主串的指针与模式串重新匹配，而是根据已经得到的匹配信息将模式串尽可能远的向右滑动一段。滑 动距离的大小取决于模式串的失效函数next, nextk (Ov=kv=m-1)的值表示当模式串在下
2、标为k的字符处 与主串失配时应该向右移动到下标为nextk的字符处再与主串重新匹配。算法首先要求模式串的失效函数 next，然后再根据next的值进行模式匹配，在最坏情况下的时间复杂度为O (m*n), m为模式串的长度， n为主串的长度，当如果模式串中有较多相同的字符时，时间复杂度一般可达到O (m+n)。MonteCarlo随机算法主要是通过比较模式串和主串中与模式串等长的串的“指纹”来匹配的，若两者 指纹相等，则可以认为在概率意义下两者是相等的，算法中要求用到一个随机产生的素数作模运算，该素 数的选取直接影响了算法的准确率，算法的时间复杂度为O (m+n)。但有一定的出错率，即选取主串中
3、比 较串的指纹与模式串相等时但比较串与模式串并不相等，理论上这种情况出现的概率为1/n,只与主串的 长度有关，与模式串的长度无关，但实际上只要选取素数合适出错率比1/n要小的多。LasVegas算法是对MonteCarlo算法的改进，当模式串的指纹与主串中的比较串相等时，此时并不直 接返回匹配的位置，而是判断两个字符串是否真的相等，相等则返回，否则继续匹配。所以，该算法总能 得到正确的位置，但算法的执行时间稍微比MonteCarlo算法要长一点(判断字符串是否相等的耗费)，时 间复杂度的期望值不超过O(m+n)。要完成上述三个模式匹配算法的比较，需要一个0/1 串的随机发生器和一个素数发生器。
4、程序中头文 件”randstr.h”包含的RandomString类是用来产生MAXSIZE对的主串和模式串的，0/1串的长度和内容都是 随机的，为了便于比较，规定主串的长度一定大于模式串的长度。”random.h”包含的Random类封装了产 生随机数的函数。素数发生器首先产生MAXSIZE个随机数保存在prime数组中，供随机算法使用。本程 序中随机生成了 10000对0/1串作为测试数据，即MAXSIZE=10000。”defs.h”定义了所用的常量。2、算法分析和比较运行 PatternMatching 可以发现：1) 三个算法运行的时间处于同一数量级的，其中在大多数情况下 Monte
5、Carlo 的算法都要快于 KMP 和 LasVegas算法,从理论上分析MonteCarlo算法的平均时间复杂度优于KMP算法，一般情况MonteCarlo 时间复杂度为O (m+n),而KMP最好情况O (m+n),最坏为O(n*m)。LasVegs要比MonteCarlo稍 微慢一点点，这是预料之中的，因为判断字符串相等耗费了额外的时间。KMP和LasVegs算法的平均 时间复杂度大致相等。2) 随机选取的素数大小直接影响了 MonteCarlo算法的出错率。在模式串不是很长时，当素数大于某个数 时我们可以发现出错率可以降到0。设模式串的最长长度为m，当随机产生的素数p2m时，Y和X(j
6、) 的对p作模运算后的“指纹”Ip都要小于p,此时p不可能可以整除IY - X(j)|，因此不会出现当Ip(X(j) =Ip(y)时却有X(j)Y的误判情况，所以这种情况下MonteCarlo出错率为0。3) 素数一定大时，MonteCarlo算法的出错率比理论值1/n要小的多，即当Ip (X(j) = Ip(y)时却有X(j)Y 的情况很少。相反，当素数很小时，不同 0/1 序列对素数作模运算的结果相同的可能性增大，出错率 相应地变大。4) 当模式串的长度比主串小很多时，三个算法的执行时间明显快了， KMP 和 MonteCarlo 算法的执行时 间几乎相等。这也是比较容易理解的，模式串很短
7、意味着它与主串匹配成功的可能性就大，算法不需 要从头到尾扫描一遍主串就可以在主串的较前面找到匹配串的位置，此外，模式串的长度小则说明耗费在扫描一遍模式串的时间就短，因此执行算法所花费的时间就少得多,KMP时间复杂度接近O（m+n）, 与 MonteCarlo 算法相等。为了更好的说明问题，对 p 的大小和模式串的长度选取了几组不同的测试数据，以下为不同数据的运 行结果（其中m，n分别为主串和模式串的长度，m, n, p都是在给定的区间上随机取值）：1）第一组：素数p2m取m e 1,16, n e m,128 , p e 1,2 m ，从测试结果可以看出MonteCarlo算法的 出错率达到了
8、 20%以上，这是难以接受的。p越小MonteCarlo算法的出错率越大。2）第二组:取m e 1,16, n e m,128 , p e 2,216 ，此时随机选取素数p既有可能小于2m也有可能大于2m ,MonteCarlo算法的出错率只有0.03%.3）第二组：取m e 1,16, n e m,128 , p e 216,232 ，此时随机选取的素数必定大于2m， MonteCarlo算 法的出错率降至0.4）第四组：取m e 1,8, n e m,1024 , p e m2,2 ，KMP算法和MonteCarlo算法每次执行的时间几乎相等，并且 MonteCarlo 算法的出错率很小,
9、几乎接近0。5）第五组：取m e 1,2000, n e m ,2048 , p e 216,232 ，素数p取介于16位机器表示最大整型数和32位机器表示最大整型数之间，此时MonteCarlo算法的出错率为0.07% 1/n3、算法实现代码(程序中MAXSIZE=10000 )文件名：PatternMatching.cpp功能：实现并比较三种模式匹配算法：KMP， MonteCarlo， LasVegas#include random.h#include randstr.h#include defs.h#include #include vfstream#include vtime.h#i
10、nclude vwindows.h#include vstdlib.h#include #include using namespace std;/函数声明 / bool isprime(int n);判断n是否为素数int random_prime( int min, int max );随机产生一个 minmax-1 之间的素数int KMP(char* s, char* t, int position);KMP 算法int getIP(char *x, int len, int prime);获取 x0xlen-1的指纹int MonteCarlo(char* x, char* y, i
11、nt position, int prime);/MonteCarlo 算法int LasVegas(char* x, char* y, int position, int prime); /LasVegas 算法/函数定义 /函数名：isprime功能：测试一个整数是否为素数输出：若n为素数，则返回true;否则falsebool isprime(int n)for(int i = 2; i = min; i-)if(isprime(i) break;return i;/三种模式匹配算法的实现/I、KMP 算法函数名：KMP功能：利用KMP算法匹配模式串输入：主串s和模式串t输出：模式串在主
12、串第pos个字符之后出现的位置int KMP(char* s, char* t, int pos)int i, j;int s_len = (int)strlen(s);int t_len = (int)strlen(t);先求模式串t的nextint *next = new intt_len;i = 0;j = -1;next0 = -1;while(i t_len)if(j = -1 ) i+； j+； nexti = j ; elseif(ti = tj) i+; j+； nexti = j ； else j = nextj;再匹配模式串，求在主串中的位置i = pos - 1 ;j =
13、 0；while(i s_len & j = t_len) return (i - t_len) + 1;else return 0;/II、MonteCarlo 算法函数名：getIP功能：求序列x的指纹输入：01串x,长度len输出：X(i) = xixi+l.xi+len-l mod p 的指纹int getIP(char *x, int len, int p)int ip = 0;for(int k = 0 ; k = len -1; k+)ip = ( 2 * ip + xk - 0) % p;return ip;函数名：MonteCarlo功能：利用随机算法MonteCarlo进行模式匹配输入：主串s和模式串t,随机素数p输出：模式串在主串第pos个字符之后出现的位置int MonteCarlo(char* x, char* y, int pos, int p)
