一種改進的KMP算法在不良網站信息過濾中的應用

摘 要：針對網絡信息過濾的特點和現實中人們對網絡信息純凈度的要求，提出了一種基于KMP字符串匹配算法，對不良網站信息進行過濾和相應的性能測試。在測試環境下，對100組非法網站進行過濾，得出對不良信息過濾查準率達到95%，查全率達到98%，通過對測試數據的分析和網絡吞吐量的測試結果表明，該方案所設計的系統性能基本能夠滿足實際需要。



關鍵詞：信息過濾； KMP算法； 模式匹配; 網絡吞吐量



中圖分類號：TN919.1-34; TP311

文獻標識碼：A

文章編號：1004-373X(2012)01-0110-03



Application of an improved KMP algorithm in bad website information filtering



DANG Hong-yun， JIANG Pin-qun， HE Ting-ting

(College of Electronic Engineering， Guangxi Normal University， Guilin 541004， China)



Abstract：

According to the characteristics of network information filtering and people′s requirement on the degree of purity of network information in reality， a KMP (Kunth-Morris-Pratt)-based string matching algorithm is introduced to filter the negative website information and test the corresponding performance. In the test environment， 100 groups of illegal websites were filtered. It is concluded that the filtering precision ratio on bad information has been reached 95% and recall ratio has been reached 98%. The analysis to the test data and the test results of network throughput show that the system performance designed by this scheme can basically meet the practical need.



Keywords： information filtering; KMP algorithm; pattern match; network throughput





收稿日期：2011-09-10

0 引 言

隨著網絡的日益普及和網絡信息總量的激增，當人們正享受網絡技術帶給我們美好生活的同時，也使某些不法分子通過網絡傳送一些不健康的非法信息，因此，建立一種積極主動的信息安全過濾系統已成為網絡安全領域中研究的熱點。

目前，信息過載、信息污染的問題正嚴重的困擾著用戶，簡單的信息檢索成為了整個網絡中數據出入的瓶頸。在網頁信息過濾領域，主要采用的方法有分級法、URL地址列表法和動態文本分析法，同時包過濾作為一種能選取用戶需要的信息、剔除用戶不需要的信息的有效方法應運而生。包過濾的關鍵技術包括網絡封裝的截獲和解析，而包過濾技術[1]的核心算法是字符串匹配算法，字符串匹配的效率直接影響數據包過濾[2]的能力。當前，較為有效的匹配算法有BF算法、KMP算法、BMH算法、SUNDAY算法和ZZL算法等。經過各類試驗證明，KMP算法雖然提出時間較早，但由于其可擴展性和易用性，仍然是目前應用較為廣泛的一種[3]。

1 KMP算法及改進策略

所謂KMP算法匹配技術，即用戶模板與文本的匹配技術。文本過濾的主要流程是首先根據用戶的信息需求，建立用戶需求模型，然后在相應的文本流中搜索符合用戶需求的文本，再利用反饋，改進需求模型。KMP算法的信息過濾模型如圖1所示。

圖1 信息過濾系統的一般模型

在整個信息過濾系統中，用戶需求模板的構建、信息的揭示、匹配算法和反饋機制是最為關鍵的部分。在現有技術條件下，全自動的信息過濾系統還處于試驗階段，為了提高實用性，往往會在這些關鍵部分進行必要的人工干預，把人工智能和機器學習的方法引入到信息過濾中，通過遺傳算法、神經網絡方法、K最近相鄰方法(KNN)和支持向量機(SVM)等方法，來判斷用戶信息需求與文檔的相似性，動態地反饋用戶需求的變化，提高過濾的效率。如對動態的信息集先作預處理、人工修改用戶需求模板等。

