[發(fā)明專(zhuān)利]一種大規(guī)模關(guān)鍵詞匹配方法

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 200710122231.X
• 申請(qǐng)日: 2007-09-24
• 公開(kāi)（公告）號(hào): CN101398820A
• 公開(kāi)（公告）日: 2009-04-01
• 發(fā)明（設(shè)計(jì)）人: 葉潤(rùn)國(guó);周濤;華東明;孫海波;駱擁政;焦玉峰
• 申請(qǐng)（專(zhuān)利權(quán)）人: 北京啟明星辰信息技術(shù)有限公司
• 主分類(lèi)號(hào): G06F17/30
• 分類(lèi)號(hào): G06F17/30
• 代理公司: 北京市商泰律師事務(wù)所
• 代理人: 毛燕生

技術(shù)領(lǐng)域

本發(fā)明涉及計(jì)算機(jī)內(nèi)容分析技術(shù)領(lǐng)域，具體涉及一種快速內(nèi)容分析的多關(guān)鍵詞匹配方法。

背景技術(shù)

多關(guān)鍵詞匹配(Multiple?Pattern?String?Matching)解決的問(wèn)題是快速判斷某一數(shù)據(jù)塊中是否包含關(guān)鍵詞集合中的某一或某些關(guān)鍵詞。多關(guān)鍵詞匹配技術(shù)廣泛應(yīng)用于文本處理、網(wǎng)絡(luò)內(nèi)容分析、入侵檢測(cè)、信息檢索和病毒檢測(cè)等領(lǐng)域。

傳統(tǒng)多關(guān)鍵詞匹配方法包括文獻(xiàn)[A.V.Aho，M.J.Corasick.EfficientString?Matching：An?Aid?to?Bibliographic?Search，(中文名稱(chēng)：一種用于目錄搜索的高效的字符串匹配方法)Communications?of?the?ACM，1975，18(6)：333-340]、文獻(xiàn)[S.Wu，U.Manber.A?Fast?Algorithm?For?Multi-Pattern?Searching(中文名稱(chēng)：一種快速的多模式匹配算法).TechnicalReport?TR-94-17，University?of?Arizona.1994：1-11]和文獻(xiàn)[K.G.Anagnostakis，S.Antonatos，M.Polychronakis，and?E.P.Markatos.：A?domain-specific?string?matching?algorithm?for?intrusion?detection(中文名稱(chēng)：一種領(lǐng)域相關(guān)的為入侵檢測(cè)設(shè)計(jì)得多模式匹配算法).In?Proceedings?of?IFIPIntemational?Information?Security?Conference(SEC′03)，May?2003]等。這些文獻(xiàn)涉及的多關(guān)鍵詞匹配方法都存在一個(gè)理想的應(yīng)用條件，比如，Aho-Corasick方法的最佳應(yīng)用條件為小規(guī)模關(guān)鍵詞場(chǎng)合，Wu-Manber的最佳應(yīng)用條件為中等規(guī)模關(guān)鍵詞應(yīng)用場(chǎng)合，E2XB的最佳應(yīng)用為入侵檢測(cè)場(chǎng)合。這些多關(guān)鍵詞匹配方法在大規(guī)模關(guān)鍵詞應(yīng)用場(chǎng)合下效果并不理想，并不適合實(shí)時(shí)病毒檢測(cè)類(lèi)應(yīng)用場(chǎng)合。實(shí)時(shí)病毒檢測(cè)類(lèi)應(yīng)用場(chǎng)合下的多關(guān)鍵詞匹配具有如下特點(diǎn)：1)關(guān)鍵詞數(shù)量非常大，一般在6萬(wàn)到20萬(wàn)條左右；2)關(guān)鍵詞長(zhǎng)度一般比較大，最小為8字節(jié)；3)待檢測(cè)文本長(zhǎng)度較大，從幾千字節(jié)到幾兆字節(jié)不等；4)待檢測(cè)文本與任何關(guān)鍵詞匹配的成功概率異常低。

文獻(xiàn)[Erdogan，O.；Pei?Cao，Hash-AV：fast?virus?signature?scanning?bycache-resident?filters(中文名稱(chēng)：HASH-AV：一種采用緩存駐留過(guò)濾器的快速病毒特征掃描方法)，Global?Telecommunications?Conference，2005.GLOBECOM?apos；05.IEEE?Volume?3，Issue，28?Nov.-2?Dec.2005?Page(s)：6pp.]給出了一種針對(duì)病毒檢測(cè)類(lèi)應(yīng)用場(chǎng)合多關(guān)鍵詞匹配特點(diǎn)而設(shè)計(jì)的多關(guān)鍵詞匹配方法：HASH-AV，它構(gòu)建一個(gè)可容納于現(xiàn)代CPU高速緩存中的布隆過(guò)濾器(Bloom?Filter)，并巧妙設(shè)計(jì)了一組布隆過(guò)濾器散列函數(shù)，通過(guò)依次調(diào)用該組散列函數(shù)來(lái)實(shí)現(xiàn)當(dāng)前窗口中文本串不與任一關(guān)鍵詞匹配的快速判定。由于病毒檢查等應(yīng)用場(chǎng)合下，文本數(shù)據(jù)流與任一關(guān)鍵詞匹配的概率異常低，絕大多數(shù)情況下這種基于布隆過(guò)濾器的快速判定都是成功的，絕大多數(shù)時(shí)候并不需要執(zhí)行代價(jià)昂貴的全關(guān)鍵詞比較操作。與其它關(guān)鍵詞匹配方法相比，該關(guān)鍵詞匹配方法更多地考慮了病毒檢測(cè)領(lǐng)域獨(dú)有的特性，在病毒檢測(cè)應(yīng)用場(chǎng)合表現(xiàn)出了較好的掃描速率。利用布隆過(guò)濾器在判定某一元素是否屬于指定元素集合時(shí)不存在漏報(bào)，但是可能存在誤報(bào)，特別在布隆過(guò)濾器表示的元素集合較大時(shí)誤報(bào)率更大。理論上來(lái)說(shuō)，可以通過(guò)增大布隆過(guò)濾器的位串大小來(lái)降低誤報(bào)，但是實(shí)際上很難達(dá)到效果，因?yàn)閷?shí)際情況中構(gòu)造的布隆過(guò)濾器散列函數(shù)并不具有較好的隨機(jī)性。HASH-AV方法采用一個(gè)布隆過(guò)濾器來(lái)表示所要查找的關(guān)鍵詞集合，我們?cè)趯?shí)驗(yàn)中發(fā)現(xiàn)，當(dāng)HASH-AV中查找的關(guān)鍵詞集合大于10萬(wàn)時(shí)，基于單一布隆過(guò)濾器執(zhí)行當(dāng)前文本不與任何關(guān)鍵詞匹配判定的誤報(bào)率較高，這直接影響了HASH-AV的關(guān)鍵詞匹配效率；同時(shí)，在每次文本匹配窗口移動(dòng)后，HASH-AV方法需要基于當(dāng)前文本重新執(zhí)行各布隆過(guò)濾器散列函數(shù)，而沒(méi)有考慮當(dāng)前文本串與上一窗口中文本串大部分相同這個(gè)特點(diǎn)。

發(fā)明內(nèi)容