1、搜索引擎开发实践第十三讲文档排重主讲人：罗刚概概 述述l语义指纹语义指纹lSimHashSimHashl基于基于SimHashSimHash的文档排重的文档排重l作业：实现网页排重作业：实现网页排重什么是近似重复网页?内容相同，但是文档的少部分不同内容相同，但是文档的少部分不同广告计数器时间戳不同的标题文档ID文档1文档2标题北大清华硕士不嫁的“最牛征婚女”1米4专科女征婚 求1米8硕士男 应征者如云内容24岁的罗玉凤，在上海街头发放了1300份征婚传单。传单上写了近乎苛刻的条件，要求男方北大或清华硕士，身高1米76至1米83之间，东部沿海户籍。而罗玉凤本人，只有1米46，中文大专学历，重庆綦
2、江人。此事经网络曝光后，引起了很多人的兴趣。“每天都有打电话、发短信求证，或者是应征。”罗玉凤说，她觉得满意的却寥寥无几，“到目前为止只有2个，都还不是特别满意”。24岁的罗玉凤，在上海街头发放了1300份征婚传单。传单上写了近乎苛刻的条件，要求男方北大或清华硕士，身高1米76至1米83之间，东部沿海户籍。而罗玉凤本人，只有1米46，中文大专学历，重庆綦江人。此事经网络曝光后，引起了很多人的兴趣。“每天都有打电话、发短信求证，或者是应征。”罗玉凤说，她觉得满意的却寥寥无几，“到目前为止只有2个，都还不是特别满意”。为什么要去除近似重复网页为什么需要检测近似重复为什么需要检测近似重复?节省存储空
3、间改进搜索体验(节约用户的时间)互联网存在大量的重复内容，有研究显示，其中有互联网存在大量的重复内容，有研究显示，其中有30%30%的网页内容重的网页内容重复。抄袭论文的情况也经常发生，文本去重类似的技术还可以用在抄复。抄袭论文的情况也经常发生，文本去重类似的技术还可以用在抄袭检测上。袭检测上。爬虫架构简化版Web索引HTML文档Web近似重复?遍历链接新抓取的文档一个文档整个索引插入垃圾语义指纹(fingerprint)l每个文档产生一个每个文档产生一个f f位的语义指纹位的语义指纹lMD5MD5方法的语义指纹无法找出特征近似的文档。例如，对于两个文方法的语义指纹无法找出特征近似的文档。例如
4、，对于两个文档，如果两个文档相似，但这两个文档的档，如果两个文档相似，但这两个文档的MD5MD5值却是完全不同的。关值却是完全不同的。关键字的微小差别会导致键字的微小差别会导致MD5MD5的散列值差异巨大。这是的散列值差异巨大。这是MD5MD5算法中的雪算法中的雪崩效应崩效应(avalanche effect)(avalanche effect)的结果。输入中一位的变化，散列结果中将的结果。输入中一位的变化，散列结果中将有一半以上的位改变。有一半以上的位改变。l如果两个相似文档的语义指纹只相差几位或更少，这样的语义指纹如果两个相似文档的语义指纹只相差几位或更少，这样的语义指纹叫做叫做SimHa
5、shSimHash。l两个文档是近似重复文档，如果它们的语义指纹最多差两个文档是近似重复文档，如果它们的语义指纹最多差k k位位lGoogleGoogle的实验表明的实验表明f=64,k=3f=64,k=3取得不错的效果，我们的实验表明取得不错的效果，我们的实验表明SimHashSimHash生成方法对排重准确度有重要影响生成方法对排重准确度有重要影响Simhash文档w1w2wn特征,权重100110w1散列码,权重110000w2001001wnw1-w1-w1 w1 w1-w1w2 w2-w2-w2-w2 -w2-wn-wn wn-wn-wn wn按列加13,108,-22,-5,-32
6、,55符号函数110001语义指纹理解SimHash假设可以得到文档的一系列的特征，每个特征有不同的重要度。计算假设可以得到文档的一系列的特征，每个特征有不同的重要度。计算文档对应的文档对应的SimHashSimHash值的方法是把每个特征的值的方法是把每个特征的HashHash值叠加到一起形成值叠加到一起形成一个一个SimHashSimHash。可以把特征权重看成特征在可以把特征权重看成特征在SimHashSimHash结果的每一位上的投票权。权重结果的每一位上的投票权。权重大的特征的投票权大，权重小的特征投票权小。所以权重大的特征更大的特征的投票权大，权重小的特征投票权小。所以权重大的特征
7、更有可能影响文档的有可能影响文档的SimHashSimHash值中的很多位，而权重小的特征影响文档值中的很多位，而权重小的特征影响文档的的SimHashSimHash值位数很少。值位数很少。根据特征生成64位的SimHashpublic static long public static long simHash(StringsimHash(String features,intfeatures,int weights)weights)intint histhist=new int64;/=new int64;/创建直方图创建直方图for(intfor(int i=0;i i=0;ifeatu
8、res.length;+ifeatures.length;+i)long long featureHashfeatureHash=stringHash(featuresistringHash(featuresi);/);/生成特征的散列码生成特征的散列码intint weight=weight=weightsiweightsi;/*更新直方图更新直方图 */for(for(intint c=0;c64;c+)c=0;c64;c+)intint fWeightfWeight=(=(featureHashfeatureHash&(1 c)=0?-weight:weight;&(1 c)=0?-we
9、ight:weight;histchistc+=+=fWeightfWeight;/*从直方图计算位向量从直方图计算位向量 */long long simHashsimHash=0;=0;for(for(intint c=0;c64;c+)c=0;c=0)?1:0);/long t=(histc=0)?1:0);/符号函数符号函数t=c;t=c;simHash|=t;simHash|=t;return simHash;return simHash;生成特征的散列码要生成好的要生成好的SimHashSimHash编码，就要让完全不同的特征差别尽量大，而相编码，就要让完全不同的特征差别尽量大，而相
10、似的特征差别比较小。似的特征差别比较小。特征是枚举类型，比如只有两个可能的取值，例如是Open和Close。Open返回二进制位全是1的哈希编码，而Close则返回二进制位全是0的哈希编码。需要为指定的枚举值生成尽量不一样的哈希编码。考虑中文字符的编码范围计算中文字符串的散列编码生成枚举特征的散列码/输入枚举值，返回对应的输入枚举值，返回对应的SimHashSimHash值值public static long public static long getSimHash(MatterTypegetSimHash(MatterType matter)matter)intint b=1;/b=1;
11、/记录用多少位编码可以表示一个枚举类型的集合记录用多少位编码可以表示一个枚举类型的集合intint x=2;x=2;while(xwhile(x MatterType.values().lengthMatterType.values().length)b+;b+;x=x1;x=x1;long long simHashsimHash=matter.ordinalmatter.ordinal();();intint end=64/b;end=64/b;for(intfor(int i=0;i i=0;iend;+iend;+i)simHashsimHash=simHashsimHash b;/b;
12、/枚举值按枚举类型总个数向左移位枚举值按枚举类型总个数向左移位simHashsimHash+=+=matter.ordinalmatter.ordinal();/();/取得枚举值对应的整数值取得枚举值对应的整数值 return return simHashsimHash;/;/返回枚举值的返回枚举值的SimHashSimHash值值 中文字符的散列码public static public static intint byte2int(byte b)/byte2int(byte b)/把字节转换成整数把字节转换成整数return(b&0 xff);return(b&0 xff);privat
13、e static private static intint MAX_CN_CODE=6768;/MAX_CN_CODE=6768;/最大中文编码最大中文编码private static private static intint MAX_CODE=6768+117;/MAX_CODE=6768+117;/最大编码最大编码/取得中文字符的散列编码，每个中文字符用尽量小的正整数表示取得中文字符的散列编码，每个中文字符用尽量小的正整数表示public static public static intint getHashCode(chargetHashCode(char c)throws c)th
14、rows UnsupportedEncodingExceptionUnsupportedEncodingException String s=String s=String.valueOf(cString.valueOf(c););intint maxValuemaxValue=6768;=6768;byte b=s.getBytes(gb2312);byte b=s.getBytes(gb2312);if(b.lengthif(b.length=2)=2)intint index=(byte2int(b0)-176)index=(byte2int(b0)-176)*94 +(byte2int
15、(b1)-161);94 +(byte2int(b1)-161);return index;return index;else else if(b.lengthif(b.length=1)=1)intint index=byte2int(b0)-9+MAX_CN_CODE;index=byte2int(b0)-9+MAX_CN_CODE;return index;return index;return c;return c;中文字符串的散列码/取得中文字符串的散列码取得中文字符串的散列码public static long public static long getSimHash(Strin
16、ggetSimHash(String input)throws input)throws UnsupportedEncodingExceptionUnsupportedEncodingException intint b=13;/b=13;/记录用多少位二进制编码可以表示一个中文字符记录用多少位二进制编码可以表示一个中文字符long long simHashsimHash=getHashCode(input.charAt(0);=getHashCode(input.charAt(0);intint maxBitmaxBit=b;=b;for(intfor(int i=1;i i=1;iinpu
17、t.length();+iinput.length();+i)simHashsimHash *=MAX_CODE;/=MAX_CODE;/把汉字串看成是把汉字串看成是MAX_CODEMAX_CODE进制的进制的simHashsimHash+=+=getHashCode(input.charAt(igetHashCode(input.charAt(i););maxBitmaxBit+=b;+=b;long long origialValueorigialValue=simHashsimHash;for(intfor(int i=0;i=(64/maxBit);+i)i=0;i=(64/maxBi
18、t);+i)simHashsimHash=simHashsimHash maxBitmaxBit;simHashsimHash+=+=origialValueorigialValue;return return simHashsimHash;海明距离问题lSimHashSimHash:查找近似重复文档转换成查找最多差查找近似重复文档转换成查找最多差k k位的语义指纹位的语义指纹l给出一个给出一个f f位的指纹集合位的指纹集合F F和一个指纹和一个指纹fg fg，鉴别出，鉴别出F F中是否存在与中是否存在与fg fg只只有有k k位差异的指纹。位差异的指纹。l穷举探查探查法穷举探查探查法l扩展指
19、纹fgl扩展指纹集合Fl分而治之法分而治之法l有限状态机？有限状态机？扩展待查指纹排好序的语义指纹集合S64位 Q所有的 Q:hd(Q,Q)k=3相等查找逐次探查法-生成相似语义指纹long long fingerPrintfingerPrint=1L;/=1L;/语义指纹语义指纹intint indices;/indices;/组合数生成的一种组合结果组合数生成的一种组合结果/生成差生成差2 2位的语义指纹位的语义指纹CombinationGeneratorCombinationGenerator x=new CombinationGenerator(64,2);x=new Combinat
20、ionGenerator(64,2);intint count=0;/count=0;/计数器计数器while(while(x.hasMorex.hasMore()()indices=indices=x.getNextx.getNext();/();/取得组合数生成结果取得组合数生成结果long long simFPsimFP=fingerPrintfingerPrint;for(for(intint i=0;i i=0;i indices.lengthindices.length;i+);i+)simFPsimFP=simFPsimFP 1L 1L indicesiindicesi;/;/翻
21、转对应的位翻转对应的位 System.out.println(Long.toBinaryString(simFPSystem.out.println(Long.toBinaryString(simFP);/);/打印相似语义指纹打印相似语义指纹+count;+count;逐次探查法查找过程 public public booleanboolean containSim(longcontainSim(long fingerPrint,intfingerPrint,int k)/k)/输入要查找的语义指纹和输入要查找的语义指纹和k k值，如果找到相似的语义指纹则返回真，否则返回假值，如果找到相似的
22、语义指纹则返回真，否则返回假if(contains(fingerPrintif(contains(fingerPrint)/)/首先用二分法直接查找语义指纹首先用二分法直接查找语义指纹return true;return true;/然后用逐次探查法查找然后用逐次探查法查找int indices;int indices;for(intfor(int ki ki=1;ki=1;ki=k;+kik;+ki)/)/找差找差1 1位直到差位直到差k k位的位的CombinationGeneratorCombinationGenerator x=new CombinationGenerator(64,x
23、=new CombinationGenerator(64,ki ki););while(while(x.hasMorex.hasMore()()indices=indices=x.getNextx.getNext();();long long simFPsimFP=fingerPrintfingerPrint;/;/存放相似的语义指纹存放相似的语义指纹for(for(intint i=0;i i=0;i indices.lengthindices.length;i+);i+)simFPsimFP=simFPsimFP 1L 1L indicesiindicesi;if(contains(sim
24、FPif(contains(simFP)/)/查找相似语义指纹查找相似语义指纹return true;return true;return false;return false;扩展指纹集合语义指纹集合S64位 Q相等查找S:与S最多k位差别的所有语义指纹(Sort)SimHash排重流程查询文档提取特征生成SimHash文档数据库提取语义指纹语义指纹库海明距离指定阈值判为重复是无重复否查询语义指纹库快速查找近似的方法观察到的情况：观察到的情况：1.1.整个表中排列组合的部分很少，不太可能出现例如：一批整个表中排列组合的部分很少，不太可能出现例如：一批8 8位位SimHashSimHash，前
25、，前4 4位都一样，但后位都一样，但后4 4位出现位出现1616种种0-10-1组合的情况。组合的情况。2.2.整个表在前整个表在前d d位位0-10-1分布不会有很多的重复。分布不会有很多的重复。QQ海明距离(Q,Q)=3精确匹配!分而治之方法-准备把问题分解成更小的几个子问题，降低问题需要处理的数据规模。利把问题分解成更小的几个子问题，降低问题需要处理的数据规模。利用空间（原空间的用空间（原空间的t t倍）和并行计算换时间。分治法查找海明距离在倍）和并行计算换时间。分治法查找海明距离在k k以内的语义指纹算法步骤如下：以内的语义指纹算法步骤如下：1.1.先复制原表先复制原表T T为为t t
26、份：份：T T1 1,T,T2 2,T Tt t。2.2.每个每个T Ti i都关联一个整数都关联一个整数p pi i和一个置换函数和一个置换函数 i i，置换函数负责把来源于，置换函数负责把来源于表表T T的的p pi i个二进制位换到高位上。个二进制位换到高位上。3.3.应用置换函数应用置换函数 i i到相应的到相应的T Ti i表上，然后对表上，然后对T Ti i进行排序。进行排序。分而治之方法-查找1.1.然后对每一个然后对每一个T Ti i和要匹配的指纹和要匹配的指纹F F、海明距离、海明距离k k做如下运算：使用指做如下运算：使用指纹纹F F通过置换函数通过置换函数 i i 生成生
27、成的的F F的高的高p pi i位检索，找出位检索，找出T Ti i中高中高p pi i位相同的集位相同的集合，在检索出的集合中比较剩下的合，在检索出的集合中比较剩下的f-pf-pi i位，找出海明距离小于或等于位，找出海明距离小于或等于k k的指纹。的指纹。2.2.最后合并所有最后合并所有T Ti i中检索出的结果。中检索出的结果。FFipif-pi分而治之例子在S中的语义指纹ABCD64位16位ABCD64位 QQ1Q2Q3Q4Q1Q2Q3Q4在16位上的精确搜索准备表public static public static booleanboolean isLessThanUnsigned
28、(longisLessThanUnsigned(long n1,long n2)n1,long n2)return(n1 n2)(n1 0)!=(n2 0);return(n1 n2)(n1 0)!=(n2 0);static Comparatorstatic Comparator comp=new Comparator comp=new Comparator()()public int compare(SimHashData o1,SimHashData o2)public int compare(SimHashData o1,SimHashData o2)if(o1.q=o2.q)retu
29、rn 0;if(o1.q=o2.q)return 0;return(isLessThanUnsigned(o1.q,o2.q)?1:-1;return(isLessThanUnsigned(o1.q,o2.q)?1:-1;/;/比较无符号比较无符号6464位位public void sort()/public void sort()/对四个表排序对四个表排序t2.clear();t2.clear();t3.clear();t3.clear();t4.clear();t4.clear();for(SimHashDatafor(SimHashData simHash:t1)simHash:t1)l
30、ong t=long t=Long.rotateLeft(simHash.qLong.rotateLeft(simHash.q,16);,16);t2.add(new t2.add(new SimHashData(t,simHash.noSimHashData(t,simHash.no););t=t=Long.rotateLeft(tLong.rotateLeft(t,16);,16);t3.add(new t3.add(new SimHashData(t,simHash.noSimHashData(t,simHash.no););t=Long.rotateLeft(t,16);t=Long.
31、rotateLeft(t,16);t4.add(new SimHashData(t,simHash.no);t4.add(new SimHashData(t,simHash.no);Collections.sort(t1,comp);Collections.sort(t1,comp);Collections.sort(t2,comp);Collections.sort(t2,comp);Collections.sort(t3,comp);Collections.sort(t3,comp);Collections.sort(t4,comp);Collections.sort(t4,comp);查
32、找-探查某个表public Span public Span probe(ArrayListprobe(ArrayList t,long key)/t,long key)/返回匹配区间返回匹配区间intint low=0;/low=0;/采用折半查找的方式实现采用折半查找的方式实现intint high=high=t.sizet.size()-1;()-1;while(low=high)while(low 1;mid=(low+high)1;Long Long midValmidVal=t.get(mid).qt.get(mid).q;intint cmpcmp=compHpare(midVa
33、lcompHpare(midVal,key);/,key);/比较高位，也就是高比较高位，也就是高1616位做精确匹配位做精确匹配if(if(cmpcmp 0)0)0)high=mid-1;high=mid-1;else/else/已找到，扩展匹配区间已找到，扩展匹配区间intint matchStartmatchStart=mid;=mid;intint matchEndmatchEnd=mid;=mid;while(while(matchStartmatchStart 0)0)midValmidVal=t.get(matchStartt.get(matchStart-1).q;-1).q;
34、if(if(compHpare(midValcompHpare(midVal,key)=0),key)=0)-matchStartmatchStart;else else break;break;while(while(matchEndmatchEnd (t.sizet.size()-1)()-1)midValmidVal=t.get(matchEndt.get(matchEnd+1).q;+1).q;if(if(compHpare(midValcompHpare(midVal,key)=0),key)=0)+matchEndmatchEnd;else else break;break;ret
35、urn new return new Span(matchStartSpan(matchStart,matchEndmatchEnd););return null;/return null;/没找到没找到 查找-选择出差别在k位的语义指纹集合/从从SpanSpan找出最多差找出最多差k k位的语义指纹集合位的语义指纹集合public public ArrayListArrayList getSim(ArrayListgetSim(ArrayList t,Span s,/t,Span s,/区间区间 long long fingerPrintfingerPrint,/,/待查找的语义指纹待查找的
36、语义指纹 intint k/k/差差k k位位 )ArrayListArrayList result=new result=new ArrayListArrayList();();for(for(intint i=i=s.getStarts.getStart();i=();i=s.getEnds.getEnd();+i)();+i)SimHashDataSimHashData data=data=t.get(it.get(i););long q=long q=data.qdata.q;if(if(BitUtil.diffIn(fingerPrintBitUtil.diffIn(fingerPr
37、int,q,k)/,q,k)/fingerPrintfingerPrint和和q q的海明距离是否在的海明距离是否在k k位以内位以内result.add(dataresult.add(data););return result;return result;查找4个表public public HashSetHashSet getSimSet(longgetSimSet(long fingerPrintfingerPrint,intint k)k)HashSetHashSet retAllretAll=new =new HashSetHashSet();();Span s1=probe(t1,
38、Span s1=probe(t1,fingerPrintfingerPrint););if(s1!=null)if(s1!=null)ArrayListArrayList ret1=getSim(t1,s1,ret1=getSim(t1,s1,fingerPrintfingerPrint,k);/,k);/找第一个表找第一个表retAll.addAll(ret1);retAll.addAll(ret1);long q2=long q2=Long.rotateLeft(fingerPrintLong.rotateLeft(fingerPrint,16);,16);Span s2=probe(t2
39、,q2);Span s2=probe(t2,q2);if(s2!=null)if(s2!=null)ArrayListArrayList ret2=getSim(t2,s2,q2,k);/ret2=getSim(t2,s2,q2,k);/找第二个表找第二个表retAll.addAll(ret2);retAll.addAll(ret2);long q3=Long.rotateLeft(q2,16);long q3=Long.rotateLeft(q2,16);Span s3=probe(t3,q3);Span s3=probe(t3,q3);if(s3!=null)if(s3!=null)Arr
40、ayListArrayList ret3=getSim(t3,s3,q3,k);/ret3=getSim(t3,s3,q3,k);/找第三个表找第三个表retAll.addAll(ret3);retAll.addAll(ret3);long q4=Long.rotateLeft(q3,16);long q4=Long.rotateLeft(q3,16);Span s4=probe(t4,q4);Span s4=probe(t4,q4);if(s4!=null)if(s4!=null)ArrayListArrayList ret4=getSim(t4,s4,q4,k);/ret4=getSim(t4,s4,q4,k);/找第四个表找第四个表retAll.addAll(ret4);retAll.addAll(ret4);return return retAllretAll;局限仅能在网页下载后实现，因此它无助于降低抓取过程中的网络带宽浪仅能在网页下载后实现，因此它无助于降低抓取过程中的网络带宽浪费。费。解决方法：爬虫公开排重结果？解决方法：爬虫公开排重结果？作业作业实现网页排重实现网页排重感谢您对猎兔搜索的支持!http:/
