中文垃圾邮件过滤系统中的实时分词算法设计

维普资讯

ｃ。州 ｒ Ｅ 讥ｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉ。 计算机工程与应用 ！型一—

中文垃圾邮件过滤系统中的实时分词算法设计

申庆永，张建忠，何 云，杨 洁

ＳＨＥＮ Ｑｉｎｇ—ｙｏｎｇ．ＺＨＡＮＧ Ｊｉａｎ－ｚｂｏｎｇ，ＨＥ Ｙｕｎ，ＹＡＮＧ Ｊｉｅ

南开大学计算机科学与技术系，天津３０００７１

Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｎａｎｋａｉ Ｕｎｉｖｅｒｓｉｔｙ，Ｔｉａｎｊｉｎ ３０００７１，Ｃｈｉｎａ

Ｅ—ｍａｉｌ：ｓｑｙ＠ｍａｉｌ。ｎａｎｋａｉ。ｅｄｕ．ＣＲ

ＳＩｔＥＮ Ｑｌｎｇ－Ｙｏｎｇ．ＺＨＡＮＧ Ｊｉ￣ｍ－Ｚｈｏｎｇ，ＨＥ Ｙｕｎ，ｅｔ ａ１．Ａｌｇｏｒｉｔｈｍ ｏｆ Ｃｌ￣ａｅｓｅ ｗｏｒｄ ｓｅｇｍｅｎｔａｔｉｏｎ ｉｎ ａｎｔｉ一￥ｐａｍ ｓｙｓｔｅｍ・

Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ，２００７，４３（３）：１７９—１８１・

Ａｂｓｔｒａｃｔ：Ｃｈｉｎｅｓｅ ｗｏｒｄ ｓｅｇｍｅｎｔａｔｉｏｎ ｉｓ ａｌｌ ａｂｓｏｌｕｔｅｌｙ ｎｅｃｅｓｓａｒｙ ｓｔｅｐ ｉｎ ｔｈｅ Ｃｈｉｎｅｓｅ ａｎｔｉ—ｓｐａｒｅ ｔｅｃｈｎｏｌｏｇｉｅｓ ｂａｓｅｄ ｏｎ ｍａｉｌ ｃｏｎ－

ｔｅｎｔ．Ｔｈｅ ｅｇｉｃｉｅｎｅｙ ｏｆ ｗｏｒｄ ｓｅｇｍｅｎｔａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｉｓ ｂｅｃｏｍｉｎｇ ａ ｂｏｔｔｌｅｎｅｃｋ ｗｈｅｎ ｉｔ ｉｓ ｕｓｅｄ ｉｎ ｔｈｅ ｔｒａｉｎｉｎｇ ｏｆ ａｂｕｎｄａｎｔ ｍａｉｌ

ｓａｍｐｌｅｓ ｏｒ ｏｎ ｔｈｅ ｈｉｇｈ ｌｏａｄ ｍａｉｌ ｓｅｒｖｅｒ．Ａ ｒｅａｌ ｔｉｍｅ ａｌｇｏｒｉｔｈｍ ｉｓ ｐｒｏｐｏｓｅｄ ｈｅｒｅ。ｗｈｉｃｈ ＵＳｅＳ ａ ＴＲＩＥ ｓｔｒｕｃｔｕｒｅ ａｓ ｔｈｅ ｃａｒｒｉｅｒ ｏｆ

ｄｉｃｔｉｏｎａｒｙ．Ｂａｓｅｄ ｏｎ ｔｈｅ Ｍａｘｉｍｕｍ Ｍａｔｃｈｉｎｇ（ＭＭ）ｐｒｉｎｃｉｐｌｅ ａｎｄ ｃｏｍｂｉｎｅｄ ｗｉｔｈ ｔｈｅ ｈａｓｈ ｔａｂｌｅ ｏｆ ｗｏｒｄ ａｔｔｒｉｂｕｔｅｓ，ｔｈｉｓ ａｌｇｏｆｉｔｈｍ

ｉｍｐｒｏｖｅｓ ｔｈｅ ｅｆｆｉｃｉｅｎｃｙ ｏｆ ｔｈｅ ａｎｔｉ－ｓｐａｍ ｓｙｓｔｅｍ ｏｂｓｅｒｖａｂｌｙ．

