网页网页检测

收稿日期:修返日期:基金项目:国家"&()"计划资助项目;国家"-')"计划资助项目;计算所知识创新科研课题资助项目改进的基于布尔模型的网页查重算法!
连/浩%,!
,刘/悦%,许洪波%,程学旗%(%0中国科学院计算技术研究所,北京%"""-";!
0中国科学院研究生院信息学院,北京%"""*&)摘/要:提出一种基于布尔模型的网页查重算法,利用布尔模型寻找适当的特征,建立索引以减少网页文档之间的比较次数.
实验验证了这种算法的性能,并取得了较好的效果.
关键词:网络;特征;布尔模型;相似网页中图法分类号:12)"%0'///文献标识码:.
///文章编号:(!
""()3456789:;29;@3;:;8:7AB.
6AC7:DE,9@;A%,+JNIOM4;$P7%01#)2).
3,+1&#($(4056(,3)*70&(#0($,8(&9&1!
!
+)22(5%&)#,;:56'5%(701))2,+1&59;@AA6;9BEAAA6;9BEA59;@9B476:45:A;$:Q;;B=;>59;@R.
B;5C;::VAA29;@!
/引言如今,网络中的数据呈现出爆炸式增长的趋势,以=;>为例,据可靠估计,其增长速度可以达到每六个月翻一番,!
""*年年底,最大的搜索引擎可以索引到的=;>网页的数目大概为-"亿X%""亿,这还只是=;>数据的一小部分.
微软曾作过一个试验,从网络中下载了%个网页,下载这些网页耗费了%%周的时间.
实验发现这些网页中有!
&0!
Y是相似网页,而且这些相似网页中还有!
!
0!
Y是完全重复的(一字不差);另外相似网页十分稳定地存在,一对相似的网页在%"个星期以后极有可能还是相似的网页.
从该实验可以看出,网络中存在大量的相似网页,它们降低了网页采集器的工作效率,浪费了一些数据挖掘工具的资源,使用户的工作效率下降,如何能够尽可能准确地去除这些重复的网页就是我们所面临的问题.
(/网页查重的起源早在!
"世纪("年代初,就有学者研究阻止大规模拷贝程序的技术和软件.
但是这只是用于复制检测,也就是剽窃检测,其目的在于知识产权的保护,Z::;B@:;7B在%&('年提出了基于属性计数法(.
::C7>4:;+A4B:7B)检测软件剽窃的方法.
但是,单纯的属性计数法抛弃了太多的程序结构信息,导致错误率太高.
[;C8A和=7@;[-]在%&&'年指出,对于仅仅使用属性计数法的检测算法,增加向量维数并不能降低错误率.
改进属性计数法的措施就是加入程序的结构信息,结合结构度量(\:C48:4C;F;:C78@),也称为控制流(+AB:CA6$S6AQ)来检测剽窃.
现在检测程序复制都是用各种方法综合属性计数和程序结构度量[%%X%)].
29C];C等人[%%]和+6A4D[%!
]分别对上述的各种程序复制检测方法作了详细的介绍和评述.
在二十年后,出现了自然语言的复制检测,这一部分就涉及到了网页查重技术.
%&&)年,.
C7^AB9大学的F9B>;C提出了一个\7S[']工具,用于在大规模文件系统中寻找内容相似的文件.
\7S工具提出了近似指纹(.
55CAT7E9:;W7B;C5C7B:@),就是用基于字符串匹配的方法来度量文件之间的相似性.
这个思路被后来很多的文本复制检测系统所采用.
%&&#年,\:9BSAC上探测文本复制的方法.
同期,贝尔实验室的J;7B:^;开发了_Z.
G.
[%']系统用于剽窃检测.
_Z.
G.
系统采用与\7S基本相同的方法,与之类似的方法还有,CA-,在!
@@:年提出的.
$&1将文章按!
个字一组分成一个&2%&!
,其中%是集合中文档的总数目,!
是这些文档中出现了&7,4对于重复的定义是:如果两篇文章之间有超过"DK的用词相同,而且长度相差不超过正负ADK,则这两篇文章就是重复的.
另外他认为现在对于网页查重的研究忽视了对正文部分结构差异的研究,他还试图将重复的网页按照正文部分的结构分成L*8-,;3,L54M>,43)>7,C79-,3)>7,F>8'9和%-N)09)>7五类.
L*8-,;3表示一对相似的网页正文部分第一段是完全一样的,而L54M>,43)>7则意味着正文的中间若干段是相似的.
O'2,H(>,Q>>25-)对于重复的定义就要简单得多:如果两篇文章之间有超过(个特征相同,则它们就是相似的.
由于1>7,4的定义需要明确找出两篇重复的网页中哪一篇是拷贝,所以在不考虑网页其他特征(如创建时间、站内链接关系等)的情况下,我们很难判断重复网页中哪一篇是拷贝,因此在利用布尔模型的查重算法中,对于重复的定义就是使用O'2/&,(随机取了其中的$!
%),硬件平台为@#&!
#AB,#C内存.
采取%值作为算法比较的依据:%7$D*D+((*:+),其中*为正确率,+为召回率.
对比算法为/0EF)0(特征的维数为$,)和基于标点符号的特征串算法.
实验结果如表%所示.
各算法的综合性能比较如图&所示.
6"实验分析由表%可以看到,C**5EG*(25与/0EF)0的%值相差不太大,效果稍微好一点,但是C**5EG*(25的速度几乎比/0EF)0快了&GHI3以上,效率比/0EF)0高一些.
这两种算法在扫描全文、提取特征和计算词频这部分是相同的,但是/0EF)0在文档两两比较时只是在判断全文长度时过滤了一次,而C**5EG*(25利用两篇文档之间不同的特征个数再过滤了一次,所以其文档两两之间的比较次数比/0EF)0少了很多,速度加快了一些.
基于标点符号的特征串算法只需要定位文章中标点符号的位置,无需扫描全文,但是它的代价是比较次数较多,随着语料集合的增加,比较的次数慢慢增多,速度也会逐渐下降,比较次数与语料大小成线性关系,这是该算法的主要瓶颈.
它的效果比C**5EG*(25和/0EF)0算法要差一些.
/0EF)0的正确率比C**5EG*(25稍高,如果将特征的维数取得更多,/0EF)0的正确率可以达到&,,J,但是效率会下降.
而C**5EG*(25就不存在这样的问题,如果需要提高正确率,只需要控制文档的二进制码异或后结果中为&的特征个数即可.
阈值改变了,但是文档之间的比较次数不会增加,所以效率不会下降太多.
基于标点符号的特征串算法只限于找到&,,J重复的文档(一字不差),所以有大量的重复文档它无法确定,其正确率为&,,J.
C**5EG*(25的召回率比/0EF)0稍高一些,由于C**5EG*(25判定重复的依据没有/0EF)0那么强势,所以它分辨KL/出来的重复文档肯定会比/0EF)0要多.
而且@4MN对于重复的定义原本就有缺陷:即使两篇文档有超过+个特征相同,在+不是文档特征总数的情况下,这两篇文档就不可能&,,J相似,所以使用C**5EG*(25必然会出现两篇文档被错误判断成重复的情况.
既然基于标点符号的特征串算法只能找到&,,J重复的文档,显然有大量稍作修改的重复文档它是无法确定的,这也是其召回率较低的原因.
微软的实验可以验证网络中的数据,虽然增长速度较快,但是不同的网页还是占了大部分,有;,J以上的网页是不同的.
如果能使用某种机制快速找出那些不同的网页,也就不需要两两计算文档之间的相似度了.
9"结论和展望本文提出了一种基于布尔模型的网页查重算法,利用布尔·]8;.
8$8]中文信息学报,ABBE,&C(A):AF#EG[E]鲍军鹏,沈钧毅,刘晓东,等自然语言文档复制检测研究综述[>]软件学报,ABBE,&H(&B):&CGE#&CIB[H]宋擒豹,沈钧毅数字商品非法复制和扩散的监测机制[>]计算机研究与发展,ABB&,EF(&):&A&#&AG[G]王建勇,谢正茂,雷鸣,等近似镜像网页检测算法的研究与评价[>]电子学报,ABBB,AF(增刊):&AD,&EB#&EA[I]@:8(4+J"38)38K93=35:+"354;38:L:+K4"35490;74=[,]M+.
#644)38K;.
9.
,V:+63:#@.
538:W,.
20%474673.
8@46-:83;=;1,.
=2*74+'5K.
+37-=;]$OOO!
+:8;:673.
8;.
8O)*6:73.
8,&DFD,EA(A):DH#DD[&A],5.
*K-MM5:K3:+3;=38P:7*+:5:8)M+.
K+:==38KL:8K*:K4;:'81U4+U34/487!
.
.
5;:8)!
46-8.
5.
K34;[Y]Y4;4:+6-@4=.
+:8#)::,9#BB#BG,%42:+7=487.
,V:+63:#@.
538:W,.
20%474673.
8@46-:83;=;:=34,:55:8P4:+#%*2536:74%474673.
8:=4;,53,53]1L]-772:6;:*6)X]^6;_]!
-4;3;],ABBB[G],9>48;48,Y98.
)K+:;;!
4=2.
+:5%:7:@:8:K4=487[,]$OOO!
S%O,&DDDEI#HH[I],-+3;73:89>48;48,Y36-:+)!
98.
)K+:;;,@36-:45%9.
.
!
-4!
9'LA%:7:@.
)45[>]1L]-772:6;:*6)X]^6;_]!
-4#;3;],ABBB[C]N:8KL*(:8K,!
:8K\.
8K,\*\:8K'T374=2.
+:5Y45:73.
8:5'5K4#(+:T:;4).
8T,%@[>]>.
*+8:5.
48;48,-+3;73:89,9:57483;93=.
8:L3K-7#N43K-7$8)4a38K.
.
-8!
-.
+87.
8,'()*59:77:+'P.
U45'22+.
:6-7.
@.
)45P.
/38!
4=2.
+:5%:7:(:;4;[,]!
-4&B7-$874+8:73.
8:590=#2.
;3*=.
8!
4=2.
+:5Y42+4;487:73.
8:8)Y4:;.
838K:8)7-4H7-$874+#8:73.
8:5,.
8]>.
*+8:5.
<9.
<7/:+4,&DDH,G(I):&E#&F[&E]N-:7:+4!
4=2.
+:5%:7:(:;4@:8:K4=48790;74=;[OT]1L]-7#72:73=46.
8;*576.
=],&DDF#BF#&G作者简介:王路帮(&DCH#),男,讲师,硕士,主要研究方向为数据库、知识库及Y.
*K-集理论等;汤庸(&DIH#),男,教授,博导,博士,主要研究方向为数据库、知识库与,9,N等.
·DE·第A期连b浩等:改进的基于布尔模型的网页查重算法bbb