资源预览内容
第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
第9页 / 共9页
亲,该文档总共9页全部预览完了,如果喜欢就下载吧!
资源描述
算法作业三种模式匹配算法051073 闵洪波 作业要求:分别用 KMP、MonteCarlo、LasVegs 算法编制三个程序,随机生成不小于5000 对长度不等的 01 串(三个程序使用相同的串),然后统计算法的执行时间和MonteCarlo算法的出错比率,并根据运行结果 对三种算法进行深入的比较。1、算法思路KMP 算法的主要特点是指向主串的指针不需要回溯,只向右移动,即模式串在与主串失配时,并不 回溯主串的指针与模式串重新匹配,而是根据已经得到的匹配信息将模式串尽可能远的向右滑动一段。滑 动距离的大小取决于模式串的失效函数next, nextk (Ov=kv=m-1)的值表示当模式串在下标为k的字符处 与主串失配时应该向右移动到下标为nextk的字符处再与主串重新匹配。算法首先要求模式串的失效函数 next,然后再根据next的值进行模式匹配,在最坏情况下的时间复杂度为O (m*n), m为模式串的长度, n为主串的长度,当如果模式串中有较多相同的字符时,时间复杂度一般可达到O (m+n)。MonteCarlo随机算法主要是通过比较模式串和主串中与模式串等长的串的“指纹”来匹配的,若两者 指纹相等,则可以认为在概率意义下两者是相等的,算法中要求用到一个随机产生的素数作模运算,该素 数的选取直接影响了算法的准确率,算法的时间复杂度为O (m+n)。但有一定的出错率,即选取主串中比 较串的指纹与模式串相等时但比较串与模式串并不相等,理论上这种情况出现的概率为1/n,只与主串的 长度有关,与模式串的长度无关,但实际上只要选取素数合适出错率比1/n要小的多。LasVegas算法是对MonteCarlo算法的改进,当模式串的指纹与主串中的比较串相等时,此时并不直 接返回匹配的位置,而是判断两个字符串是否真的相等,相等则返回,否则继续匹配。所以,该算法总能 得到正确的位置,但算法的执行时间稍微比MonteCarlo算法要长一点(判断字符串是否相等的耗费),时 间复杂度的期望值不超过O(m+n)。要完成上述三个模式匹配算法的比较,需要一个0/1 串的随机发生器和一个素数发生器。程序中头文 件”randstr.h”包含的RandomString类是用来产生MAXSIZE对的主串和模式串的,0/1串的长度和内容都是 随机的,为了便于比较,规定主串的长度一定大于模式串的长度。”random.h”包含的Random类封装了产 生随机数的函数。素数发生器首先产生MAXSIZE个随机数保存在prime数组中,供随机算法使用。本程 序中随机生成了 10000对0/1串作为测试数据,即MAXSIZE=10000。”defs.h”定义了所用的常量。2、算法分析和比较运行 PatternMatching 可以发现:1) 三个算法运行的时间处于同一数量级的,其中在大多数情况下 MonteCarlo 的算法都要快于 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) 的对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 算法的执行时 间几乎相等。这也是比较容易理解的,模式串很短意味着它与主串匹配成功的可能性就大,算法不需 要从头到尾扫描一遍主串就可以在主串的较前面找到匹配串的位置,此外,模式串的长度小则说明耗费在扫描一遍模式串的时间就短,因此执行算法所花费的时间就少得多,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算法的 出错率达到了 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 算法的出错率很小,几乎接近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#include 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, int 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输出:模式串在主串第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 = 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)
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号