Ｋｅｙ ｗｏｒｄｓ：Ｃｈｉｎｅｓｅ ＷＯｒｄ ｓｅｇｍｅｎｔａｔｉｏｎ；ｓｐａｍ；ＴＲＩＥ ｔｒｅｅ

摘 要：在基于内容的中文反垃圾邮件技术中，中文分词是必不可少的一个环节。面对大规模的邮件训练样本和大负我的邮件服

务器．中文分词算法的时间效率成为中文垃圾邮件过滤技术中的一个瓶颈。时此，提出一种应用在中文垃圾邮件过滤系统中的实

时分词算法。该算法采用一种ＴＲＩＥ树型结构作为词典栽体并基于最大匹配的原则，同时，在实时分类阶段结合ｈａｓｈ表进行特征

查询．极大地提高了系统的时间效率。

关键词：中文分词；垃圾邮件；ＴＲＩＥ树

文章编号：１００２—８３３１（２００７）０３—０１７９—０３ 文献标识码：Ａ 中图分类号：ＴＰ３９３

ｌ 弓Ｉ言

需要。现有的很多中文分词算法，虽然在准确率、歧义分析等方

１３益增多的垃圾邮件给人们的生产生活带来了极大的不

面有一些改进，但是算法往往实现复杂，时间效率不高。面对大

便，造成了极大的人力物力资源的浪费。据统计，我国已成为全

规模的邮件训练样本和大负载的邮件服务器，中文分词时间效

球第二大垃圾邮件受害国。中文垃圾邮件已经成为危害我国信

率成为中文邮件过滤系统的瓶颈。

息化发展的一个严重问题。

中文分词。需要有分词词典（也有无词典的分词方法，但尚

在众多的反垃圾邮件技术中，基于内容的反垃圾邮件技术

不成熟）圈，在实现中文垃圾邮件过滤系统过程中，本文采用一种

成为发垃圾邮件的主流技术。基于内容的反垃圾邮件技术，一般

ＴＲＩＥ树结构作为词典载体，结合正向最大匹配原则，在保证较

是根据文本分类的原理，首先对已归类的邮件样本进行机器学

高的精度的同时极大地提高了分词的时间效率，满足了对大规

习，取得不同类别邮件的特征，然后对未分类的邮件作出类别判

模邮件集进行快速学习及邮件传输过程中实时处理的需要。

断。这两个阶段分别称为训练阶段和分类阶段。作为针对中文垃

圾邮件的邮件过滤系统，不同于英文等其他语言的邮件处理系

２训练阶段的分词算法

统．首先需要对邮件进行中文分词．就是把中文的汉字序列切分

２．１词典的树型结构组织

成有意义的词。它是机器翻译、文献标引、智能检索、自然语言理

ＴＲＩＥ是一种树型数据结构，用于存储字符串，可以实现字

解与处理的基础。也是中文文本分类的一个比较关键的环节川。

符串的快速查找ｆ３Ｉ。ＴＲＩＥ索引树是以树的多重链表形式表示的

在中文垃圾邮件过滤系统中．分词算法必须保证有一定的

键树。面向英文的ＴＲＩＥ索引树一般以２６个字母作为关键字．

时间效率。在训练阶段，系统要对大量的邮件样本进行机器学

树节点包含个数相同的指针。汉字不同于英文。不可能以所有

习。如果训练阶段的算法效率不高，必然需要消耗大量的时间

的汉字作为关键字构建树节点。因此，一般面向中文的ＴＲＩＥ

和人力；同时，由于各式的垃圾邮件不断出现，系统必须及时地

索引树的节点应允许指针个数变化脚。但是由于每个树节点中

将新类型的垃圾邮件加入训练集中进行训练，以便能够尽快地

的关键字个数不同。构建树节点和查找关键字（一般使用二分

识别出新类型的垃圾邮件。在实时分类阶段，系统对分词的时

查找）比较复杂。

间效率要求更高．以便满足大负载邮件服务器实时处理邮件的

在中国大陆使用的中文信息，绝大部分都使用ＧＢ２３１２编

基金项目：天津市信息化项目（０４２０２３０１２）。

作者简介：申庆永（１９８１一），男，硕士研究生，主要研究方向：网络与信息安全；张建忠，副教授；何云，硕士研究生；杨沽，硕士研究生。