KMP算法的改進

2014-12-31 00:00:00高世澤

數(shù)字化用戶 2014年17期

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

【關鍵詞】模式；串匹配；文本處理

符號說明：

模式串S的長度：m

主串T的長度：n

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

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

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

字符X所對應出現(xiàn)的頻率：PX

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

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

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

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

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

例 S=’abstract’ 則S所對應的字符M為E，PM=0.105。

算法描述：

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

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

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

時間復雜度分析

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

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

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

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

結論

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