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