一种改进的KMP算法在不良网站信息过滤中的应用作者：党红云 蒋品 何婷婷来源：《现代电子技术》2012年第01期 摘 要：针对网络信息过滤的特点和现实中人们对网络信息纯净度的要求，提出了一种基于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)等方法，来判断用户信息需求与文档的相似性，动态地反馈用户需求的变化，提高过滤的效率。如对动态的信息集先作预处理、人工修改用户需求模板等。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议