将KMP算法应用于反垃圾邮件的一点想法

前几天,也就是在考研复试的准备期间,我一个以前同学让我来帮忙完成一个基于内容的反垃圾邮件的程序,我当时也没上网查找,就灵光一现的想到:kmp算法不是虽然比较快,但不适用于文本组成字符较多(比如英文有26个字母,而中文每个字都是)的情况,那我索性将文本转为二进制呢,这样组成字符只有2个,岂不是会比较得非常快~~于是就接下了这个活,答应帮忙写比较程序。

今天,复试完后终于有时间来写程序啦~~手有点生,加磨磨蹭蹭,写了一个白天~~

不多说了,贴程序:

#include <iostream>
#include <vector>
#include <iomanip>
#include <stdio.h>
#include <fstream>
#include <string>
#include <bitset>
#include “kmp.h”

using namespace std;

int main()
{
ifstream in;
in.open(“key.txt”,ios::binary);
if(NULL==in){
return -1;//要返回错误代码
}
ofstream out;//需要注意ofstream只写
out.open(“keybin.txt”,ios::trunc);//如果文件已存在则先删除该文件
if(NULL==out){
return -1;//要返回错误代码
}
string key;
while(getline(in,key)){
for(int i=0;i<key.size()-1;i++){//去掉最后的回车
//cout<<bitset<sizeof(char)*8>(key[i]);
out<<bitset<sizeof(char)*8>(key[i]);//把文件转为二进制
}
//cout<<endl;
out<<endl;
}
out.close();
in.close();

in.open(“keybin.txt”,ios::binary);
if(NULL==in){
return -1;//要返回错误代码
}
out.open(“keyff.txt”,ios::trunc);//如果文件已存在则先删除该文件
if(NULL==out){
return -1;//要返回错误代码
}
while(getline(in,key)){
int *nextff;nextff=new int[key.size()];
FFail(key,nextff,key.size());//把二进制文件转为kmp函数
//cout<<key<<endl;
out<<key.size()<<” “;
for(int i=0;i<key.size();i++){
//cout<<nextff[i];
out<<nextff[i]<<” “;
}
//cout<<endl;
out<<endl;
}
out.close();
in.close();
/*******************************************************
以下这段程序可以单独列出,生成为判断邮件的exe
以上的程序可单独生成为处理垃圾邮件关键字的exe
*******************************************************/

in.open(“mail.txt”,ios::binary);
if(NULL==in){
return -1;//要返回错误代码
}
out.open(“mailbin.txt”,ios::trunc);//如果文件已存在则先删除该文件
if(NULL==out){
return -1;//要返回错误代码
}
while(getline(in,key)){
for(int i=0;i<key.size()-1;i++){//去掉最后的回车
out<<bitset<sizeof(char)*8>(key[i]);//把文件转为二进制
}
}
out.close();
in.close();

in.open(“mailbin.txt”,ios::binary);
if(NULL==in){
return -1;//要返回错误代码
}
string S;
getline(in,S);
in.close();

in.open(“keyff.txt”);
if(NULL==in){
return -1;//要返回错误代码
}
//string S=”1011010111000100101101111110011110111000111100011011010110110111101110011100010010110101101101111011100111000100101110101101110010110111101101001011100011010000101110111101100010111000101101001011010111000100110100101100001010110111111111101011010111000100″;
ifstream in1;
in1.open(“keybin.txt”);
if(NULL==in1){
return -1;//要返回错误代码
}
int *f,len,k=0;
while(getline(in1,key)){//cout<<key<<endl;
in>>len;//cout<<len;
f=new int[len];
for(int i=0;i<len;i++){in>>f[i];}
if(FindKMP(S,key,f)>-1) {cout<<“YES”<<endl;k=1;break;}
}
if(k==0) cout<<“NO”<<endl;
in1.close();
in.close();

return 0;
}

(暂时没时间去找在wordpress上发程序的插件~~先就这样将就吧~~)

主要的思想就是把放在key.txt文件里的关键字转换为二进制,

QQ截图20150401183423QQ截图20150401183753       然后再利用kmp算法(kmp.h见我前几篇文章,最近网站服务器老换,就贴一个我在点点网上的地址吧:http://zhangshengdong.diandian.com/post/2015-01-08/40065758687    对了,今天又在这个头文件里添加了一个kmp比较函数,等这篇文章写完记得加上~~)把keybin.txt计算出相应的kmp的改进型失败函数:

QQ截图20150401185124

(PS:第一个数字是这个关键字的FFail有多长~~)

然后再将mail.txt里的邮件文本转换成二进制,由于邮件可能由多段组成,所以在转换时将一个txt里的所有段并做一行,也就是一个txt里就是默认一封邮件~~

QQ截图20150401185559

QQ截图20150401185643

最后,就是在程序里读取keybin的一行和对应的keyff里的一行,和mailbin进行二进制的kmp比较,若匹配成功,则说明是垃圾邮件,输出YES;否则,输出NO。

QQ截图20150401185945

在这里是key中的第二个关键字“时代”,和mail中的时代相匹配,故判断为垃圾邮件~~

可以看到,我这里的运行耗时只有0.032s,这还是多关键字对一篇文章的扫描速度,足以证明kmp算法在组成字符较少情况下比较得优越性~~~

 

 

 

 

 

 

 

 

 

将KMP算法应用于反垃圾邮件的一点想法》上有4条评论

  1. Pingback引用通告: BZ编程小组 作品 | BZ编程小组

  2. Pingback引用通告: 飞机大战 | BZ编程小组

发表评论

电子邮件地址不会被公开。 必填项已用*标注