三種模式匹配算法的比較和分析

1、三種模式匹配算法作業(yè)要求：分別用KMP、MonteCarlo、LasVegs算法編制三個(gè)程序，隨機(jī)生成不小于5000對(duì)長(zhǎng)度不等的01串（三個(gè)程序使用相同的串），然后統(tǒng)計(jì)算法的執(zhí)行時(shí)間和MonteCarlo算法的出錯(cuò)比率，并根據(jù)運(yùn)行結(jié)果對(duì)三種算法進(jìn)行深入的比較。1、 算法思路KMP算法的主要特點(diǎn)是指向主串的指針不需要回溯，只向右移動(dòng)，即模式串在與主串失配時(shí)，并不回溯主串的指針與模式串重新匹配，而是根據(jù)已經(jīng)得到的匹配信息將模式串盡可能遠(yuǎn)的向右滑動(dòng)一段。滑動(dòng)距離的大小取決于模式串的失效函數(shù)next, nextk（0=k2m時(shí)， Y和X(j)的對(duì)p作模運(yùn)算后的“指紋”Ip都要小于p, 此時(shí)p不可能可以

2、整除|Y X(j)|，因此不會(huì)出現(xiàn)當(dāng)Ip（X(j)）=Ip(y)時(shí)卻有X(j)Y的誤判情況，所以這種情況下MonteCarlo出錯(cuò)率為0。3） 素?cái)?shù)一定大時(shí)，MonteCarlo算法的出錯(cuò)率比理論值1/n要小的多，即當(dāng)Ip（X(j)）= Ip(y)時(shí)卻有X(j)Y的情況很少。相反，當(dāng)素?cái)?shù)很小時(shí)，不同0/1序列對(duì)素?cái)?shù)作模運(yùn)算的結(jié)果相同的可能性增大，出錯(cuò)率相應(yīng)地變大。4） 當(dāng)模式串的長(zhǎng)度比主串小很多時(shí)，三個(gè)算法的執(zhí)行時(shí)間明顯快了，KMP和MonteCarlo算法的執(zhí)行時(shí)間幾乎相等。這也是比較容易理解的，模式串很短意味著它與主串匹配成功的可能性就大，算法不需要從頭到尾掃描一遍主串就可以在主串的較前面

3、找到匹配串的位置，此外，模式串的長(zhǎng)度小則說(shuō)明耗費(fèi)在掃描一遍模式串的時(shí)間就短，因此執(zhí)行算法所花費(fèi)的時(shí)間就少得多，KMP時(shí)間復(fù)雜度接近O(m+n)，與MonteCarlo算法相等。為了更好的說(shuō)明問(wèn)題，對(duì)p的大小和模式串的長(zhǎng)度選取了幾組不同的測(cè)試數(shù)據(jù)，以下為不同數(shù)據(jù)的運(yùn)行結(jié)果（其中m，n分別為主串和模式串的長(zhǎng)度，m, n, p都是在給定的區(qū)間上隨機(jī)取值）：1）第一組：素?cái)?shù)p2m，取，從測(cè)試結(jié)果可以看出MonteCarlo算法的出錯(cuò)率達(dá)到了20%以上，這是難以接受的。p越小MonteCarlo算法的出錯(cuò)率越大。2）第二組：取，此時(shí)隨機(jī)選取素?cái)?shù)p既有可能小于也有可能大于，MonteCarlo算法的出錯(cuò)率

4、只有0.03%.3）第三組：取，此時(shí)隨機(jī)選取的素?cái)?shù)必定大于，MonteCarlo算法的出錯(cuò)率降至0.4）第四組：取，KMP算法和MonteCarlo算法每次執(zhí)行的時(shí)間幾乎相等，并且MonteCarlo算法的出錯(cuò)率很小,幾乎接近0。5）第五組：取，素?cái)?shù)p取介于16位機(jī)器表示最大整型數(shù)和32位機(jī)器表示最大整型數(shù)之間，此時(shí)MonteCarlo算法的出錯(cuò)率為0.07% 1/n3、算法實(shí)現(xiàn)代碼（程序中MAXSIZE=10000）/文件名：PatternMatching.cpp/功能：實(shí)現(xiàn)并比較三種模式匹配算法：KMP，MonteCarlo，LasVegas#include random.h#includ

5、e randstr.h#include defs.h#include #include #include #include #include #include #include using namespace std;/函數(shù)聲明/bool isprime(int n);/判斷n是否為素?cái)?shù)int random_prime( int min, int max ); /隨機(jī)產(chǎn)生一個(gè)minmax-1之間的素?cái)?shù)int KMP(char* s, char* t, int position); /KMP算法int getIP(char *x, int len, int prime); /獲取x0xlen-1

