[發(fā)明專利]一種利用自動機(jī)實(shí)現(xiàn)文本精確匹配的系統(tǒng)和方法

無效

• 申請?zhí)枺?/td>: 201110415222.6
• 申請日: 2011-12-13
• 公開（公告）號: CN102521357A
• 公開（公告）日: 2012-06-27
• 發(fā)明（設(shè)計）人: 李鋒偉;姬乃軍;劉燦;張英文;劉朝輝;邵宗有
• 申請（專利權(quán)）人: 曙光信息產(chǎn)業(yè)（北京）有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京安博達(dá)知識產(chǎn)權(quán)代理有限公司 11271
• 代理人: 徐國文

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

本發(fā)明屬于網(wǎng)絡(luò)安全領(lǐng)域，具體涉及一種利用自動機(jī)實(shí)現(xiàn)文本精確匹配的系統(tǒng)和方法。

背景技術(shù)

常規(guī)文本匹配方法是在文本中搜索固定感興趣字串，但往往感興趣的字串不是固定不變的串，而是一系列形狀相近的正則特征串。另外，在常規(guī)文本匹配中，需要對感興趣的字串逐一在文本中掃描一遍，效率低下。

專利號CN200710119845.2(一種快速內(nèi)容分析的多關(guān)鍵詞匹配方法)公開了一種快速內(nèi)容分析的多關(guān)鍵詞匹配方法。所述發(fā)明方法包括預(yù)處理階段和模式匹配階段。其中，所述的預(yù)處理階段包括關(guān)鍵詞特征串裁剪和關(guān)鍵詞特征分片集合的構(gòu)建、基于關(guān)鍵詞特征分片集合的Bloom?Filte(布隆過濾器)構(gòu)造，以及原始關(guān)鍵詞集合線性表構(gòu)造，所述關(guān)鍵詞匹配階段包括：依據(jù)Bloom?Filter實(shí)現(xiàn)當(dāng)前窗口中文本串不與任何關(guān)鍵詞特征分片匹配的快速判定；只在判定失敗情況下通過字符串比較操作實(shí)現(xiàn)與候選關(guān)鍵詞的精確匹配；將文本匹配窗口連續(xù)多字節(jié)快速跳躍。本發(fā)明充分利用了待匹配文本與關(guān)鍵詞匹配成功概率異常低的特點(diǎn)，可實(shí)現(xiàn)大數(shù)量關(guān)鍵詞場景下的高速匹配，非常適合病毒檢測等在線病毒掃描應(yīng)用。

專利號CN200610000801.3(一種用于文本或網(wǎng)絡(luò)內(nèi)容分析的多關(guān)鍵詞匹配方法)公開了一種用于文本或網(wǎng)絡(luò)內(nèi)容分析的多關(guān)鍵詞匹配方法，屬于文本或網(wǎng)絡(luò)內(nèi)容處理技術(shù)領(lǐng)域。首先根據(jù)待匹配的關(guān)鍵詞，建立以狀態(tài)為節(jié)點(diǎn)的有限狀態(tài)自動機(jī)，并記錄關(guān)鍵詞中的字符；根據(jù)字符對上述有限狀態(tài)自動機(jī)進(jìn)行轉(zhuǎn)換，得到以字符為節(jié)點(diǎn)的有限狀態(tài)自動機(jī)，節(jié)點(diǎn)總數(shù)為m+1，m為上述關(guān)鍵詞中的字符數(shù)；將待匹配的文本或網(wǎng)絡(luò)數(shù)據(jù)流作為以字符為節(jié)點(diǎn)的有限狀態(tài)自動機(jī)的輸入，與關(guān)鍵詞進(jìn)行匹配。本發(fā)明方法與已有的AC方法相比，沒有引入任何附加計算。當(dāng)關(guān)鍵詞集合中所出現(xiàn)的字符數(shù)量少于最大可能字符數(shù)時，可以大大降低內(nèi)存空間消耗。

目前對文本的匹配算法多采用關(guān)鍵字匹配算法，即KMP算法。但實(shí)際應(yīng)用中感興趣的不僅僅是固定不變的子串，還有一類形狀相近的正則特征串。這種場合下，KMP算法就不適用了。

本發(fā)明通過自動機(jī)對任何文本進(jìn)行搜索、查詢、匹配相應(yīng)正則子串，同時利用自動機(jī)技術(shù)對所有正則子串生成自動機(jī)，只需遍歷文本一遍，顯著提高匹配的速度，同時也提高在文本匹配中的精度。同時，本發(fā)明方案還可以批量匹配一系列的文本文件。

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

本發(fā)明克服現(xiàn)有技術(shù)不足，匹配處理模塊，按照不同用戶的需求進(jìn)行合適的替代。

本發(fā)明提供了一種利用自動機(jī)實(shí)現(xiàn)文本精確匹配的系統(tǒng)，其包括

1)Dfa匹配引擎，用于接收輸入文本；

2)dfa跳轉(zhuǎn)表，用于對Dfa匹配引擎接收的輸入文本進(jìn)行匹配查詢，如果匹配成功，則進(jìn)入匹配處理模塊，否則進(jìn)入下一輪的文本輸入匹配；

3)匹配處理模塊。

本發(fā)明提供的利用自動機(jī)實(shí)現(xiàn)文本精確匹配的系統(tǒng)，其DFA狀態(tài)機(jī)是通過將感興趣的固定串或正則特征串放置到配置文件中，然后對該配置文件編譯生成的。

本發(fā)明提供的利用自動機(jī)實(shí)現(xiàn)文本精確匹配的系統(tǒng)，DFA狀態(tài)機(jī)是多個不同的系列DFA狀態(tài)機(jī)，其對應(yīng)于被進(jìn)行分組處理的配置文件。

本發(fā)明還提供了一種利用自動機(jī)實(shí)現(xiàn)文本精確匹配的方法，其包括

1)Dfa匹配步驟，接收輸入文本并利用dfa跳轉(zhuǎn)表對其進(jìn)行匹配查詢，如果匹配成功，則進(jìn)入匹配處理模塊，否則進(jìn)入下一輪的文本輸入匹配；

2)匹配處理步驟。

本發(fā)明提供的利用自動機(jī)實(shí)現(xiàn)文本精確匹配的方法，其DFA狀態(tài)機(jī)是通過將感興趣的固定串或正則特征串放置到配置文件中，然后對該配置文件編譯生成的。

本發(fā)明提供的利用自動機(jī)實(shí)現(xiàn)文本精確匹配的方法，其DFA狀態(tài)機(jī)是多個不同的系列DFA狀態(tài)機(jī)，其對應(yīng)于被進(jìn)行分組處理的配置文件。

與現(xiàn)有技術(shù)相比，本發(fā)明的有益效果在于：通過采用該方案，可以實(shí)現(xiàn)靈活、有效、精確的查找匹配串。同時利用該方案，還可以實(shí)現(xiàn)對相似文檔的批量匹配處理。

附圖說明

圖1是流程示意圖。

具體實(shí)施方式