搜索引擎开发实践第十三讲文档排重课件

,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第一级,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,搜索引擎开发实践,第十三讲文档排重,主讲人：,罗刚,luogang,概 述,语义指纹,SimHash,基于,SimHash,的文档排重,作业：实现网页排重,什么是近似重复网页,?,内容相同，但是文档的少部分不同,广告,计数器,时间戳,不同的标题,文档,ID,文档,1,文档,2,标题,北大清华硕士不嫁的“最牛征婚女”,1,米,4,专科女征婚,求,1,米,8,硕士男,应征者如云,内容,24,岁的罗玉凤，在上海街头发放了,1300,份征婚传单。传单上写了近乎苛刻的条件，要求男方北大或清华硕士，身高,1,米,76,至,1,米,83,之间，东部沿海户籍。而罗玉凤本人，只有,1,米,46,，中文大专学历，重庆綦江人。,此事经网络曝光后，引起了很多人的兴趣。“每天都有打电话、发短信求证，或者是应征。”罗玉凤说，她觉得满意的却寥寥无几，“到目前为止只有,2,个，都还不是特别满意”。,24,岁的罗玉凤，在上海街头发放了,1300,份征婚传单。传单上写了近乎苛刻的条件，要求男方北大或清华硕士，身高,1,米,76,至,1,米,83,之间，东部沿海户籍。而罗玉凤本人，只有,1,米,46,，中文大专学历，重庆綦江人。,此事经网络曝光后，引起了很多人的兴趣。“每天都有打电话、发短信求证，或者是应征。”罗玉凤说，她觉得满意的却寥寥无几，“到目前为止只有,2,个，都还不是特别满意”。,为什么要去除近似重复网页,为什么需要检测近似重复,?,节省存储空间,改进搜索体验,(,节约用户的时间,),互联网存在大量的重复内容，有研究显示，其中有,30%,的网页内容重复。抄袭论文的情况也经常发生，文本去重类似的技术还可以用在抄袭检测上。,爬虫架构简化版,Web,索引,HTML,文档,Web,近似重复,?,遍历链接,新抓取的文档,一个文档,整个索引,插入,垃圾,No,Yes,语义指纹,(,fingerprint,),每个文档产生一个f位的语义指纹,MD5,方法的语义指纹无法找出特征近似的文档。例如，对于两个文档，如果两个文档相似，但这两个文档的,MD5,值却是完全不同的。关键字的微小差别会导致,MD5,的散列值差异巨大。这是,MD5,算法中的雪崩效应,(avalanche effect),的结果。输入中一位的变化，散列结果中将有一半以上的位改变。,如果两个相似文档的语义指纹只相差几位或更少，这样的语义指纹叫做,SimHash,。,两个文档是近似重复文档，如果它们的语义指纹最多差,k,位,Google,的实验表明,f=64, k=3,取得不错的效果，我们的实验表明,SimHash,生成方法对排重准确度有重要影响,Simhash,文档,w,1,w,2,w,n,特征,权重,100110,w,1,散列码,权重,110000,w,2,001001,w,n,w,1,-w,1,-w,1,w,1,w,1,-w,1,w,2,w,2,-w,2,-w,2,-w,2,-w,2,-w,n,-w,n,w,n,-w,n,-w,n,w,n,按列加,13,108,-22,-5,-32,55,符号函数,110001,语义指纹,理解,SimHash,假设可以得到文档的一系列的特征，每个特征有不同的重要度。计算文档对应的,SimHash,值的方法是把每个特征的,Hash,值叠加到一起形成一个,SimHash,。,可以把特征权重看成特征在,SimHash,结果的每一位上的投票权。权重大的特征的投票权大，权重小的特征投票权小。所以权重大的特征更有可能影响文档的,SimHash,值中的很多位，而权重小的特征影响文档的,SimHash,值位数很少。,根据特征生成,64,位的,SimHash,public static long,simHash(String,features,int, weights),int,hist,= new int64;/,创建直方图,for(int,i=0;i,features.length;+i,),long,featureHash,=,stringHash(featuresi,);/,生成特征的,散列,码,int,weight =,weightsi,;,/*,更新直方图 *,/,for (,int,c=0; c64; c+),int,fWeight,= (,feature,Hash,histc, +=,fWeight,;,/*,从直方图计算位向量 *,/,long,simHash,=0;,for (,int,c=0; c=0)?1:0);/,符号函数,t = c;,simHash |= t ;,return simHash;,生成特征的散列码,要生成好的,SimHash,编码，就要让完全不同的特征差别尽量大，而相似的特征差别比较小。,特征是枚举类型，比如只有两个可能的取值，例如是,Open,和,Close,。,Open,返回二进制位全是,1,的哈希编码，而,Close,则返回二进制位全是,0,的哈希编码。需要为指定的枚举值生成尽量不一样的哈希编码。,考虑中文字符的编码范围计算中文字符串的散列编码,生成枚举特征的散列码,/,输入枚举值，返回对应的,SimHash,值,public static long,getSimHash(MatterType,matter),int,b=1; /,记录用多少位编码可以表示一个枚举类型的集合,int,x=2;,while(x,MatterType.values().length,),b+;,x = x1;,long,simHash,=,matter.ordinal,();,int,end = 64/b;,for(int,i=0;i,end;+i,),simHash,=,simHash, b; /,枚举值按枚举类型总个数向左移位,simHash,+=,matter.ordinal,(); /,取得枚举值对应的整数值,return,simHash,;/,返回枚举值的,SimHash,值,中文字符的散列码,public static,int,byte2int(byte b) /,把字节转换成整数,return (b ,private static,int,MAX_CN_CODE = 6768;/,最大中文编码,private static,int,MAX_CODE = 6768+117;/,最大编码,/,取得中文字符的散列编码，每个中文字符用尽量小的正整数表示,public static,int,getHashCode(char,c) throws,UnsupportedEncodingException,String s =,String.valueOf(c,);,int,maxValue,= 6768;,byte b = s.getBytes(gb2312);,if(b.length,=2),int,index = (byte2int(b0) - 176) * 94 + (byte2int(b1) - 161);,return index;,else,if(b.length,=1),int,index = byte2int(b0) - 9 + MAX_CN_CODE;,return index;,return c;,中文字符串的散列码,/,取得中文字符串的散列码,public static long,getSimHash(String,input) throws,UnsupportedEncodingException,int,b=13; /,记录用多少位二进制编码可以表示一个中文字符,long,simHash,= getHashCode(input.charAt(0);,int,maxBit,= b;,for(int,i=1;i,input.length();+i,),simHash,*= MAX_CODE; /,把汉字串看成是,MAX_CODE,进制的,simHash,+=,getHashCode(input.charAt(i,);,maxBit,+= b;,long,origialValue,=,simHash,;,for(int,i=0;i=(64/maxBit);+i),simHash,=,simHash,maxBit,;,simHash,+=,origialValue,;,return,simHash,;,海明距离问题,SimHash,:,查找近似重复文档转换成查找最多差,k,位的语义指纹,给出一个,f,位的指纹集合,F,和一个指纹,fg,，鉴别出,F,中是否存在与,fg,只有,k,位差异的指纹。,穷举探查探查法,扩展指纹,fg,扩展指纹集合,F,分而治之法,有限状态机？,扩展待查指纹,排好序的,语义指纹,集合,S,64,位,Q,所有的,Q,:,hd(,Q,Q,)k,=3,相等查找,( ) probes!,64,3,逐次探查法,-,生成,相似语义指纹,long,fingerPrint,= 1L; /,语义指纹,int, indices; /,组合数生成的一种组合结果,/,生成差,2,位的语义指纹,CombinationGenerator,x = new CombinationGenerator(64, 2);,int,count =0; /,计数器,while (,x.hasMore,() ,indices =,x.getNext,();/,取得组合数生成结果,long,simFP,=,fingerPrint,;,for (,int,i = 0; i ,indices.length,; i+) ,simFP,=,simFP, 1L ,indicesi,;/,翻转对应的位,System.out.println(Long.toBinaryString(simFP,);/,打印相似语义指纹,+count;,逐次探查法查找过程,public,boolean,containSim(long,fingerPrint,int,k) /,输入要查找的语义指纹和,k,值，如果找到相似的语义指纹则返回真，否则返回假,if(contains(fingerPrint,)/,首先用二分法直接查找语义指纹,return true;,/,然后用逐次探查法查找,int indices;,for(int,ki,=1;ki=,k;+ki,)/,找差,1,位直到差,k,位的,CombinationGenerator,x = new CombinationGenerator(64,ki,);,while (,x.hasMore,() ,indices =,x.getNext,();,long,simFP,=,fingerPrint,;/,存放相似的语义指纹,for (,int,i = 0; i ,indices.length,; i+) ,simFP,=,simFP, 1L ,indicesi,;,if(contains(simFP,)/,查找相似语义指纹,return true;,return false;,扩展指纹集合,语义指纹,集合,S,64,位,Q,相等查找,S:,与,S,最多,k,位差别的所有,语义指纹,(Sort),|S| ,|S|,( ),64,3,SimHash,排重流程,查询文档,提取特征,生成,SimHash,文档数据库,提取语义指纹,语义指纹库,海明距离,指定阈值,判为重复,是,无重复,否,查询语义指纹库,快速查找近似的方法,观察到的情况：,整个表中排列组合的部分很少，不太可能出现例如：一批,8,位,SimHash,，前,4,位都一样，但后,4,位出现,16,种,0-1,组合的情况。,整个表在前,d,位,0-1,分布不会有很多的重复。,Q,Q,海明距离,(Q,Q) = 3,精确匹配,!,分而治之方法,-,准备,把问题分解成更小的几个子问题，降低问题需要处理的数据规模。利用空间（原空间的,t,倍）和并行计算换时间。分治法查找海明距离在,k,以内的语义指纹算法步骤如下：,先复制原表,T,为,t,份：,T,1,T,2,T,t,。,每个,T,i,都关联一个整数,p,i,和一个置换函数,i,，置换函数负责把来源于表,T,的,p,i,个二进制位换到高位上。,应用置换函数,i,到相应的,T,i,表上，然后对,T,i,进行排序。,分而治之方法,-,查找,然后对每一个,T,i,和要匹配的指纹,F,、海明距离,k,做如下运算：使用指纹,F,通过置换函数,i,生成,的,F,的高,p,i,位检索，找出,T,i,中高,p,i,位相同的集合，在检索出的集合中比较剩下的,f-p,i,位，找出海明距离小于或等于,k,的指纹。,最后合并所有,T,i,中检索出的结果。,F,F,i,p,i,f,-p,i,分而治之例子,在,S,中的语义指纹,A,B,C,D,64,位,16,位,A,B,C,D,64,位,Q,Q1,Q2,Q3,Q4,Q1,Q2,Q3,Q4,在,16,位上的,精确搜索,准备表,public static,boolean,isLessThanUnsigned(long,n1, long n2) ,return (n1 n2) (n1 0) != (n2 0);,static Comparator comp = new Comparator(),public int compare(SimHashData o1, SimHashData o2),if(o1.q=o2.q) return 0;,return (isLessThanUnsigned(o1.q,o2.q) ? 1: -1;,; /,比较无符号,64,位,public void sort() /,对四个表排序,t2.clear();t3.clear();t4.clear();,for(SimHashData,simHash:t1),long t =,Long.rotateLeft(simHash.q, 16);,t2.add(new,SimHashData(t,simHash.no,);,t =,Long.rotateLeft(t, 16);,t3.add(new,SimHashData(t,simHash.no,);,t = Long.rotateLeft(t, 16);,t4.add(new SimHashData(t,simHash.no);,Collections.sort(t1, comp);,Collections.sort(t2, comp);,Collections.sort(t3, comp);,Collections.sort(t4, comp);,查找,-,探查某个表,public Span,probe(ArrayList, t, long key) /,返回匹配区间,int,low = 0;/,采用折半查找的方式实现,int,high =,t.size,() - 1;,while (low 1;,Long,midVal,=,t.get(mid).q,;,int,cmp,=,compHpare(midVal, key);/,比较高位，也就是高,16,位做精确匹配,if (,cmp, 0),high = mid - 1;,else /,已找到，扩展匹配区间,int,matchStart,= mid;,int,matchEnd,= mid;,while (,matchStart, 0) ,midVal,=,t.get(matchStart,- 1).q;,if (,compHpare(midVal, key) = 0) ,-,matchStart,;, else ,break;,while (,matchEnd, (,t.size,() - 1) ,midVal,=,t.get(matchEnd,+ 1).q;,if (,compHpare(midVal, key) = 0) ,+,matchEnd,;, else ,break;,return new,Span(matchStart,matchEnd,);,return null; /,没找到,查找,-,选择出差别在,k,位的语义指纹集合,/,从,Span,找出最多差,k,位的语义指纹集合,public,ArrayList,getSim(ArrayList, t, Span s,/,区间,long,fingerPrint,/,待查找的语义指纹,int,k/,差,k,位,) ,ArrayList, result = new,ArrayList,();,for (,int,i =,s.getStart,(); i =,s.getEnd,(); +i) ,SimHashData,data =,t.get(i,);,long q =,data.q,;,if (,BitUtil.diffIn(fingerPrint, q, k) /,fingerPrint,和,q,的海明距离是否在,k,位以内,result.add(data,);,return result;,查找,4,个表,public,HashSet,getSimSet(long,fingerPrint,int,k) ,HashSet,retAll,= new,HashSet,();,Span s1 = probe(t1,fingerPrint,);,if (s1 != null) ,ArrayList, ret1 = getSim(t1, s1,fingerPrint, k);/,找第一个表,retAll.addAll(ret1);,long q2 =,Long.rotateLeft(fingerPrint, 16);,Span s2 = probe(t2, q2);,if (s2 != null) ,ArrayList, ret2 = getSim(t2, s2, q2, k); /,找第二个表,retAll.addAll(ret2);,long q3 = Long.rotateLeft(q2, 16);,Span s3 = probe(t3, q3);,if (s3 != null) ,ArrayList, ret3 = getSim(t3, s3, q3, k); /,找第三个表,retAll.addAll(ret3);,long q4 = Long.rotateLeft(q3, 16);,Span s4 = probe(t4, q4);,if (s4 != null) ,ArrayList, ret4 = getSim(t4, s4, q4, k); /,找第四个表,retAll.addAll(ret4);,return,retAll,;,局限,仅能在网页下载后实现，因此它无助于降低抓取过程中的网络带宽浪费。,解决方法：爬虫公开排重结果？,作业,实现网页排重,感谢您对猎兔搜索的支持,!,http:/,