垃圾邮件关键字过滤算法.docx

垃圾邮件关键字过滤算法【摘要】本课题在对电子邮件原理和垃圾邮件的过滤方法进行分析研究的基础上设计了一种垃圾邮件过滤算法并实现了垃圾邮件过滤系统。本文主要介绍了关键字过滤算法的实现。关键字过滤是根据中文分词算法和关键字过滤的词典的实际情况改进而来。【关键词】垃圾邮件过滤;关键字过滤;中图分类号：F618.1文献标识码：A文章编号：引言随着Internet的普及电子邮件由于方便、快捷、低成本的特点逐渐取代了传统的通信方式成为现代社会主要的通讯方式之一。但是随之而来的垃圾邮件也给人们带来了许多的不便与烦恼而且这个问题也日益的严重。邮件过滤技术就是根据邮件的信头、发送方、接收方、内容等信息选择对自己有用或者排除对自己没用的信件的一种手段。对自己没用甚至是有害的邮件就是垃圾邮件。垃圾邮件过滤技术就是最大程度上的把这类邮件拒绝在自己的邮箱之外。然而垃圾邮件过滤技术也随着时间的推移不断的发展进步着。解决垃圾邮件关键字过滤的方法关键字过滤是基于规则过滤的一种人工的设定关键字集合通过对信件主题、内容等的匹配来过滤垃圾邮件的一种机械的过滤算法。1中文分词算法说到关键字过滤很容易就想到要对信件的内容的全文搜索。传统的做法是将一篇文章看作是字符串然后利用string类所提供的indexOf()方法进行通配看文章中是否有自己设定的关键字。如果有则过滤。假设待过滤的内容的字数是L关键字个数为N那么过滤的全部耗时为O(LN)。在对传统算法研究和改进的基础上有人提出了中文分词算法。这样就解决了传统算法在对全文通配时的浪费大量时间的问题。随着人们对中文分词的研究特别是2003年7月首届国际中文分词评测活动Bakeo开展以来中文自动分词技术有了一定的进步。目前。中文分词的方法主要分为三大类：基于字符串匹配的分词方法、基于统计的分词方法和基于理解的分词方法。国内学者在上述三类分词方法基础上展开了中文分词算法较深入的研究。刍海山等提出了一种基于词典的正向最大匹配和逆向最大匹配相结合的中文分词方案。可以高效、准确地实现中文文档的主题词条的抽取和词频统计[14]；应志伟等采用一种改进的最大匹配法提出了一种基于统计模型的算法来处理其中的多交集歧义字段可以切分出所有的交集歧义解决多音字的异读问题以及中文姓名的自动识别问题以达到文语转换的目的[15]．这些中文分词算法的应用领域较广、范围较大。2关键字过滤算法原理本系统使用的关键字过滤算法采用的就是中文分词算法中字符串匹配的分词方法的思路。不同的是通常基于字符串匹配的分词方法是从文本中切出一定长度的字符串与词典中的词相匹配若匹配成功则表明是一个词若匹配不成功则改变切出的字符串长度再匹配。直到匹配成功中文分词算法旨在分词。而本系统相对而言词库较小而且不需要分出文本中的词旨在匹配所以本系统中的分词方法也有所改变。本系统中遍历待查字符串查询关键字首字串当匹配时就遍历关键字表每个关键字都与待查字符串匹配。如果匹配成功则从成功词组的下一个字继续如果不成功则在原来字的下一个字继续。流程在下一节中将有详细的介绍。3关键字过滤算法的数据结构首先我们定义两个字符串str和pre_str定义str=“一个广告的代理厂家”是待查询的字符串pre_str=“好人广他免”是关键字首字的序列。其中以“广”开头的关键字为“广告好代理”、“广场的”、“广告”。其它的关键字我们先不与考虑。本系统中采用的是最大长度匹配[19]长度长的词排在前边。接下来我们定义一个结构TableNode这个结构存储对应的关键字首字以及指向以该字为首字的所有关键字数组的指针。定义如下：图1、本系统关键字过滤关键字结构示意图4关键字过滤算法的实现关键匹配的过程首先遍历待查询字符串在遍历过程中每一个字都与关键字首字序列匹配如果匹配失败则继续下一个字；如果匹配成功也就说存在着以当前字为首字的关键字这时就要找到这些关键字并把所有的关键字依次的与待查询字符串进行匹配如果成功则继续查找待查字符串中改关键字的下一个字如果匹配失败则继续查找当前字的下一个字。如此循环到待查询字符串结束。关键字过滤算法实验分析关键字过滤算法的实现过程在上文中已经有了详细的介绍这里就不重复了。强调一点就是中文分词算法目的是分词因此根据内容语义的不同可以分出不用的词也就可能出现分词错误的情况但是对于我们的关键字过滤算法来说就不存在“歧义”的问题因为我们的目的是对字符串匹配并不在意其是否有具体的意义。所以我们就不用讨论其错误率只要考察其匹配的速度就可以了