admin 随着互联网的不断发展，web已经成为信息制造、发布、加工和处理的主要平台，但是，互联网同时也面临着许多问题，使得互联网应用技术很难有效地应用。大量重复的网页数据就是其中的一个主要问题，如何对这些数据进行消重呢？今天，我给大家介绍一个方法：利用MD5加密算法给数据消重。
一、MD5加密算法思想及算法描述
1、算法思想
MD5加密算法的作用是让大容量信息在用数字签名软件签署私人密钥前被”压缩”成一种保密的格式（就是把一个任意长度的字节串变换成一定长的大整数）。对MD5加密算法简要的叙述为：
MD5以512位分组来处理输入的信息，且每一分组又被划分为16个32位子分组，经过了一系列的处理后，算法的输出由四个32位分组组成，将这四个32位分组级联后将生成一个128位散列值。本文就是使用MD5加密算法将农业供求数据不同的字段值经过处理得到一个128位的MD5编码存放于数据库的表中，并对该表建立索引，然后通过比较MD5编码迅速消除数据库中重复及相似的供求数据。
1.1、多重MD5加密算法
北京大学的天网使用了多重MD5加密算法，其基于这样一个基本思想：为每个文档计算出一组指纹，若两个文档拥有一定数量的相同指纹，则认为这两个文档的内容重叠性较高，也即两者是互为近似相似的。
假设数据集为N个网页，若我们为每个网页生成m个指纹，则对于N个网页两两比较以检测近似的时间代价就是0（m2N2）。这样的计算量，对于N为上亿个web页面的数据集来说是不可能完成的。
所以，一般的全文签名算法都会对数据作一些处理以降低算法的复杂度。有算法使用对＜文档标识，段标识，指纹＞三元组排序的方法避免了对所有网页作两两比较，使算法复杂度有所降低。但是该算法的空间复杂度和时间复杂度仍然是相当大的，若应用于海量的搜索引擎系统，仍然难以取得理想的效果。
天网的算法在生成每个网页的指纹的时候，对于这m个指纹进行了优先级排序。这样，在比较网页指纹组的时候，只对于在前pre（0＜＝pre＜＝rn）个位置上存在相同指纹的网页对进行两两比较。由于前几个指纹多数对应的是网页文本的标题块和主要正文块。该算法可以大大降低算法的复杂度，但是对于农业垂直搜索引擎要每天及时更新数据库来说，这也难以满足要求。
在考虑到农业垂直搜索引擎数据的特点后，发现农业数据完全重复的居多，所以本文采用单MD5指纹对完全相同的数据进行消重后，再对消重后的数据利用多重MD5指纹消重，且定义pre＝3，因为在本文设计的农业垂直搜索引擎中使用的文档数据前三个指纹对应的是文档标题，联系人以及联系方式，只有这三个字段一样的情况下我们才认为供求信息可能是相似的。
2、算法描述
根据前文的描述，本文提出了单MD5和多重MD5混合使用的算法，其算法流程如下：
第一步：单MD5指纹消重
①从数据库供求信息表（即存放原始供求信息数据的表）中读取供求数据各个字段值并连接生成字符串；
②对1中生成的字符串进行MD5编码，得到编码值，并写入数据库供求信息临时表中（该表比供求信息表多了一个字段即MD5编码字段）;
③对数据库中供求信息临时表建立索引;
④按照时间段在索引文件中进行RangeQuery查询产生结果集hits1(0);
⑤取出hits1(i)的第一条记录hits1(0)，在索引文件中进行TermQuery查询生生结果集hits2;
⑥如果hist2.length（）＞1，说明有重复记录，得到重复记录的ID，在数据中删除，并在索引文件中同步删除;
⑦将步骤6中重复记录中REG—TIME值最大的记录写入数据库以及索引文件中；
⑧i＋＋，返回步骤5中取下一条记录，直到hits1(i）记录为空结束。
第二步：多重MD5指纹消重
①从数据库供求信息表中读取供求数据需处理的各个字段值并连接生成字符串；
②对1中生成的字符串进行分词；
③对分词结果统计词频，按照词频高低重新生成一个新的字符串数组；
④对字符串数组进行MD5编码，得到MD5编码数组，写入数据库中供求信息临时表；
⑤对数据库中供求信息临时表建立索引；
⑥按照时间段在索引文件中进行RangeQuery查询产生结果集hits1；
⑦取出hits1（i）的第一条记录hits1(0)，按照MD5编码数组中前三个元素值为关键字在索引文件中进行TermQuery查询生成结果集hits2；
⑧如果hits2.length（）＞1，说明可能有相似记录，计算两条数据中含有的相同MD5指纹数s；
⑨如果s＞t（t为设定的阀值），则认为两条数据记录相似，得到相似记录的ID，在数据库中删除，并在索引文件中同步删除；
⑩i＋＋，返回步骤7中取下一条记录，直到hits1（i）记录为空结束。
二、实验结果及分析
本文从原始数据库中（网络爬虫采集到的，但是没有经过任何处理的数据）抽取70万条农业供求信息数据，利用本文介绍的方法进行试验，然后分别使用算法描述中的步骤一和步骤二进行独立实验，并比较这三种实验结果的查准率和召回率（也称查全率）以及响应时间。
1、查准率
查准率反映了的算法所发现的近似数据中有多少是正确的近似数据结果，假设算法检测到了Ｓ个重复数据记录，其中个正确结果，即符合我们对于近似数据的定义。则算法的查准率为Precision=P=So/s，计算查准率本文使用的方法为：在大数据的实验结果中进行采样，进行人工评测，取样本的准确率的平均值作为算法的查准率。
2、召回率
召回率是算法所发现的正确的近似数据记录占全部近似数据记录的百分比。计算召回率方法为：由于不能确定实际全部近似数据记录的个数，用算法发现的近似数据记录集合的大小与实验中所有算法得到的近似数据记录的并集的大小之比来代替查全率。假设算法检测到了个近似数据记录，而数据集中实际存在Ｓ个近似数据记录，则算法的召回率为：Recall=r=S0/S0。
3、实验结果
运行环境：PC机，Windows xp操作系统，JAVA实现算法。在我们的垂直搜索引擎“搜农”上实验得到结果如表一所示：
方法一为使用本文提出的先使用单MD5指纹进行完全相同数据记录消重，然后对消重后的数据库利用多重MD5指纹进行相似数据消重；
方法二为单独使用单MD5指纹进行消重；
方法三为单独使用多重MD5指纹进行消重。
为了方便对比作出查准率和召回率对比图，如图所示。
实验结果表明：在查准率和响应时间上，方法二最高；在召回率上，方法一最优；考虑到方法二不能有效消除近似的数据记录，而只能消除完全相同的数据记录，所以我们选用方法一。
利用MD5加密算法在数据处理阶段可以有效的消除冗余数据。结果表明该方法可以很好的提高检索质量。
小知识之MD5加密算法
MD5就是采用单向加密的加密算法，对于MD5而言，有两个特性是很重要的，第一是任意两段明文数据，加密以后的密文不能是相同的；第二是任意一段明文数据，经过加密以后，其结果必须永远是不变的。前者的意思是不可能有任意两段明文加密以后得到相同的密文，后者的意思是如果我们加密特定的数据，得到的密文一定是相同的。