所謂字符串匹配就是指給定一組特定的字符串集合T，找出T中的字符串在主串S中的所有出現，如在文本S中查找到一個與模式串T相同的字符串，則模式串與文本匹配；如在文本T中未查找到一個與模式串S相同的字符串，則不匹配。KMP算法[4]從文本中逐個讀入字符，每讀入一個字符就更新相應變量，同時也是已讀入文本的后綴的最長字符串的長度，檢查是否存在一個可能的匹配，它是一種改進的字符串匹配算法，KMP算法的關鍵是根據給定的模式串T，定義一個next函數，數組next［j］表示當模式串中的第j個字符與主串中的該字符匹配失敗時，在模式中需重新與主串中該字符進行比較的字符的位置，next包含了模式串本身局部匹配的信息，得到next之后，便可繼續進行匹配。

下面給出簡單的例子來說明KMP經典算法匹配過程：例如把主串S=ABACABADAEACABAE與模式串T=ABAE進行匹配，按照KMP算法進行匹配，具體匹配過程如圖2所示[5]。

KMP算法的時間復雜度為O(m+n)，計算Q(r)的復雜度為O(m)。本文算法時間復雜度仍分兩部分進行討論:一是模式匹配算法中文本與模式的比較次數;二是根據模式串來計算Q(r)。由于KMP算法中Q(r)與其他的運算量相同，但其循環次數明顯減少，所以KMP算法被廣泛應用。

在KMP算法匹配過程中如果失配，不需回溯指針，而是利用已經得到的“部分匹配”結果將模式串向前滑動盡可能遠的一段距離，然后繼續進行比較。

通過KMP算法的滑動長度與實際經驗相結合，提出了相鄰位對比的KMP算法，盡量在不丟失匹配項的前提下增大滑動長度，可以有效提高匹配效率，算法流程如圖3所示[6]。

核心KMP算法程序：



While(比較未完)

{ 

If(S［j］!=T［j］)

{調用kmp算法確定滑動系數k;

使得S［j］==T［k］;

If((S［k-1］)!=T［j-1］)or (S［k+1］!=T［j+1］))

{ 向后滑動模式串長度，使得S［j+1］與T［1］對齊；}

else {模式串向后滑動j-k，使得S［j］與T［k］對齊；}

}

else {j++;}

}



該算法相對于KMP經典算法的優勢是在盡量不丟失匹配項的前提下在滑動長度上進行了調整，在相鄰位匹配不成功時，直接滑動整個模式串，而不是僅僅滑動j-k個長度，這樣可以更高的提高匹配效率。

圖3 改進后的KMP算法流程圖

2 系統設計的基本要求

2.1 系統的應用要求

(1) 系統應滿足人們對網絡使用的基本需要，并注重系統的可用性、可靠性和可維護性，整個系統長期可靠的運行，并達到操作過程中的直觀、方便、實用等要求。

(2) 采用KMP算法匹配過濾技術[7]，根據網絡上各網站信息特點把不良網站網址分為色情、非法娛樂、反動3類。所有Web信息在通過系統時，會把Web的URL信息與網址庫的URL進行比較，所有網址可以讓用戶很方便的增加、刪除和修改禁止訪問的URL地址，進而按規則過濾受屏蔽的網站。

(3) 系統管理員能夠在不改變系統運行的情況下對網絡活動進行實時的控制和管理，不管網絡設備的物理位置在何處，網絡都應該是可以控制的，而且管理員要能夠在頁面管理可以讓用戶很方便地增加、刪除和修改敏感關鍵字，從而限制瀏覽出現非法關鍵字的網頁。

2.2 系統的功能要求

系統主要通過調用KMP字符串匹配算法對在計算機屏幕出現的關鍵詞進行邏輯判斷，主要功能是在網絡鏈路層對Sock端口進行過濾和屏蔽，然后在網絡應用層對Web信息流根據語法和語義進行分析，按管理員制訂的不同規則進行實時監控，進而完成對100組不良網站的查殺。

2.3 主要技術

本文前臺開發工具為Visual Studio 2008，后臺利用Oracle建立樣本訓練庫，采用ADO.NET數據訪問技術進行數據庫互聯[8]，在應用層采用Windows Socket 2 SPI 標準的網絡接口技術。

3 系統的結構和設計

3.1 整體結構設計

