中文垃圾郵件過濾系統中的實時分詞算法設計

維普資訊

ｃ。州 ｒ Ｅ 譏ｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉ。 計算機工程與應用 ！型一—

中文垃圾郵件過濾系統中的實時分詞算法設計

申慶永，張建忠，何 云，楊 潔

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

南開大學計算機科學與技術系，天津３０００７１

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

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

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

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

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

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

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

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

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

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

摘 要：在基于內容的中文反垃圾郵件技術中，中文分詞是必不可少的一個環節。面對大規模的郵件訓練樣本和大負我的郵件服

務器．中文分詞算法的時間效率成為中文垃圾郵件過濾技術中的一個瓶頸。時此，提出一種應用在中文垃圾郵件過濾系統中的實

時分詞算法。該算法采用一種ＴＲＩＥ樹型結構作為詞典栽體并基于最大匹配的原則，同時，在實時分類階段結合ｈａｓｈ表進行特征

查詢．極大地提高了系統的時間效率。

關鍵詞：中文分詞；垃圾郵件；ＴＲＩＥ樹

文章編號：１００２—８３３１（２００７）０３—０１７９—０３ 文獻標識碼：Ａ 中圖分類號：ＴＰ３９３

ｌ 弓Ｉ言

需要。現有的很多中文分詞算法，雖然在準確率、歧義分析等方

１３益增多的垃圾郵件給人們的生產生活帶來了極大的不

面有一些改進，但是算法往往實現復雜，時間效率不高。面對大

便，造成了極大的人力物力資源的浪費。據統計，我國已成為全

規模的郵件訓練樣本和大負載的郵件服務器，中文分詞時間效

球第二大垃圾郵件受害國。中文垃圾郵件已經成為危害我國信

率成為中文郵件過濾系統的瓶頸。

息化發展的一個嚴重問題。

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

在眾多的反垃圾郵件技術中，基于內容的反垃圾郵件技術

不成熟）圈，在實現中文垃圾郵件過濾系統過程中，本文采用一種

成為發垃圾郵件的主流技術。基于內容的反垃圾郵件技術，一般

ＴＲＩＥ樹結構作為詞典載體，結合正向最大匹配原則，在保證較

是根據文本分類的原理，首先對已歸類的郵件樣本進行機器學

高的精度的同時極大地提高了分詞的時間效率，滿足了對大規

習，取得不同類別郵件的特征，然后對未分類的郵件作出類別判

模郵件集進行快速學習及郵件傳輸過程中實時處理的需要。

斷。這兩個階段分別稱為訓練階段和分類階段。作為針對中文垃

圾郵件的郵件過濾系統，不同于英文等其他語言的郵件處理系

２訓練階段的分詞算法

統．首先需要對郵件進行中文分詞．就是把中文的漢字序列切分

２．１詞典的樹型結構組織

成有意義的詞。它是機器翻譯、文獻標引、智能檢索、自然語言理

ＴＲＩＥ是一種樹型數據結構，用于存儲字符串，可以實現字

解與處理的基礎。也是中文文本分類的一個比較關鍵的環節川。

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

在中文垃圾郵件過濾系統中．分詞算法必須保證有一定的

鍵樹。面向英文的ＴＲＩＥ索引樹一般以２６個字母作為關鍵字．

時間效率。在訓練階段，系統要對大量的郵件樣本進行機器學

樹節點包含個數相同的指針。漢字不同于英文。不可能以所有

習。如果訓練階段的算法效率不高，必然需要消耗大量的時間

的漢字作為關鍵字構建樹節點。因此，一般面向中文的ＴＲＩＥ

和人力；同時，由于各式的垃圾郵件不斷出現，系統必須及時地

索引樹的節點應允許指針個數變化腳。但是由于每個樹節點中

將新類型的垃圾郵件加入訓練集中進行訓練，以便能夠盡快地

的關鍵字個數不同。構建樹節點和查找關鍵字（一般使用二分

識別出新類型的垃圾郵件。在實時分類階段，系統對分詞的時

查找）比較復雜。

間效率要求更高．以便滿足大負載郵件服務器實時處理郵件的

在中國大陸使用的中文信息，絕大部分都使用ＧＢ２３１２編

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

作者簡介：申慶永（１９８１一），男，碩士研究生，主要研究方向：網絡與信息安全；張建忠，副教授；何云，碩士研究生；楊沽，碩士研究生。