6、的指紋int MonteCarlo(char* x, char* y, int position, int prime);/MonteCarlo算法int LasVegas(char* x, char* y, int position, int prime); /LasVegas算法/函數(shù)定義/函數(shù)名：isprime/功能：測(cè)試一個(gè)整數(shù)是否為素?cái)?shù)/輸出：若n為素?cái)?shù)，則返回true;否則falsebool isprime(int n)for(int i = 2; i = min; i-)if(isprime(i) break;return i;/三種模式匹配算法的實(shí)現(xiàn)/I、KMP算法/函數(shù)名：K

7、MP/功能：利用KMP算法匹配模式串/輸入：主串s和模式串t/輸出：模式串在主串第pos個(gè)字符之后出現(xiàn)的位置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

8、j = nextj;/再匹配模式串，求在主串中的位置i = pos - 1 ;j = 0;while(i s_len & j = t_len) return (i - t_len) + 1;else return 0;/II、MonteCarlo算法/函數(shù)名：getIP/功能：求序列x的指紋/輸入：01串x，長(zhǎng)度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;r

9、eturn ip;/函數(shù)名：MonteCarlo/功能：利用隨機(jī)算法MonteCarlo進(jìn)行模式匹配/輸入：主串s和模式串t,隨機(jī)素?cái)?shù)p/輸出：模式串在主串第pos個(gè)字符之后出現(xiàn)的位置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); /計(jì)算2m mod pwp

10、 = 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; elseIpx = ( 2 * Ipx - wp * ( xj - 0 ) + (xj + y_len - 0) ) % p;if(Ipx = p) Ipx -= p;j+;return 0;/III、LasVegas算法/函數(shù)名：LasVegas/功能：對(duì)MonteCarlo算法的改進(jìn)，當(dāng)Ip(X(j)=Ip(Y)時(shí)比較X(j)與Y是否相等，若相等則返

11、回/ 子串在主串中的位置，否則繼續(xù)執(zhí)行循環(huán)。該算法總能給出正確的位置/輸入：主串s和模式串t,隨機(jī)素?cái)?shù)p/輸出：模式串在主串第pos個(gè)字符之后出現(xiàn)的位置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); /取指紋Ipx = getIP(x + pos - 1, y_len, p);Ipy = getIP(y, y_len, p); /計(jì)算2m mod pwp = 1;for(int i = 0

12、; i y_len; i+)wp = (wp * 2) % p; /開始匹配模式串while( j = x_len - y_len -( pos - 1) )if(Ipx = Ipy & !strncmp(x + j, y, strlen(y)return j + 1;elseIpx = ( 2 * Ipx - wp * ( xj - 0 ) + (xj + y_len - 0) ) % p;if(Ipx = p) Ipx -= p;j+;return 0;/主函數(shù)/main()char *x, *y; DWORD t_start, t_end;/記錄算法開始執(zhí)行時(shí)間和結(jié)束時(shí)間int m,n;

13、int index_KMPMAXSIZE, index_MCMAXSIZE, index_LVMAXSIZE;/分別存放KMP和MonteCarlo算法返回的匹配結(jié)果，即模式串在主串中首次出現(xiàn)的位置 int primeMAXSIZE; /存放MAXSIZE個(gè)隨機(jī)產(chǎn)生的素?cái)?shù)int minlen, maxlen; while(1)cout maxlen;cout minlen;/隨機(jī)產(chǎn)生MAXSIZE對(duì)主串和子串最長(zhǎng)長(zhǎng)度分別為maxlen,minlen的0/1串RandomString rs(minlen,maxlen); /素?cái)?shù)發(fā)生器：產(chǎn)生MonteCarlo和Las Vegas算法中所需要的素

14、數(shù)for(int i = 0; i MAXSIZE; i+)x = rs.getX(i);y = rs.getY(i);n = (int)strlen(y);m = (int)strlen(y);primei = random_prime(m*m,MAXINT32);/隨機(jī)產(chǎn)生一個(gè)素?cái)?shù)cout endl;cout 三種模式匹配算法運(yùn)行時(shí)間： endl;cout - endl;/KMP算法t_start = GetTickCount();/開始時(shí)間for(int i = 0; i MAXSIZE; i+)x = rs.getX(i);y = rs.getY(i);index_KMPi = KMP

15、(x, y, 1);t_end = GetTickCount();/結(jié)束時(shí)間cout KMP ： t_end - t_start ms endl; /MonteCarlo算法int mismatch = 0 ; /失敗的次數(shù)t_start = GetTickCount();/開始執(zhí)行MonteCarlo算法for(int i = 0; i MAXSIZE; i+)x = rs.getX(i);y = rs.getY(i);index_MCi = MonteCarlo(x, y, 1, primei);t_end = GetTickCount();/MonteCarlo算法運(yùn)行完畢cout MonteCarlo ： t_end - t_start ms endl; /LasVegas算法t_start = GetTickCount();/開始執(zhí)行MonteCarlo算法for(int i = 0; i MAXSIZE; i+)x = rs.getX(i);y = rs.getY(i);index_LVi = LasVegas(x, y, 1, primei);t_end = GetTickCount();/LasVegas算法運(yùn)行完畢cout LasVegas ： t_end - t_