高性能精確單模式串匹配算法研究.pdf

1、串匹配問(wèn)題是計(jì)算機(jī)科學(xué)的基礎(chǔ)問(wèn)題之一，幾乎所有涉及字符串處理的應(yīng)用中都或多或少的存在字符串匹配的要求。特別是在信息檢索，網(wǎng)絡(luò)安全，計(jì)算生物學(xué)等領(lǐng)域，字符串匹配為這些領(lǐng)域的核心問(wèn)題。在所有字符串匹配問(wèn)題中，精確單模式匹配算法設(shè)計(jì)又是串匹配問(wèn)題的基礎(chǔ)。目前，隨著網(wǎng)絡(luò)安全問(wèn)題的凸顯，網(wǎng)絡(luò)技術(shù)、計(jì)算生物學(xué)的高速發(fā)展，以及“信息爆炸”現(xiàn)象愈加嚴(yán)重，字符串匹配應(yīng)用對(duì)字符串匹配性能的要求越來(lái)越高，這對(duì)高性能字符串匹配應(yīng)用的串匹配算法設(shè)計(jì)(特別是精確單

2、模式匹配算法)提出了新的挑戰(zhàn)。 本文主要對(duì)高性能精確單模式串匹配算法進(jìn)行研究。首先對(duì)現(xiàn)有高性能精確單模式算法發(fā)展進(jìn)行分析，給出目前在英文語(yǔ)料匹配下，性能最高的精確單模式串匹配算法。并分別對(duì)當(dāng)前英文語(yǔ)料匹配下性能最高的兩個(gè)串匹配算法Tuned BM和SBNDM2提出改進(jìn)，提出了DQM算法和S2BNDM算法。 具體來(lái)說(shuō)，本文成果主要在于： 1．總結(jié)前人研究結(jié)果，分析了現(xiàn)有精確單模式串匹配算法，并給出了目前進(jìn)行字符串匹

3、配領(lǐng)域研究的研究方向，以及目前性能最高的精確單模式串匹配算法。 2．提出一種基于后綴匹配機(jī)制的高性能精確單模式串匹配算法—DQM算法。DQM算法以tuned BM算法為基礎(chǔ)算法，在tuned BM算法基礎(chǔ)上引入兩個(gè)判定字交替進(jìn)行跳躍的方法降低了隨跳躍進(jìn)行判定字匹配概率動(dòng)態(tài)增長(zhǎng)對(duì)算法性能的影響；引入了一種改進(jìn)的越界保護(hù)機(jī)制以降低越界檢查的開(kāi)銷；并通過(guò)位操作和合并操作的方法改進(jìn)算法在判定字匹配后的動(dòng)作，使分支與跳轉(zhuǎn)的次數(shù)降至最低。實(shí)

4、驗(yàn)表明，DQM性能比Tuned BM算法更高。 3．提出了一種基于位并行、循環(huán)展開(kāi)、按子串匹配機(jī)制的高性能精確單模式串匹配算法—S2BNDM系列算法。S2BNDM算法以SBNDM2算法為基礎(chǔ)算法，通過(guò)修改BNDM類算法的位掩碼定義，成功將BNDM類算法的核心循環(huán)化簡(jiǎn)至五條指令的最簡(jiǎn)形式。同時(shí)，本文在 SBNDM2算法中引入下標(biāo)越界保護(hù)，將下標(biāo)越界檢查的開(kāi)銷也降至最低。實(shí)驗(yàn)數(shù)據(jù)顯示，在模式長(zhǎng)度不超過(guò)機(jī)器字長(zhǎng)的英文語(yǔ)料檢索應(yīng)