摘 要：針對(duì)網(wǎng)絡(luò)信息過濾的特點(diǎn)和現(xiàn)實(shí)中人們對(duì)網(wǎng)絡(luò)信息純凈度的要求，提出了一種基于KMP字符串匹配算法，對(duì)不良網(wǎng)站信息進(jìn)行過濾和相應(yīng)的性能測(cè)試。在測(cè)試環(huán)境下，對(duì)100組非法網(wǎng)站進(jìn)行過濾，得出對(duì)不良信息過濾查準(zhǔn)率達(dá)到95%，查全率達(dá)到98%，通過對(duì)測(cè)試數(shù)據(jù)的分析和網(wǎng)絡(luò)吞吐量的測(cè)試結(jié)果表明，該方案所設(shè)計(jì)的系統(tǒng)性能基本能夠滿足實(shí)際需要。



關(guān)鍵詞：信息過濾； KMP算法； 模式匹配; 網(wǎng)絡(luò)吞吐量



中圖分類號(hào)：TN919.1-34; TP311

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：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 引 言

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

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

1 KMP算法及改進(jìn)策略

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

圖1 信息過濾系統(tǒng)的一般模型

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

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

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

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

在KMP算法匹配過程中如果失配，不需回溯指針，而是利用已經(jīng)得到的“部分匹配”結(jié)果將模式串向前滑動(dòng)盡可能遠(yuǎn)的一段距離，然后繼續(xù)進(jìn)行比較。

通過KMP算法的滑動(dòng)長(zhǎng)度與實(shí)際經(jīng)驗(yàn)相結(jié)合，提出了相鄰位對(duì)比的KMP算法，盡量在不丟失匹配項(xiàng)的前提下增大滑動(dòng)長(zhǎng)度，可以有效提高匹配效率，算法流程如圖3所示[6]。

核心KMP算法程序：



While(比較未完)

{ 

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

{調(diào)用kmp算法確定滑動(dòng)系數(shù)k;

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

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

{ 向后滑動(dòng)模式串長(zhǎng)度，使得S［j+1］與T［1］對(duì)齊；}

else {模式串向后滑動(dòng)j-k，使得S［j］與T［k］對(duì)齊；}

}

else {j++;}

}



該算法相對(duì)于KMP經(jīng)典算法的優(yōu)勢(shì)是在盡量不丟失匹配項(xiàng)的前提下在滑動(dòng)長(zhǎng)度上進(jìn)行了調(diào)整，在相鄰位匹配不成功時(shí)，直接滑動(dòng)整個(gè)模式串，而不是僅僅滑動(dòng)j-k個(gè)長(zhǎng)度，這樣可以更高的提高匹配效率。

圖3 改進(jìn)后的KMP算法流程圖

2 系統(tǒng)設(shè)計(jì)的基本要求

2.1 系統(tǒng)的應(yīng)用要求

(1) 系統(tǒng)應(yīng)滿足人們對(duì)網(wǎng)絡(luò)使用的基本需要，并注重系統(tǒng)的可用性、可靠性和可維護(hù)性，整個(gè)系統(tǒng)長(zhǎng)期可靠的運(yùn)行，并達(dá)到操作過程中的直觀、方便、實(shí)用等要求。

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

(3) 系統(tǒng)管理員能夠在不改變系統(tǒng)運(yùn)行的情況下對(duì)網(wǎng)絡(luò)活動(dòng)進(jìn)行實(shí)時(shí)的控制和管理，不管網(wǎng)絡(luò)設(shè)備的物理位置在何處，網(wǎng)絡(luò)都應(yīng)該是可以控制的，而且管理員要能夠在頁(yè)面管理可以讓用戶很方便地增加、刪除和修改敏感關(guān)鍵字，從而限制瀏覽出現(xiàn)非法關(guān)鍵字的網(wǎng)頁(yè)。

2.2 系統(tǒng)的功能要求

系統(tǒng)主要通過調(diào)用KMP字符串匹配算法對(duì)在計(jì)算機(jī)屏幕出現(xiàn)的關(guān)鍵詞進(jìn)行邏輯判斷，主要功能是在網(wǎng)絡(luò)鏈路層對(duì)Sock端口進(jìn)行過濾和屏蔽，然后在網(wǎng)絡(luò)應(yīng)用層對(duì)Web信息流根據(jù)語(yǔ)法和語(yǔ)義進(jìn)行分析，按管理員制訂的不同規(guī)則進(jìn)行實(shí)時(shí)監(jiān)控，進(jìn)而完成對(duì)100組不良網(wǎng)站的查殺。

2.3 主要技術(shù)

本文前臺(tái)開發(fā)工具為Visual Studio 2008，后臺(tái)利用Oracle建立樣本訓(xùn)練庫(kù)，采用ADO.NET數(shù)據(jù)訪問技術(shù)進(jìn)行數(shù)據(jù)庫(kù)互聯(lián)[8]，在應(yīng)用層采用Windows Socket 2 SPI 標(biāo)準(zhǔn)的網(wǎng)絡(luò)接口技術(shù)。

