基于MD5算法计算数字指纹的网页消重算法简单而高效，在网页消重领域应用比较广泛。但是由于MD5算法是一种严格的信息加密算法，在文章内容变动很少的情况下得出的指纹结果完全不同，导致基于这种算法的网页消重技术召回率不是很高。提出了两种基于字集特征向量的网页消重改进算法，把文章内容映射到字集空间中去，计算字集空间距离来判断文章是否相似。提出的算法具有良好的泛化能力，段落中存在的调整语序和增删改个别字不会影响到对相似段落的识别，大大提高了网页消重算法的召回率。实验结果表明，算法的时间复杂度为[O(n)]，空间复杂度为[O(1)]，适合应用于大规模网页消重。李洪奇,冯海波,张伟,等:基于字集特征向量的网页消重改进算法2017,53(2)End it除2运算使用移位运算实现,其中,ke,表示机器码第jEND位的值,N表示常用汉字字数。基于字集特征向量的树如消重策略通过字集特征然后,通过哈希函数计算网页内容中屮所有字的位置,向量代替MD5算法计算出的网页数字指纹,可以很好并将该位置的字频加1。得出该网贞的字集特征向量。地解决召回率不高的问题。同时,提出的算法时间复杂根据雅克比系数公式(5)计算两个网页之间的距离度为Onm),其中n代表文章总字数,m代表常用汉字11×12个数,算法需要建立一个字频数组,空间复杂度为O(11+可以应用到大规模的网页消重领域最后判断lemn≥,如果为真则树贞相似,如果为假33某于机器码映射字集特征冋量算法的原理则网页不相似,其中θ表示-个经验值,本文建议取09与思想3.4算法描述通过对基亍字集特征向量算法的分析,基丁字集特该算法的伪代码如下征向量算法的运行时间主要消耗在比较查询每·个字Begin的空间位置上。所以,在此基础上提出了另一种基于汉Dim Freq1N] As Integer[]∥定义字节码频字机器码怏射字集特征向量的改进算法。Dim Freqln」 as Integer」研究MD5算法发现,该算法的原理是把输入的字Dim character as char∥定义获取的汉字字符符串转化为字节码后进行位运算,通过累加位运算的结For i=1 to 2果来计算得出数字指纹。在计算机休系里,汉字与英文Ifi=1Then读取第一个网页内容的不同在于每个汉字都有唯一的机器编码,汉字的机器Flse读取第二个网页内容编码在计算机中占2个字节。所以可以通过位运算把End if汉字散列到一维向量空间中,减少了查询每一个汉字位Do while没有读到文章结尾置的时间损耗,进一步提高算法的运行效率。hen character:=读取的汉字Dim size:=N宁集空间宇数基于该思想,算法的主要实现步骤如下Dim pos:=0/hash得到的位置首先,根据3.1节中的公式(1)定义字集特征向量,For 1=0 to 15该特征向量表示整篇网页的数字指纹。Dim temp: - character>>j)&1:每·个汉字字节码通过Hash函数获取所在的空间pos+=( temp*size)>>(j+1)位置,映射原理如图1所示End forN/4 N12 3N/4 NThen Freqllpos]+-EEnd ifEnd while图1映射原理图End forDim Len as double图1中,0~N表示整个汉字的字集空间,本文取Dim key1, key2, della3764个常用汉字,从机器编码低位开始映射,逐位二分For i=o to 16上一次划分的字集空间,如果该位为1则分到高半区delta: =Freq[i]" Freq2[]如果为0则分到低半区。以图1为例,第一位为1分配key l:=Freq*Freql[il到上半区[M2,N],第二位二分上半区,为0分配到低半key2: -Freq2[1*Freq2[i]区[NM2,3N4],其他位的操作类似,直到找到该字在字End for集空间中所在的唯一位置。Len: delta/(key 1+key2-delta射公式如公式(3)与公式(4)所示If Len≥日Then网页重复key=[bit1bit2,…,bin1…,bitd(3)End If其中,ke表示汉字的机器码,这里b1为低位bit16为高END位,bi;表示汉字字节码在第i位的进制位,为汉字基于杋器码映射特征向量的网贞消重算法,改进了字节码的位数,i∈1,16]。基于宇集向量网页消重算法比较查询每个汉字的空间kev, Ne]Hush(key=(4)位置时消耗大量时间的弊端,提高了算法的运行效率。+1该算法时间复杂度为O(n)。562017,53(2)Computer Engineering and4 pplications计算机工程与应用表1实验结果检出网页算法完全一致(250个)部分一致(250个)完全不同(500个)基于MD5的消重算法2500基于字集特征向量的消重算法249基于机器码映射字集特征向量消重算法基于正文结构树的消重算法2130基于特征码的消重算法2323表2结果统计使用算法正确率/%召回率行时间s基于MD5的消重算法99.9基于宇集特征向量的消重算法99999.8基于机器码射字集特征向量消重算法99999.8基于正文结构树的消重算法99.9457基于特祉码的消重算法964314实验验证错误率-检出完全不同网页数×100%4.1实验条件500召回率检出一致网页数+检出部分一致网页数4.1.1数据集100%500本文使川 WebZip工具下教新浪、搜狐新闻类体育其中基于正文结构树的消重算法在本次实验中是把段类、娱乐类共计500个网页作为样本集,通过计算机程落的首尾句的经MD5计算得到的数字指纹作为提取的序提取网页正文內容,复制结果屮的前250个网页内容特征码。由于本文在测试集中对首句改动较多,对正文作为測试集,改动后250个网页内容作为测试集,改动结构树消重算法有不利影响的方法为调整句子的语序、增删改个别的字词或句子,实验结果表明,基于字集特征向量的网页杳重算法再下载500个网页并提取正文作为测试集在正确率没有太大改变的情况下,召回率远远高于基于4.1.2运行环境Ⅵ冂5的网页查重算法;时间上远远低于基于正文结构开发语言:Java树的网页消重算法所消耗的时间。语言版本:JDK1.742.3算法运行时间对比操作系统:Wim764位实验把测试集1和测试集2合并为一个测试集,复制处理器: Intel i52.20GHz测试集2中的网页与样本集组成1000个网页数量级的内存:8GB新样本集。测试5种算法分别在50、100、150、200、42实验结果900、950、1000数量级的样本集下运行时间趋势。统计4.2.1实验步骤结果如图2所示把500个样本集网放到样本集H录下,把测试集基于字集特征向量的网页消重算法中未改动的250个网页和改动的250个网页放在测试集基于机器码玦射特征向量的网页消重算法1目录下,把500个完全不同的网页测试集放在测试集2基于MD5数字指纹的网页消重算法基于正文结构树的网页消重算法且录下。基于特征码的网页消重算法首先,把样本集目录和测试集1目录下的所有网页45000使用5科种算法两两比较,比较后相同的网页输入到检出40000树贞日录1下然后,把样本集目录和测试集2目录下的所有网页巴25000使用5种算法两两比较,比较后相同的网页输入到检出22网页目录2下最后分别统计检出网页目录1和目录2中检出相同100005000的网页数目。4.2.2算法正确率召回率对比品沉沉三实验得到的结果和统计如表1和表2所示。比较页数正确率=1-错误率图2五种算法运行时间对比李洪奇,冯海波,张伟,等:基于字集特征向量的网页消重改进算法2017,53(2)通过实验数据可以得出,本文提出的两种算法的时的民族大学,2008间复杂度都是线性的。验证了本文在上节屮分析得到[3]李志义,梁士金国内树贞去重技术研究:现状与总结[信的结论:基于宇集特征向量的刚贝消重算法的时间复杂息技术,2011,55(7):118-121度为Omm),基于机器码映射字集特征向量的时间复杂4熊忠阳,牙漫,张玉芳,等基丁网页止文结构和特征串的度为O(m),提出的两种算法都适合应用于大规模网页相似网页去重算法门计算机应用,2013,33(2):554-557消重领域。[5」吴平博,陈群秀,马亮,等基于特征牛的大规模中文网页基于字集特征向量的树贞消重算法的整体运行时快速去重算法研究[J中文信息学报,2003,2(17):28-35间是基于MD5算法和基于机器码映射字集特征向量算6姚漫基于文本聚类的网页消重算法研究北京:北京交法运行时间的8-10倍左右。但是基于机器码映射字集通大学,2008特征向量算法具有基丁字集特征向量算法高召回率的[7]周小平,黄家裕.刘连芳,等基于网页正文主题和摘要的优点。网页去重算法!广西科学院学报,2009,25(4):251-253[8]王建勇,谢正茂,雷鸣,等近似镜像网贞检测算法的饼究与评价门电子学报,200,28(71):130-1325结束语[9 Chowdhury A, Frieder O, Grossman D Collection statistics本文提出了两种基于字集向量的空间距离进行树for fast duplicate document detection [J]. ACM Transactions页消重的改进方法。实验证明,该方法可以高效地解决on Information Systems, 2002, 20(2):171-191网页存在噪声导致MDS算法不能很好地识别出相似网0韩冰人规模文本去重策略研究D]宁大连:人连理工页的问题。经大量数据验证,该算法可以应用在大规模大学,200的网页消重领域。算法还有待改进的地方有以下两点:[11 Manku g s. Jain A, Das Sarma A Detecting near-duplicates(1)停词在文章中的作用不大,可以考虑过滤停词突出for web crawling[C]/ International World Web Conference有意义的词的权重,进一步提高消重准确率;(2)由于在Conmittee, 2007本文算法并没有考虑稀有字与常用汉字的不同,而出于[12] Montanari d. Puglisi P L Near duplicate document deted常用汉字出现的频率较高,所以对稀有字和常用字的增tion for large information flowsIC] /International Con-删改会对整个字集空间距离产生不同的影响,下·步的ference on Availability and Security. Berlin: Springer, 2012:工作重点可以借鉴TFDF算法中的逆文档颊率思想来203-217进行改进[13]杨茂基于句子相似度的文本比对算法研究[D]成都:电子科技大学,2010参考文献[14]曹玉娟,牛振东,彭学平,等.一个基丁特祉向量的近似网[黄仁,冯胜,杨吉云,等基于正文结构和长句提取的网页页去重算法[中国索引,2009,7(1):11-14去重算法[计算机应川研究,2010,22(7):248924975」周杨基于关键长句及正文长度预分类的网页去重算法[2]范小源搜索引擎系统网页消重的研究与实现[D武汉:中究[软件导刊,2012,11(10):48-50(上接52贞)2014.[9] Qureshi M K, Patt Y N Utility-based cache partitioning:[14 Che S, Boyer M, Meng J, et al. Rodinia: a benchmarka low-overhead, high-performance, runtime mechanism tosuite for heterogeneous computinglcy/lIs wC, 2009partition shared caches[C]/MICRO-39, 2006: 423-432[15Parboilbenchmarksuite[eb/ol]-[2014-08-20].http://im[10 Zakharenko V, Aamodt T', Moshovos A Characterizing thepact.crhc. illinois. edu/parboil. phpperformance benefits of lused CPU/GPU systems using[16 Arora M.The architecture and evoltof CPU-GPuFusionSim[C]//DATE-13, 2013: 685-688systems for general purpose computing[J].IEEE Micro[11 Woo D h. Lee h H s.CompasS: a programmable data2012,32:4-16prefetcher using idle GPU shaders[C/ASPLOS 10, 2010[17 Lee C, Ro ww. Gaudiot J L Cooperative heterogeneous297-310computing for parallel processing on CPU-GPU hybrids[C!/[12 Yang Yi, Xiang Ping, Mantor M, et al. CPU-assisted GPGPU2012 16th Workshop on INTERACT, 2012on fused CPU-GPU architectures [C]//HPCA, 2012[18 Power J, Basu A, Gu J et al. Heterogeneous system[13 Power J, Hestness J. Orr M S. gem5-gpu: a heterogeneouscoherence for integrated CPU-GPU systems[Cy/MICRO-46CPU-GPU simulator[J]. IEEE Computer Architecture Letters20l3