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

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

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

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

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