1、垃圾邮件 Bloom Filter 过滤算法浅析【摘要】本课题在对电子邮件原理和垃圾邮件的过滤方法进行分析研究的基础上，设计了一种垃圾邮件过滤算法，并实现了垃圾邮件过滤系统。这个系统基于 Bloom Filter 的 LOAF 技术，通过 LOAF 把收到的邮件初步分为从高到低的 1，2，3 三个可信度等级，1 级表示是自己的好友发来的邮件，2 级表示是跟自己好友有联系的人发来的邮件，1、2 级邮件不可能是垃圾邮件。 本文主要介绍了 Bloom Filter 的基本原理及其实现。Bloom Filter是一种新的高效率的数据机构，是实现 LOAF 的基础。 【关键词】垃圾邮件过滤; Bloom
2、 Filter；LOAF; 中图分类号：F618.1 文献标识码：A 文章编号： 系统设计思路 随着垃圾邮件的泛滥，各种垃圾邮件过滤技术不断的出现和发展。通过对部分过滤技术的研究，我们设计并实现了这个系统。接下来我们看看系统工作的整个流程。 这个系统包括两部分，邮件发送端和邮件接收端。发送端的功能包括发送邮件、读取显示通讯录、添加联系人等。接收端的功能包括接收邮件、读取显示通讯录、邮件过滤、添加功能等。 Bloom Filter 实现的主要函数 1BFMembershipQuery()函数 BFMembershipQuery()函数的功能就是判断一个元素是不是在 Bloom Filter 数组
3、中，如果是则返回 1；不是则返回 0。需要传递三个参数为：Bloom Filter 数组 bf、带查询的元素 element 和元素长度 length。 首先，对 element 产生一个 SHA1 哈希函数地址。其次，与 bf 中的对应位进行比较。函数代码如下： int BFMembershipQuery(BloomFilter *bf, const unsigned char *element, unsigned length) int result = 1, i; /产生 SHA1 地址 unsigned *hashAddress = (unsigned *)malloc(sizeof(
4、unsigned) * bf-Hash_Num); if (!GenerateHashAddress(element, length, bf-Length, bf-Hash_Num, hashAddress) free(hashAddress); return 0; for (i = 0; i Hash_Num; i+) /对应位比较 if (!GetBits(unsigned *)bf-Bit_Array, hashAddressi, 1) result = 0; break; free(hashAddress); return result; 2BFInsert()函数 BFInsert(
5、)函数实现把一个元素插入 Bloom Filter 数组中，同样需要传递 Bloom Filter 数组 bf、带查询的元素 element 和元素长度length 三个参数。 插入过程也比较简单，首先，对 element 产生一个哈希地址，然后把在 bf 中对应位置 1，这样就完成了插入的操作，函数实现代码如下： int BFInsert(BloomFilter *bf, const unsigned char *element, unsigned length) int i; /产生 SHA1 地址 unsigned *hashAddress = (unsigned *)malloc(si
6、zeof(unsigned) * bf-Hash_Num); if (!GenerateHashAddress(element, length, bf-Length, bf-Hash_Num, hashAddress) free(hashAddress); return 0; for (i = 0; i Hash_Num; i+) /对应位置 1 SetBits(unsigned *)bf-Bit_Array, hashAddressi, 1, 1); free(hashAddress); return 1; 3Main()主函数 主函数的功能就是实现 Bloom Filter 的初始化、判断
7、以及插入。 在初始化这一步骤中，我们要设定 Bloom Filter 数组的大小numOfArray，以及哈希函数的个数 numOfHash。其中 numOfArray 必须是2 的整数次幂且，numOfArray 8，而 numOfHash 则根据实际情况设定1。这个例子中我们取 numOfArray = 1024，numOfHash =7。 判断元素 element 可以是字符串，汉字，也可以是特殊符号，用数组存储，根据一般性，限定数组长度为 20。 首先，我们要对 Bloom Filter 数组进行初始化，并加载测试数据，数据由另外的一个文档 test.txt 读入。 初始化 Bloom
8、 Filter 数组后，加载测试数据，并输出当前的 Bloom Filter 数组。 下面一段代码是主函数中的一个循环，在判断的同时也执行了插入操作： while(1) cout str_Test; cout “The elem you input is: “str_Testendl; /程序出口 if(!strcmp(str_Test,“-1“) exit(0); elem = (const unsigned char *)str_Test; unsigned str_Length = strlen(str_Test); if(BFMembershipQuery(bloomFilter, e
9、lem, str_Length)!=1) /判断元素 element 是否在 bf 中，如果在，则继续判断；如果不再，则插入 BFInsert(bloomFilter, elem, str_Length); cout“The elem you inputed is NOT in the BF! “endl; cout“ Insert the elem into the BF!“endl; for( int i=0;i1024;i+) /输出 bf 数组 coutBit_Array, i, 1); else cout“The element you input is in the BF!“end
10、l; 以上就完成了 Bloom Filter 的简单实现，在实现过程中，每次运行结束后 Bloom Filter 数组都会被释放，同时不保存 Bloom Filter 数组。Bloom Filter 实验分析 根据 Bloom Filter 的基本原理初步的实现了 Bloom Filter 的功能。经过实验证明了，Bloom Filter 的错误率跟 Bloom Filter 数组的大小和插入元素的多少有很大的关系。当 Bloom Filter 数组中的 0 和 1 的比例约为 1：1 时，错误率将达到较低值。数组的大小则要根据插入元素的多少和哈希函数的数目的具体情况来做出相应的改变。再一个，
11、相对与利用哈希表来判断元素是否在其中来说，Bloom Filter 节省了很大的空间，代价仅仅是很小的错误率。 结束语 本文对垃圾邮件和反垃圾邮件技术做了简单的介绍，并在此基础上讲述了我们实现的这个系统的整个思路和系统工作流程。本文着重介绍了 Bloom Filter 的基本原理及其实现。 但是随着垃圾邮件的增多和伪造邮件技术的发展，反垃圾邮件技术也要不断的进步。我们这个系统也有着很多的发展潜力。可以通过对LOAF 文档加密来加强对个人隐私的保护，对于第二层的关键字过滤可以实现自学习来随时的更新字典库，这样能更灵活、更快捷的实现反垃圾邮件这个目的。 当然，想要彻底的消除垃圾邮件是一项长期的工作，也是要社会的各个方面共同合作才能完成的目标。
