垃圾邮件关键字过滤算法

垃圾邮件关键字过滤算法 张溪 深圳市地铁集团运营分公司 【摘要】 本课题在对电子邮件原理和垃圾邮件的过滤方法进行研究的基础上，设计了一种垃 圾邮件过滤算法，并实现了垃圾邮件过滤系统。 本文主要介绍了关键字过滤算法的实现。关键字过滤是根据中文分词算法和关键字过滤 的词典的实际情况改进而来。 【关键词】垃圾邮件过滤;关键字过滤; 中图分类号：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，这个结构存储对应的关键字首字以及指向以该字 为首字的所有关键字数组的指针。定义如下： typedef struct tnode { int num; //以该字为首字的词条数目 KeyWordNode *first; //指向以该字为首字的关键字数组的指针 }TableNode; 我们还要定义一个结构 KeyWordNode来存储关键字和关键字的长度： typedef struct node { int len; //汉字的个数 string keyword; //关键字 }KeyWordNode; 定义： TableNode arr_preword[5]; //假设有最多 5个不同的首字 KeyWordNode arr_keyword[10]; //假设每个首字有最多 10个关键字 手动的给数组赋值： string pre_str = "好人广他免"; //所有的首字连成一个字符串 arr_preword[2].num = 3; arr_preword[2].first = arr_keyword; arr_keyword[0].len = 5; arr_keyword[0].keyword = "广告好代理"; arr_keyword[1].len = 3; arr_keyword[1].keyword = "广场的"; arr_keyword[2].len = 2; arr_keyword[2].keyword = "广告"; 图 1、本系统关键字过滤关键字结构示意图 4 关键字过滤算法的实现 关键匹配的过程，首先遍历待查询字符串，在遍历过程中，每一个字都与关键字首字序 列匹配，如果匹配失败则继续下一个字；如果匹配成功，也就说存在着以当前字为首字的关 键字，这时就要找到这些关键字，并把所有的关键字依次的与待查询字符串进行匹配，如果 成功则继续查找待查字符串中改关键字的下一个字，如果匹配失败则继续查找当前字的下一 个字。如此循环到待查询字符串结束。 关键字过滤算法实验分析 关键字过滤算法的实现过程在上文中已经有了详细的介绍，这里就不重复了。强调一点 就是中文分词算法目的是分词，因此根据内容语义的不同可以分出不用的词，也就可能出现 分词错误的情况，但是对于我们的关键字过滤算法来说就不存在“歧义”的问题，因为我们 的目的是对字符串匹配，并不在意其是否有具体的意义。所以我们就不用讨论其错误率，只 要考察其匹配的速度就可以了。 这里我们设待查询字符串的长度为 L，关键字首字序列的长度为 N，关键字的个数为M， 最后设我们调用的系统函数 find()的执行时间为 T。那么我们匹配过程最最糟糕的情况就是 O(LNM)。  对于查询函数 find()的执行时间为 T，在匹配一个关键字的时候，传入关键字的长度， 这样在待查询字符串中，只匹配到关键字的长度处即可，这样节省了很大一部分时间。 对于关键字的个数M，我们采用了最大长度匹配的原则，先匹配关键字长度长的，在 依次比较长度短的，这样也可以节省匹配时间。 结束语 本文对垃圾邮件和反垃圾邮件技术做了简单的介绍，并在此基础上讲述了我们实现 的这个系统的整个思路和系统工作流程。着重介绍了关键字过滤算法。通过实验的数据证明， 我们的这个系统基本上达到了预期的目标，实现了较高效率的垃圾邮件过滤，相比其他的反 垃圾邮件技术也有自己的优点。 垃圾邮件关键字过滤算法 作者： 张溪 作者单位： 深圳市地铁集团运营分公司 刊名： 城市建设理论研究（电子版） 英文刊名： ChengShi Jianshe LiLun Yan Jiu 年，卷(期)： 2013(16) 本文链接：http://d.wanfangdata.com.cn/Periodical_csjsllyj2013163908.aspx 垃圾邮件关键字过滤算法 【摘要】 引言 解决垃圾邮件关键字过滤的方法 1中文分词算法 2关键字过滤算法原理 3关键字过滤算法的数据结构 4关键字过滤算法的实现 关键字过滤算法实验分析 结束语