局域網網頁信息過濾系統采用的是C/S模式，通過查詢Oracle數據庫的信息進行有選擇性的過濾，數據庫的信息是管理員預置的過濾信息，利用Winsock 2接口，使它工作在應用層，負責連接核心層驅動程序和高層應用程序，并為上層調用提供接口函數，當捕獲到的不良信息需要過濾時，在數據鏈路層、網絡層、傳輸層以及應用層分別使用改進后的KMP算法進行模式匹配，找到匹配項，則將數據丟棄；否則進行更深層次的匹配。在應用層，并不是將整個應用層數據進行匹配，而是從數據頭和數據尾取一定長度的數據分別進行匹配，進而縮短匹配時間，提高匹配效率。當捕獲到的不良信息需要過濾時，在數據鏈路層、網絡層、傳輸層以及應用層分別使用改進后的KMP算法進行模式匹配，找到匹配項，則將數據丟棄；否則進行更深層次的匹配。在應用層，并不是將整個應用層數據進行匹配，而是從數據頭和數據尾取一定長度的數據分別進行匹配，進而縮短匹配時間，提高匹配效率[9]。

3.2 系統界面設計

界面如圖4~圖7所示，有4個界面。用戶管理界面：該界面的主要功能是實現系統與用戶的交互，即它是用戶需要檢索過濾的不良網站進行操作的平臺；樣本庫訓練界面：該界面的主要作用是根據用戶的興趣通過Google，Baidu等搜索引擎獲得需要過濾的不良網站的樣本庫；過濾參數管理界面：該界面的主要作用是對當前用戶對信息過濾參數的一個可視化呈現[10]；過濾效果圖界面：該界面的主要功能是通過關鍵字設置、過濾網址設置和管理員設置來分別呈現過濾的效果，進而對信息過濾的評價指標查準率、查全率和過濾速度進行分析[11]。

4 結 語

本文設計是在KMP算法基礎上，提出了一種在模式串滑動時采用相鄰位對比方式來決定滑動長度的算法，并將其應用于網絡信息過濾技術中。主要用于過濾禁止瀏覽的網頁(網址)，從而達到信息過濾的目的。該算法應用在網絡信息過濾中，通過在應用層中采用Winsock 2 SPI技術，使其實現相對容易且靈活，CPU資源占有少，效率較好，提高了網絡安全性能，從而限制了用戶對不良網站的瀏覽。本文采用相對成熟的技術，系統易于管理，安全可靠，并具有較強的實用性、應用效果較為理想。

參 考 文 獻

［1］劉翌南.基于SPI的信息過濾的設計及實現［J］.長沙交通學院學報，2005，21(1):64-68.



［2］張敏.信息過濾系統模型的相關問題研究［J］.科技情報開發與經濟，2008(1):85-86.



［3］黃曉斌.網絡信息過濾原理與應用［M］.北京:北京圖書館出版社，2005.



［4］GARDNER Michael， DOBSON Judith， MILLER Brian. Implementation of a \"data filter\"for the UK national marine monitoring programme [J]. Accred. Qual. Assur.， 2002，7: 60-65.



［5］趙繼俊，胡啟秀，馮茜，等.基于規則匹配算法信息過濾系統的設計與實現［J］.陜西科技大學學報:自然科學版，2010，28(1):109-112.



［6］譚躍生，顧瑞春，段軍，等.改進的KMP算法在深度包過濾中的應用［J］.計算機應用，2007，27(6):217-218.



［7］鄒萍，紀沙.網絡信息過濾機制的研究［J］.哈爾濱師范大學自然科學學報，2008(2)：66-69，97.



［8］王小科.C#開發實戰寶典［M］.北京：清華大學出版社，2010.



［9］NEWELL SIMA C. User models and filtering agents for improved internet information retrieval [J]. User Modeling and User-adopted Interaction， 2005，7: 223-237.



［10］宋寶亞.基于數據挖掘的信息過濾系統的設計與實現［D］.濟南：山東師范大學，2006.



［11］石云輝，陳文剛.一種網頁信息過濾系統的設計［J］.計算機與信息技術，2008(8):95-96.



作者簡介：

黨紅云 女，1986年出生，陜西西安人，碩士研究生。主要研究方向為電路與系統、數據挖掘。