海量多模式串匹配算法關(guān)鍵技術(shù)研究.pdf

1、經(jīng)過40余年的發(fā)展,字符串匹配已經(jīng)從單一的單模式串匹配發(fā)展成為包含多模式匹配、正則匹配、近似匹配等多個(gè)新方向的研究領(lǐng)域。而隨著計(jì)算機(jī)技術(shù)、網(wǎng)絡(luò)技術(shù)的發(fā)展,社會(huì)的進(jìn)步,字符串匹配也有了越來越廣泛的應(yīng)用場(chǎng)所。在信息檢索、入侵檢測(cè)、網(wǎng)絡(luò)數(shù)據(jù)分析等多個(gè)領(lǐng)域都能夠看到字符串匹配的身影。布爾表達(dá)式匹配也有很多的應(yīng)用,如搜索引擎中的布爾查詢,病毒檢測(cè)系統(tǒng)的特征組合匹配等等。字符串匹配算法以往的研究和實(shí)驗(yàn)分析都是在模式集規(guī)模在幾千到幾萬的情況下進(jìn)行的,

2、對(duì)于大規(guī)模模式集下的算法沒有進(jìn)行過深入的分析。本文主要研究?jī)?nèi)容分為如下兩個(gè)部分:
　　研究在大規(guī)模模式集下的多模式匹配問題的特點(diǎn)和難點(diǎn),提出了基于Wu-manber算法的三種改進(jìn)算法:基于最短關(guān)鍵字長(zhǎng)度哈希的改進(jìn)算法、多哈希值預(yù)檢改進(jìn)算法、成組比較改進(jìn)算法。
　　研究布爾表達(dá)式匹配問題,提出更泛化的復(fù)雜與或布爾表達(dá)式匹配問題,并且針對(duì)該問題提出擴(kuò)展位標(biāo)記算法。此外本文還提出了布爾表達(dá)式化簡(jiǎn)方法,來進(jìn)一步減少表達(dá)式數(shù)目,提高匹