【摘 要】進(jìn)行KMP算法時(shí)，根據(jù)模式串的字符特點(diǎn)和統(tǒng)計(jì)學(xué)規(guī)律，在每一次匹配前增加一次比較，使得每次匹配過(guò)程開始前有一定的概率跳過(guò)模式串字符長(zhǎng)度個(gè)字符，以減少比較次數(shù)，在文本處理中有較好的使用效果。

【關(guān)鍵詞】模式；串匹配；文本處理

符號(hào)說(shuō)明：

模式串S的長(zhǎng)度：m

主串T的長(zhǎng)度：n

模式串中未出現(xiàn)的字符的集合：D

字符出現(xiàn)的頻率：P

D中字符P值最高的字符：M

字符X所對(duì)應(yīng)出現(xiàn)的頻率：PX

整個(gè)比較過(guò)程中字母比較次數(shù)：d

整個(gè)匹配過(guò)程中匹配的次數(shù)：t

在英文模式串匹配過(guò)程中，設(shè)定模式串L所包含的字符種類少于27個(gè)（即字母表字符個(gè)數(shù)加上空格）。根據(jù)統(tǒng)計(jì)學(xué)規(guī)律，英文中每個(gè)字母出現(xiàn)的概率是不相同的，其分布近似于下表

本方法就是根據(jù)字母出現(xiàn)的頻率有差異，以縮短匹配過(guò)程中字母比較的次數(shù)以提高效率。

在參考文獻(xiàn)[2]中給出了KMP算法實(shí)現(xiàn)的具體方法。在匹配開始前，需對(duì)模式串S進(jìn)行next函數(shù)的求值。而本方法在對(duì)next函數(shù)進(jìn)行求值后，還要查找出在S中未出現(xiàn)過(guò)的字符所構(gòu)成字符集D，并且根據(jù)上表，找出D中出現(xiàn)概率最高的非空格字符M，則M所對(duì)應(yīng)的P為PM。

例 S=’abstract’ 則S所對(duì)應(yīng)的字符M為E，PM=0.105。

算法描述：

從主串的第k個(gè)字符開始進(jìn)行模式匹配，先找到第（k+m）個(gè)字符與M進(jìn)行比較。比較成功轉(zhuǎn)到b步驟。比較不成功轉(zhuǎn)到c步驟。

表明第k個(gè)字符與第（k+m）個(gè)字符之間不包含S，所以可以全部跳過(guò)，從第k+l+1個(gè)字符重新開始開始匹配。使k=k+m+1，轉(zhuǎn)回a步驟

返回第k個(gè)字符進(jìn)行KMP算法的模式匹配過(guò)程，若出現(xiàn)匹配失敗，則根據(jù)KMP算法的next函數(shù)將匹配位置向右滑動(dòng)，并將此位置賦值給k，返回a步驟。若全部匹配成功，則根據(jù)KMP算法返回匹配成功的位置。

時(shí)間復(fù)雜度分析

KMP的時(shí)間復(fù)雜度為O（m+n）[2]，而本算法的基本思路與KMP算法相似但有一定的幾率跳過(guò)m個(gè)字符，其在不考慮字母前后相關(guān)性的情況下，在整個(gè)匹配過(guò)程中跳過(guò)的字符數(shù)為（PM*t*m），增加的比較次數(shù)為t。

則在KMP算法下：dKMP=m+n

而改進(jìn)后的方法：d=m+n+t-PM*t*m

從二者的字符比較次數(shù)可以看出當(dāng)：t < PM*t*m時(shí)，此方法的效果優(yōu)于KMP算法。

結(jié)論

本文給出了一種新的串匹配方法，結(jié)合統(tǒng)計(jì)學(xué)上字母出現(xiàn)頻率的不同，在KMP算法的基礎(chǔ)上，盡可能的在匹配過(guò)程中跳過(guò)不必進(jìn)行比較的字符串以提高匹配效率，在文本搜索中有較好的效果。

參考文獻(xiàn)：

[1]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（c語(yǔ)言版）北京：清華大學(xué)出版社

[2]李梅，李亦農(nóng).信息論基礎(chǔ)教程（第2版）北京郵電大學(xué)出版社

作者簡(jiǎn)介：

高世澤，男，籍貫：山東省煙臺(tái)市，工作單位：哈爾濱市東北林業(yè)大學(xué)理學(xué)院，學(xué)位：本科在校生，方向：數(shù)學(xué)。