3 系統(tǒng)的結(jié)構(gòu)和設(shè)計(jì)

3.1 整體結(jié)構(gòu)設(shè)計(jì)

局域網(wǎng)網(wǎng)頁(yè)信息過濾系統(tǒng)采用的是C/S模式，通過查詢Oracle數(shù)據(jù)庫(kù)的信息進(jìn)行有選擇性的過濾，數(shù)據(jù)庫(kù)的信息是管理員預(yù)置的過濾信息，利用Winsock 2接口，使它工作在應(yīng)用層，負(fù)責(zé)連接核心層驅(qū)動(dòng)程序和高層應(yīng)用程序，并為上層調(diào)用提供接口函數(shù)，當(dāng)捕獲到的不良信息需要過濾時(shí)，在數(shù)據(jù)鏈路層、網(wǎng)絡(luò)層、傳輸層以及應(yīng)用層分別使用改進(jìn)后的KMP算法進(jìn)行模式匹配，找到匹配項(xiàng)，則將數(shù)據(jù)丟棄；否則進(jìn)行更深層次的匹配。在應(yīng)用層，并不是將整個(gè)應(yīng)用層數(shù)據(jù)進(jìn)行匹配，而是從數(shù)據(jù)頭和數(shù)據(jù)尾取一定長(zhǎng)度的數(shù)據(jù)分別進(jìn)行匹配，進(jìn)而縮短匹配時(shí)間，提高匹配效率。當(dāng)捕獲到的不良信息需要過濾時(shí)，在數(shù)據(jù)鏈路層、網(wǎng)絡(luò)層、傳輸層以及應(yīng)用層分別使用改進(jìn)后的KMP算法進(jìn)行模式匹配，找到匹配項(xiàng)，則將數(shù)據(jù)丟棄；否則進(jìn)行更深層次的匹配。在應(yīng)用層，并不是將整個(gè)應(yīng)用層數(shù)據(jù)進(jìn)行匹配，而是從數(shù)據(jù)頭和數(shù)據(jù)尾取一定長(zhǎng)度的數(shù)據(jù)分別進(jìn)行匹配，進(jìn)而縮短匹配時(shí)間，提高匹配效率[9]。

3.2 系統(tǒng)界面設(shè)計(jì)

界面如圖4~圖7所示，有4個(gè)界面。用戶管理界面：該界面的主要功能是實(shí)現(xiàn)系統(tǒng)與用戶的交互，即它是用戶需要檢索過濾的不良網(wǎng)站進(jìn)行操作的平臺(tái)；樣本庫(kù)訓(xùn)練界面：該界面的主要作用是根據(jù)用戶的興趣通過Google，Baidu等搜索引擎獲得需要過濾的不良網(wǎng)站的樣本庫(kù)；過濾參數(shù)管理界面：該界面的主要作用是對(duì)當(dāng)前用戶對(duì)信息過濾參數(shù)的一個(gè)可視化呈現(xiàn)[10]；過濾效果圖界面：該界面的主要功能是通過關(guān)鍵字設(shè)置、過濾網(wǎng)址設(shè)置和管理員設(shè)置來(lái)分別呈現(xiàn)過濾的效果，進(jìn)而對(duì)信息過濾的評(píng)價(jià)指標(biāo)查準(zhǔn)率、查全率和過濾速度進(jìn)行分析[11]。

4 結(jié) 語(yǔ)

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

參 考 文 獻(xiàn)

［1］劉翌南.基于SPI的信息過濾的設(shè)計(jì)及實(shí)現(xiàn)［J］.長(zhǎng)沙交通學(xué)院學(xué)報(bào)，2005，21(1):64-68.



［2］張敏.信息過濾系統(tǒng)模型的相關(guān)問題研究［J］.科技情報(bào)開發(fā)與經(jīng)濟(jì)，2008(1):85-86.



［3］黃曉斌.網(wǎng)絡(luò)信息過濾原理與應(yīng)用［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］趙繼俊，胡啟秀，馮茜，等.基于規(guī)則匹配算法信息過濾系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)［J］.陜西科技大學(xué)學(xué)報(bào):自然科學(xué)版，2010，28(1):109-112.



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



［7］鄒萍，紀(jì)沙.網(wǎng)絡(luò)信息過濾機(jī)制的研究［J］.哈爾濱師范大學(xué)自然科學(xué)學(xué)報(bào)，2008(2)：66-69，97.



［8］王小科.C#開發(fā)實(shí)戰(zhàn)寶典［M］.北京：清華大學(xué)出版社，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］宋寶亞.基于數(shù)據(jù)挖掘的信息過濾系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)［D］.濟(jì)南：山東師范大學(xué)，2006.



［11］石云輝，陳文剛.一種網(wǎng)頁(yè)信息過濾系統(tǒng)的設(shè)計(jì)［J］.計(jì)算機(jī)與信息技術(shù)，2008(8):95-96.



作者簡(jiǎn)介：

黨紅云 女，1986年出生，陜西西安人，碩士研究生。主要研究方向?yàn)殡娐放c系統(tǒng)、數(shù)據(jù)挖掘。