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

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

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

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

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