帶可變長(zhǎng)度通配符的模式匹配算法研究.pdf

1、隨著互聯(lián)網(wǎng)的飛速發(fā)展，網(wǎng)絡(luò)上的信息量呈現(xiàn)出爆炸式的增長(zhǎng)，如何從大量信息中迅速有效地提取出所需信息成為一項(xiàng)重要的研究課題。高效的模式匹配算法能迅速檢索出用戶(hù)需要的重要信息。模式匹配問(wèn)題是個(gè)古老而又經(jīng)典的問(wèn)題，模式P的相鄰字符之間出現(xiàn)可變長(zhǎng)度的通配符使的該問(wèn)題更加復(fù)雜。帶有通配符和長(zhǎng)度約束的模式匹配問(wèn)題PMWL(Pattern Matching with Wildcards and Lengthconstraints)不僅具有重要的理論研究

2、價(jià)值，而且在生物信息學(xué)、網(wǎng)絡(luò)安全和信息檢索中具有重要的實(shí)際應(yīng)用價(jià)值。
　　本文對(duì)帶有可變長(zhǎng)度通配符的模式匹配問(wèn)題展開(kāi)研究，主要研究?jī)?nèi)容有三個(gè)方面:(1)基于關(guān)鍵字符定位的模式匹配算法研究;(2)提出了一種文本分割算法，并與后綴樹(shù)相結(jié)合，提高模式匹配算法的時(shí)間和空間效率;(3)對(duì)PMWL問(wèn)題中匹配解的完備性問(wèn)題進(jìn)行研究，提出了一種新穎的數(shù)據(jù)結(jié)構(gòu)CluTree，以及基于CluTree的檢索算法，能進(jìn)一步提高匹配解的完備性和時(shí)間效率。<

3、br>　　主要研究?jī)?nèi)容和創(chuàng)新如下:
　　(1)基于關(guān)鍵字符定位的模式匹配算法研究;
　　對(duì)于含有通配符和長(zhǎng)度限制的模式匹配問(wèn)題，模式中相鄰字符間包含通配符使匹配問(wèn)題更加復(fù)雜。當(dāng)文本T的長(zhǎng)度比較大，字符分布非常復(fù)雜時(shí)，目前的算法定位誤差比較大。由于現(xiàn)有算法沒(méi)有考慮待檢索文本T分布的特點(diǎn)，沒(méi)有考慮到模式P中子模式及各字符的不同作用，在一些不可能匹配的地方進(jìn)行檢索，消耗了檢索時(shí)間，降低了檢索效率。本文根據(jù)模式P中各字符在文本T中出

4、現(xiàn)的差異及在模式P中的分布，提出一種模式P中字符重要性的評(píng)價(jià)機(jī)制，先計(jì)算出模式P的頻率函數(shù)fT(Pj)和自頻率函數(shù)fP(Pj)，根據(jù)以上的計(jì)算結(jié)果找出模式P的KWP(k)函數(shù)，由KWP(k)函數(shù)找出了模式P的關(guān)鍵字符Pk。關(guān)鍵字符作為定位字符，然后借鑒SAIL的匹配思路，改進(jìn)掃描表格的方式。當(dāng)表格成功構(gòu)建后，算法將得到一個(gè)匹配解。文本T掃描完畢后，算法返回所有的匹配解。
　　(2)提出了一種文本分割算法，并與后綴樹(shù)相結(jié)合，提高模式

5、匹配算法的時(shí)間和空間效率;
　　對(duì)大文本進(jìn)行分而治之的模式匹配策略，有效地解決了大規(guī)模串匹配的性能瓶頸。如何進(jìn)行正確的分割是該問(wèn)題的核心部分。本文設(shè)計(jì)分割算法，從T中找出可以分割，且不影響匹配結(jié)果的點(diǎn)。借鑒SAIL的forward過(guò)程的思想，利用局部約束確定解的空間，排除所有不滿(mǎn)足條件的位置。在具體實(shí)現(xiàn)過(guò)程中，算法逐個(gè)掃描初始分割點(diǎn)附近的點(diǎn)，若發(fā)現(xiàn)某個(gè)點(diǎn)與周?chē)狞c(diǎn)不可能構(gòu)成一個(gè)匹配解時(shí)結(jié)束循環(huán)，返回當(dāng)前掃描的位置，并將作為正確的分

6、割位置。分割算法對(duì)大文本的檢索效率有了很大提高?；诜指钏惴Ｊ狡ヅ渌惴芗涌鞕z索速度，因此也很好的提高了檢索的時(shí)間。將分割算法與后綴樹(shù)相結(jié)合的多后綴樹(shù)檢索算法能較大提高后綴樹(shù)算法的空間效率。設(shè)計(jì)的算法可用于生物信息學(xué)領(lǐng)域中，進(jìn)行DNA序列的匹配和蛋白質(zhì)序列的識(shí)別，可以提高模式匹配的效率。
　　(3)基于CluTree的PMWL問(wèn)題匹配算法
　　由于通配符的出現(xiàn)，PMWL問(wèn)題中的檢索將更加復(fù)雜，在不含通配符的簡(jiǎn)單模式匹配SP

7、M(simple pattern matching)中不會(huì)有解的爭(zhēng)議，一個(gè)待匹配文本中對(duì)于任意給定模式的解是確定的。而在PMWL問(wèn)題中，一個(gè)匹配位置可能作為模式中子模式出現(xiàn)，也可能作為通配符的位置出現(xiàn)，這種匹配位置的多樣性導(dǎo)致匹配結(jié)果的不確定性，更為復(fù)雜的是可能有多個(gè)候選匹配串的位置相互嵌套，如何選擇正確的匹配位置以確定最優(yōu)解一直是個(gè)待解決的難題。多個(gè)嵌套模式中選定最優(yōu)匹配位置，目前的算法在處理嵌套區(qū)域的糾纏態(tài)模式的匹配問(wèn)題，都采用左優(yōu)

8、先的left-most策略。當(dāng)模式比較復(fù)雜，這種相互嵌套糾纏的區(qū)域是最復(fù)雜的匹配區(qū)域，簡(jiǎn)單的左優(yōu)先無(wú)法解決這類(lèi)問(wèn)題，必然會(huì)丟失匹配串。提出了一種基于CluTree結(jié)構(gòu)的檢索算法RBCT，對(duì)這樣的嵌套區(qū)域建立一個(gè)多根的紅黑樹(shù)群CluTree，在模式的匹配過(guò)程中根據(jù)CluTree中各節(jié)點(diǎn)的共享度、相關(guān)度及混合信息熵來(lái)選擇匹配的路徑，并且運(yùn)用動(dòng)態(tài)剪枝技術(shù)來(lái)保證樹(shù)群CluTree的動(dòng)態(tài)更新和共享節(jié)點(diǎn)資源的釋放，RBCT算法對(duì)CluTree中的節(jié)