對串匹配技術(shù)中的Wu-Manber算法的研究.pdf

1、字符串匹配是計算機研究領(lǐng)域中的一個古老、經(jīng)典而且被廣泛研究的課題,是信息檢索領(lǐng)域和計算機生物學領(lǐng)域等的關(guān)鍵技術(shù)之一。在當今的互聯(lián)網(wǎng)時代,對匹配算法的需求日新月異,對處理的實時性的需求越來越高。這些都對原有的字符串匹配技術(shù)提出了新的挑戰(zhàn),有必要對原字符串匹配技術(shù)進行改進和優(yōu)化。 本文主要是對高效的多字符串匹配算法--Wu-Manber算法進行研究。本文針對Wu-Manber算法的散列表HASH的表項:HASH鏈表的不足,提出了基于

2、非空公共子后綴模式的處理算法；而后綜合前人對Wu-Manber算法的SHIFT表的改進,提出更加高效的字符串匹配算法；進而提出一種在大規(guī)模串匹配時對Wu-Manber算法的改進。 本文的研究成果具體如下： 1.基于非空公共子后綴的Wu-Manber算法的改進：針對Wu-Manber算法在處理公共子后綴模式情況下的不足,本文提出了一種基于非空公共子后綴模式的處理算法。該算法把同一next鏈表中有非空公共子后綴的模式匯集在-

3、起,進一步減小了next鏈表的平均長度。在匹配過程中減少了字符比較的次數(shù),從而提高算法的運行效率。本文對搜狗實驗室給出的相關(guān)文檔進行全文檢索實驗,并和原Wu-Manber算法、前人提出的改進算法進行比較。實驗結(jié)果表明,本文提出的改進算法有效地減少了匹配過程中字符比較的次數(shù),從而提高匹配的速度和效率。 2.對Wu-Manber算法的綜合改進：對1中提出的算法進行了改進,在對next鏈表進行分類的同時把含有非空公共子后綴的結(jié)點提到鏈

4、表的前部；并整合了前人提出的“精確的不良字符轉(zhuǎn)移和弱化的良好后綴轉(zhuǎn)移的改進”方法。新改進的算法充分利用以上兩種算法的優(yōu)點,使匹配過程中字符比較的次數(shù)得到了進一步減少。新改進的Wu-Manber匹配算法在實驗中取得了更高的效率,比原算法提高到4.6％以上。 3.Wu-Manber算法在大規(guī)模模式串下的改進：對提出的算法進行了改進,把原算法中next鏈表中結(jié)點的Same_Subsuffix域分裂成兩個子域,使得在大規(guī)模模式串的情況下