網(wǎng)絡(luò)信息監(jiān)控中的多模式匹配算法范文

本站小編為你精心準(zhǔn)備了網(wǎng)絡(luò)信息監(jiān)控中的多模式匹配算法參考范文，愿這些范文能點燃您思維的火花，激發(fā)您的寫作靈感。歡迎深入閱讀并收藏。

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，網(wǎng)絡(luò)信息安全的重要性變得日益突出，現(xiàn)有網(wǎng)絡(luò)信息監(jiān)控系統(tǒng)，在網(wǎng)絡(luò)協(xié)議還原和分析方面的性能比較低，達(dá)不到信息監(jiān)控的需要。在網(wǎng)絡(luò)信息監(jiān)控系統(tǒng)中，多模式匹配算法是解決對敏感內(nèi)容過濾的最佳的選擇，然而模式匹配在整個檢測過程中需要花費大量時間，因此，模式匹配算法的性能將影響整個網(wǎng)絡(luò)信息監(jiān)控系統(tǒng)的工作效率。本文在AC算法的基礎(chǔ)上，結(jié)合BM算法，提出快速的多模式匹配算法，在匹配中，跳過無用的字符，使用匹配中失敗的信息，實現(xiàn)文本串的快速匹配，減少算法的時間復(fù)雜度。

1AC算法

AC算法是多模式匹配算法，利用有限自動機(jī)把字符比較轉(zhuǎn)化為狀態(tài)轉(zhuǎn)移。首先，對模式串集合預(yù)處理，構(gòu)成樹型有限狀態(tài)自動機(jī)，它包含一組狀態(tài)，每個狀態(tài)用一個數(shù)字來表示。狀態(tài)機(jī)讀取文本串中的字符，通過產(chǎn)生狀態(tài)轉(zhuǎn)移的方式或發(fā)送輸出來處理文本，只需掃描一次文本串就能夠找出與其匹配的模式串。

2BM算法

BM算法是一種精確字符串匹配算法。該算法將文本串和模式串的最左端對齊，然后從模式串的最后一個字符與文本串開始比較，若匹配失敗，模式串則向右滑動一段距離。

3快速的多模式匹配算法———N_AC_BM算法

為了提高速度，利用模式匹配失敗時所在的位置和距離，增加跳躍的距離，這就是快速的多模式匹配算法———N_AC_BM算法[1]。

3.1算法的基本思想給定一個文本串要查找模式串，從最右向左對模式串進(jìn)行匹配，若找到模式串尾字符，則再從右向左比較剩余字符，最后將指針跳過尾字符所對應(yīng)的距離。

3.2算法詳細(xì)描述詳細(xì)算法如下。

4實驗結(jié)果分析

為了驗證本算法，選5Mbit的一個文本串，與AC算法和BM算法進(jìn)行比較，測試環(huán)境為操作系統(tǒng)WinXP，CPU4．8GHz、內(nèi)存4GB。實驗結(jié)果如表1、表2所示。通過實驗可知：本文的算法，花費時間大約是BM算法的1／5，AC算法的1／3[4]。隨著模式串長度的增加、模式串?dāng)?shù)目的增多，本文所設(shè)計的算法所花時間更少有很大的優(yōu)勢。

5結(jié)束語

在網(wǎng)絡(luò)信息監(jiān)控中模式匹配的速度是非常重要的。本文的快速的模式匹配算法———N_AC_BM算法，結(jié)合有限狀態(tài)自動機(jī)的工作原理，利用單模式匹配的BM算法和多模式匹配的AC算法優(yōu)點，實現(xiàn)了一種快速的多模式匹配算法，N_AC_BM算法通過對匹配失效字符的判斷，減少了無效的跳轉(zhuǎn)和匹配。實驗證明，N_AC_BM算法大大提高了匹配速度，具有明顯的優(yōu)勢。

作者：雷赟 呂靜 單位：江西理工大學(xué) 圖書館 江西省圖書館