三种模式匹配算法的比较和分析

三种模式匹配算法工作要求：使用KMP、MonteCarlo、LasVegs算法创建三个程序，随机生成长度不小于5，000的01列(三个程序使用相同的列)，统计算法的执行时间和MonteCarlo算法的错误比率1 .算法的思路KMP算法的主要特征在于，如果指向主字符串的指针仅向右移动而不需要返回，即模式字符串与主字符串不匹配，则返回的主字符串的指针不与模式字符串重新匹配，而是向已经获得的匹配信息返回滑动距离的大小表示，在图案列的故障函数next，nextk(0=k=m-1 )的值为图案列在下标k的文字中与主列不一致的情况下，向右移动到下标nextk的文字并与主列重合。 算法首先要求模式列的失效函数next，根据next的值进行模式匹配，最坏情况下时间复杂度为O(m*n )，m是模式列的长度，n是主列的长度，当模式列含有很多相同字符时，时间复杂度通常达到O(m n )MonteCarlo随机算法主要通过比较模式列和主列中长度与模式列相等的列的“指纹”来匹配，如果两者的指纹相等，则概率上认为两者相等，算法要求使用随机生成的素数进行模型运算，该素数的但是，即使在选择主列中的比较列的指纹与图案列相等的情况下，比较列不等于图案列的概率理论上为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)3个算法的执行时间处于相同的数级。 其中，蒙特卡罗算法比KMP和LasVegas算法快，理论上分析蒙特卡罗算法的平均时间复杂度优于KMP算法，通常蒙特卡罗时间复杂度为o(mnn )，但在KMP的情况下为o(mnn )，而在KMP的情况下为o(mnn ) LasVegs预计比MonteCarlo慢一点。 因为判断字符串相等需要时间。 KMP和LasVegs算法的平均时间复杂度大致相等。2 )随机选择的素数的大小直接影响蒙特卡罗算法的错误率。 模式列不太长的情况下，像素数比某个个数大时，可知错误率下降到0。 若将图案列的最长设为m，则随机产生的像素数p2m时，将y和X(j )的p模型化的“指纹”Ip小于p，此时，p为|Y X(j)|，因此，在Ip(X(j)=Ip(y )时，不会误判定为X(j)Y，因此，在该情况下montt3 )当素数恒定时，MonteCarlo算法的错误率远小于理论值的1/n，即当Ip(X(j)=Ip(y )时，很少存在X(j)Y。 相反，像素数较小时，不同的0/1序列与对像素数进行模拟运算的结果相同的可能性变高，相应地错误率变大。4 )阵列的长度比主阵列小得多时，3个算法的执行时间明显快，KMP和蒙特卡罗算法的执行时间大致相等。 这也是容易理解的，模式列短意味着与主列的匹配成功的可能性高，算法能够在主列之前找到匹配列的位置，而且，模式列的长度小， 执行算法的时间较少，并且KMP时间的复杂度接近于O(m n )，与MonteCarlo算法等同。为了更好地解释问题，对p的大小和图案列的长度选择一些不同的测试数据，以下显示不同数据的执行结果(其中m、n分别是主列和图案列的长度，m、n、p都是在规定区间内随机取值)。1 )第一组：素数p2m经过测试，发现蒙特卡罗算法的错误率达到20%以上，这是不可接受的。 p越小，蒙特卡罗算法的错误率越大。2 )第二组：此时随机选择的素数p可能小也可能大，蒙特卡罗方法的错误率只有0.03%3 )第三组：取而代之的是，此时随机选择的素数必然大，MonteCarlo算法的错误率下降到04 )第四组： KMP算法和MonteCarlo算法的执行时间大致相同，MonteCarlo算法的错误率小，大致接近0。5 )第五组：取而代之，素数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#include#include#include#include#include使用名称空间STD；一个人，一个人，一个人，一个人，一个人，一个人，一个人，一个人，一个人，一个人，一个人，一个人，一个人，一个人判断bool isprime(int n) /n是否为素数随机生成int random_prime(int min，int max) /1minmax-1之间的素数int KMP(char* s，char* t，int位置)/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位置，int prime) /LasVegas算法一个或多个网站，包括一个或多个网站，包括一个或多个网站/我想要的是/函数名称： isprime/功能：测试整数是否为质数/输出：如果n是素数，则返回true；否则返回falsebool isprime(int n )装模作样for(int i=2； I=sqrt (双精度) n ) I )if(n % i=0)return false；return true；以下称为/函数名称： random_prime/功能：随机生成1个min，max-1区间的素数int random_prime(int min，int max )装模作样int i；srand(int)time(0) )i=rand() % (max - min) min；for (； i=min； i- )if(isprime(i) break；return i；以下称为实现了三种模式匹配算法，包括：/ enterprise matching algority (模式匹配算法)/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； 以下称为else装模作样if(ti=tj) i； j； nexti=j； 以下称为else j=nextj；以下称为以下称为/重新匹配模式列，求出主列中的位置i=pos - 1；j=0；while(i s_len j t_len )装模作样if(j=-1 | si=tj) i； j； /继续比较后续字符else j=nextj； /图案列向右移动/delete next；if(j=t_len) return (i - t_len) 1；else return 0；以下称为/II，蒙特卡罗算法/函数名称： getIP/功能：求出数组x的指纹/输入： 01系列x、长度len输出： X(i)=xixi 1.xi len-1 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；以下称为/函数名称：蒙特卡洛/功能：基于随机算法蒙特卡罗的模式匹配/输入：主列s和图案列t、随机素数p/输出：图案列出现在主列的pos字符后面的位置int MonteCarlo(char* x，char* y，int pos，int p )装模作样int j=0；int Ipx，Ipy，wp；int x_len=(int)strlen(x )int y_len=(int)strlen(y )/取指纹Ipx=getIP(x pos - 1，y_len，p )Ipy=getIP(y，y_len，p )计算2m mod pwp=1；for(int i=0； i y_len； I )wp=(wp * 2) % p；/开始匹配模式列while(j=x_len - y_len - pos 1)装模作样if(Ipx=Ipy) return j 1；else装模作样IPX=(2* IPX-WP * (x j -0 ) (x jy _ len -0 ) ) % p；if(Ipx 0) Ipx =p；if(Ipx=p) Ipx -=p；j；以下称为以下称为return 0；以下称为/III，LasVegas算法/函数名称： LasVegas/功能： MonteCarlo算法的改进，对于Ip(X(j)=Ip(Y )，比较X(j )和y是否相等，如果相等则返回/子字符串在主字符串中的位置。 否则，继续循环。 该算法总是给出正确的位置/输入：主列s和图案列t、随机素数p/输出：图案列出现在主列的pos字符后面的位置int LasVegas(char* x，char* y，int pos，int p )装模作样int j=0；int Ipx，Ipy，wp；int x_len=(int)strlen(x )int y_len=(int)strlen(y )/取指