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

搜索引擎开发实践第十三讲文档排重主讲人：罗刚[e-mail]概述语义指纹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近似重复?遍历链接新抓取的文档一个文档整个索引插入垃圾语义指纹(fingerprint)每个文档产生一个f位的语义指纹MD5方法的语义指纹无法找出特征近似的文档。例如，对于两个文档，如果两个文档相似，但这两个文档的MD5值却是完全不同的。关键字的微小差别会导致MD5的散列值差异巨大。这是MD5算法中的雪崩效应(avalancheeffect)的结果。输入中一位的变化，散列结果中将有一半以上的位改变。如果两个相似文档的语义指纹只相差几位或更少，这样的语义指纹叫做SimHash。两个文档是近似重复文档，如果它们的语义指纹最多差k位Google的实验表明f=64,k=3取得不错的效果，我们的实验表明SimHash生成方法对排重准确度有重要影响Simhash文档w1w2wn特征,权重100110w1散列码,权重110000w2001001wnw1-w1-w1w1w1-w1w2w2-w2-w2-w2-w2-wn-wnwn-wn-wnwn按列加13,108,-22,-5,-32,55符号函数110001语义指纹理解SimHash假设可以得到文档的一系列的特征，每个特征有不同的重要度。计算文档对应的SimHash值的方法是把每个特征的Hash值叠加到一起形成一个SimHash。可以把特征权重看成特征在SimHash结果的每一位上的投票权。权重大的特征的投票权大，权重小的特征投票权小。所以权重大的特征更有可能影响文档的SimHash值中的很多位，而权重小的特征影响文档的SimHash值位数很少。根据特征生成64位的SimHashpublicstaticlongsimHash(String[]features,int[]weights){int[]hist=newint[64];//创建直方图for(inti=0;ifeatures.length;++i){longfeatureHash=stringHash(features[i]);//生成特征的散列码intweight=weights[i];/*更新直方图*/for(intc=0;c64;c++){intfWeight=(featureHash&(1c))==0?-weight:weight;hist[c]+=fWeight;}}/*从直方图计算位向量*/longsimHash=0;for(intc=0;c64;c++){longt=((hist[c]=0)?1:0);//符号函数t=c;simHash|=t;}returnsimHash;}生成特征的散列码要生成好的SimHash编码，就要让完全不同的特征差别尽量大，而相似的特征差别比较小。特征是枚举类型，比如只有两个可能的取值，例如是Open和Close。Open返回二进制位全是1的哈希编码，而Close则返回二进制位全是0的哈希编码。需要为指定的枚举值生成尽量不一样的哈希编码。考虑中文字符的编码范围计算中文字符串的散列编码生成枚举特征的散列码//输入枚举值，返回对应的SimHash值publicstaticlonggetSimHash(MatterTypematter){intb=1;//记录用多少位编码可以表示一个枚举类型的集合intx=2;while(xMatterType.values().length){b++;x=x1;}longsimHash=matter.ordinal();intend=64/b;for(inti=0;iend;++i){simHash=simHashb;//枚举值按枚举类型总个数向左移位simHash+=matter.ordinal();//取得枚举值对应的整数值}returnsimHash;//返回枚举值的SimHash值}中文字符的散列码publicstaticintbyte2int(byteb){//把字节转换成整数return(b&0xff);}privatestaticintMAX_CN_CODE=6768;//最大中文编码privatestaticintMAX_CODE=6768+117;//最大编码//取得中文字符的散列编码，每个中文字符用尽量小的正整数表示publicstaticintgetHashCode(charc)throwsUnsupportedEncodingException{Strings=String.valueOf(c);intmaxValue=6768;byte[]b=s.getBytes(gb2312);if(b.length==2){intindex=(byte2int(b[0])-176)*94+(byte2int(b[1])-161);returnindex;}elseif(b.length==1){intindex=byte2int(b[0])-9+MAX_CN_CODE;returnindex;}returnc;}中文字符串的散列码//取得中文字符串的散列码publicstaticlonggetSimHash(Stringinput)throwsUnsupportedEncodingException{intb=13;//记录用多少位二进制编码可以表示一个中文字符longsimHash=getHashCode(input.charAt(0));intmaxBit=b;for(inti=1;iinput.length();++i){simHash*=MAX_CODE;//把汉字串看成是MAX_CODE进制的simHash+=getHashCode(input.charAt(i));maxBit+=b;}longorigialValue=simHash;for(inti=0;i=(64/maxBit);++i){simHash=simHashmaxBit;simHash+=origialValue;}returnsimHash;}海明距离问题SimHash:查找近似重复文档转换成查找最多差k位的语义指纹给出一个f位的指纹集合F和一个指纹fg，鉴别出F中是否存在与fg只有k位差异的指纹。穷举探查探查法扩展指纹fg扩展指纹集合F分而治之法有限状态机？扩展待查指纹排好序的语义指纹集合S64位Q所有的Q’:hd(Q,Q’)≤k=3相等查找逐次探查法-生成相似语义指纹longfingerPrint=1L;//语义指纹int[]indices;//组合数生成的一种组合结果//生成差2位的语义指纹CombinationGeneratorx=newCombinationGenerator(64,2);intcount=0;//计数器while(x.hasMore()){indices=x.getNext();//取得组合数生成结果longsimFP=fingerPrint;for(inti=0;iindices.length;i++){simFP=simFP^1Lindices[i];//翻转对应的位}System.out.println(Long.toBinaryString(simFP));//打印相似语义指纹++count;}逐次探查法查找过程publicbooleancontainSim(longfingerPrint,intk){//输入要查找的语义指纹和k值，如果找到相似的语义指纹则返回真，否则返回假if(contains(fingerPrint)){//首先用二分法直接查找语义指纹returntrue;}//然后用逐次探查法查找int[]indices;for(intki=1;ki=k;++ki){//找差1位直到差k位的CombinationGeneratorx=newCombinationGenerator(64,ki);while(x.hasMore()){indices=x.getNext();longsimFP=fingerPrint;//存放相似的语义指纹for(inti=0;iindices.length;i++){simFP=simFP^1Lindices[i];}if(contains(simFP)){//查找相似语义指纹returntrue;}}}returnfalse;}扩展指纹集合语义指纹集合S64位Q相等查找S’:与S最多k位差别的所有语义指纹(Sort)SimHash排重流程查询文档提取特征生成SimHash文档数据库提取语义指纹语义指纹库海明距离指定阈值判为重复是无重复否查询语义指纹库快速查找近似的方法观察到的情况：1.整个表中排列组合的部分很少，不太可能出现例如：一批8位SimHash，前4位都一样，但后4位出现16种0-1组合的情况。2.整个表在前d位0-1分布不会有很多的重复。Q’Q海明距离(Q,Q’)=3精确匹配!分而治之方法-准备把问题分解成更小的几个子问题，降低问题需要处理的数据规模。利用空间（原空间的t倍）和并行计算换时间。分治法查找海明距离在k以内的语义指纹算法步骤如下：1.先复制原表T为t份：T1,T2,…,Tt。2.每个Ti都关联一个整数pi和一个置换函数πi，置换函数负责把来源于表T的pi个二进制位换到高位上。3.应用置换函数πi到相应的Ti表上，然后对Ti进行排序。分而治之方法-查找1.然后对每一个Ti和要匹配的指纹F、海明距离k做如下运算：使用指纹F通过置换函数πi生成的F’的高pi位检索，找出Ti中高pi位相同的集合，在检索出的集合中比较剩下的f-pi位，找出海明距离小于或等于k的指纹。2.最后合并所有Ti中检索出的结果。FF’πipif-pi分而治之例子在S中的语义指纹ABCD64位16位ABCD64位QQ1Q2Q3Q4Q1Q2Q3Q4在16位上的精确搜索准备表publicstaticbooleanisLessThanUnsigned(longn1,longn2){return(n1n2)^((n10)!=(n20));}staticComparatorSimHashDatacomp=newComparatorSimHashData(){publicintcompare(SimHashDatao1,SimHashDatao2){if(o1.q==o2.q)return0;return(isLessThanUnsigned(o1.q,o2.q))?1:-1;}};//比较无符号64位p