垃圾邮件关键字过滤算法

垃圾邮件关键字过滤算法 【摘要】本课题在对电子邮件原理和垃圾邮件的过滤方法进行分析研究的基础上，设计了一种垃圾邮件过滤算法，并实现了垃圾邮件过滤系统。 本文主要介绍了关键字过滤算法的实现。关键字过滤是根据中文分词算法和关键字过滤的词典的实际情况改进而来。 【关键词】垃圾邮件过滤;关键字过滤; 中图分类号：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 关键字过滤算法的实现 关键匹配的过程，首先遍历待查询字符串，在遍历过程中，每一个字都与关键字首字序列匹配，如果匹配失败则继续下一个字；如果匹配成功，也就说存在着以当前字为首字的关键字，这时就要找到这些关键字，并把所有的关键字依次的与待查询字符串进行匹配，如果成功则继续查找待查字符串中改关键字的下一个字，如果匹配失败则继续查找当前字的下一个字。如此循环到待查询字符串结束。 关键字过滤算法实验分析 关键字过滤算法的实现过程在上文中已经有了详细的介绍，这里就不重复了。强调一点就是中文分词算法目的是分词，因此根据内容语义的不同可以分出不用的词，也就可能出现分词错误的情况，但是对于我们的关键字过滤算法来说就不存在“歧义”的问题，因为我们的目的是对字符串匹配，并不在意其是否有具体的意义。所以我们就不用讨论其错误率，只要考察其匹配的速度就可以了。 这里我们设待查询字符串的长度为L，关键字首字序列的长度为N，关键字的个数为M，最后设我们调用的系统函数find()的执行时间为T。那么我们匹配过程最最糟糕的情况就是O(LNM)。 对于查询函数find()的执行时间为T，在匹配一个关键字的时候，传入关键字的长度，这样在待查询字符串中，只匹配到关键字的长度处即可，这样节省了很大一部分时间。 对于关键字的个数M，我们采用了最大长度匹配的原则，先匹配关键字长度长的，在依次比较长度短的，这样也可以节省匹配时间。 结束语 本文对垃圾邮件和反垃圾邮件技术做了简单的介绍，并在此基础上讲述了我们实现的这个系统的整个思路和系统工作流程。着重介绍了关键字过滤算法。通过实验的数据证明，我们的这个系统基本上达到了预期的目标，实现了较高效率的垃圾邮件过滤，相比其他的反垃圾邮件技术也有自己的优点。第 5 页 共 5 页