搜索引擎開發(fā)實踐第十三講文檔排重課件

搜索引擎開發(fā)實踐

第十三講文檔排重主講人：

羅剛luogang@搜索引擎開發(fā)實踐

第十三講文檔排重主講人：羅剛概述語義指紋SimHash基于SimHash的文檔排重作業(yè)：實現(xiàn)網(wǎng)頁排重概述語義指紋2什么是近似重復(fù)網(wǎng)頁?內(nèi)容相同，但是文檔的少部分不同廣告計數(shù)器時間戳不同的標題文檔ID文檔1文檔2標題北大清華碩士不嫁的“最牛征婚女”1米4專科女征婚求1米8碩士男應(yīng)征者如云內(nèi)容…24歲的羅玉鳳，在上海街頭發(fā)放了1300份征婚傳單。傳單上寫了近乎苛刻的條件，要求男方北大或清華碩士，身高1米76至1米83之間，東部沿海戶籍。而羅玉鳳本人，只有1米46，中文大專學(xué)歷，重慶綦江人?！耸陆?jīng)網(wǎng)絡(luò)曝光后，引起了很多人的興趣?！懊刻於加写螂娫挕l(fā)短信求證，或者是應(yīng)征?！绷_玉鳳說，她覺得滿意的卻寥寥無幾，“到目前為止只有2個，都還不是特別滿意”?！?4歲的羅玉鳳，在上海街頭發(fā)放了1300份征婚傳單。傳單上寫了近乎苛刻的條件，要求男方北大或清華碩士，身高1米76至1米83之間，東部沿海戶籍。而羅玉鳳本人，只有1米46，中文大專學(xué)歷，重慶綦江人。…此事經(jīng)網(wǎng)絡(luò)曝光后，引起了很多人的興趣?！懊刻於加写螂娫挕l(fā)短信求證，或者是應(yīng)征?！绷_玉鳳說，她覺得滿意的卻寥寥無幾，“到目前為止只有2個，都還不是特別滿意”?！裁词墙浦貜?fù)網(wǎng)頁?內(nèi)容相同，但是文檔的少部分不同文檔ID文為什么要去除近似重復(fù)網(wǎng)頁為什么需要檢測近似重復(fù)?節(jié)省存儲空間改進搜索體驗(節(jié)約用戶的時間)互聯(lián)網(wǎng)存在大量的重復(fù)內(nèi)容，有研究顯示，其中有30%的網(wǎng)頁內(nèi)容重復(fù)。抄襲論文的情況也經(jīng)常發(fā)生，文本去重類似的技術(shù)還可以用在抄襲檢測上。為什么要去除近似重復(fù)網(wǎng)頁為什么需要檢測近似重復(fù)?爬蟲架構(gòu)簡化版Web索引HTML文檔Web近似重復(fù)?遍歷鏈接新抓取的文檔一個文檔整個索引插入垃圾NoYes爬蟲架構(gòu)簡化版WebHTMLWeb近似重復(fù)?遍歷鏈接新抓取的語義指紋(fingerprint)每個文檔產(chǎn)生一個f位的語義指紋MD5方法的語義指紋無法找出特征近似的文檔。例如，對于兩個文檔，如果兩個文檔相似，但這兩個文檔的MD5值卻是完全不同的。關(guān)鍵字的微小差別會導(dǎo)致MD5的散列值差異巨大。這是MD5算法中的雪崩效應(yīng)(avalancheeffect)的結(jié)果。輸入中一位的變化，散列結(jié)果中將有一半以上的位改變。如果兩個相似文檔的語義指紋只相差幾位或更少，這樣的語義指紋叫做SimHash。兩個文檔是近似重復(fù)文檔，如果它們的語義指紋最多差k位Google的實驗表明f=64,k=3取得不錯的效果，我們的實驗表明SimHash生成方法對排重準確度有重要影響語義指紋(fingerprint)每個文檔產(chǎn)生一個f位的語義6Simhash文檔w1w2wn特征,權(quán)重100110w1散列碼,權(quán)重110000w2001001wnw1-w1-w1w1w1-w1w2w2-w2-w2-w2-w2-wn-wnwn-wn-wnwn按列加13,108,-22,-5,-32,55符號函數(shù)110001語義指紋Simhash文檔w1w2wn特征,權(quán)重100110w1散列理解SimHash假設(shè)可以得到文檔的一系列的特征，每個特征有不同的重要度。計算文檔對應(yīng)的SimHash值的方法是把每個特征的Hash值疊加到一起形成一個SimHash。可以把特征權(quán)重看成特征在SimHash結(jié)果的每一位上的投票權(quán)。權(quán)重大的特征的投票權(quán)大，權(quán)重小的特征投票權(quán)小。所以權(quán)重大的特征更有可能影響文檔的SimHash值中的很多位，而權(quán)重小的特征影響文檔的SimHash值位數(shù)很少。理解SimHash假設(shè)可以得到文檔的一系列的特征，每個特征有8根據(jù)特征生成64位的SimHashpublicstaticlongsimHash(String[]features,int[]weights){ int[]hist=newint[64];//創(chuàng)建直方圖

for(inti=0;i<features.length;++i){ longfeatureHash=stringHash(features[i]);//生成特征的散列碼

intweight=weights[i]; /*更新直方圖*/ for(intc=0;c<64;c++){ intfWeight=(featureHash&(1<<c))==0?-weight:weight; hist[c]+=fWeight; } } /*從直方圖計算位向量*/ longsimHash=0; for(intc=0;c<64;c++){ longt=((hist[c]>=0)?1:0);//符號函數(shù) t<<=c; simHash|=t; } returnsimHash;}根據(jù)特征生成64位的SimHashpublicstatic9生成特征的散列碼要生成好的SimHash編碼，就要讓完全不同的特征差別盡量大，而相似的特征差別比較小。特征是枚舉類型，比如只有兩個可能的取值，例如是Open和Close。Open返回二進制位全是1的哈希編碼，而Close則返回二進制位全是0的哈希編碼。需要為指定的枚舉值生成盡量不一樣的哈希編碼?？紤]中文字符的編碼范圍計算中文字符串的散列編碼生成特征的散列碼要生成好的SimHash編碼，就要讓完全不同10生成枚舉特征的散列碼//輸入枚舉值，返回對應(yīng)的SimHash值publicstaticlonggetSimHash(MatterTypematter){ intb=1;//記錄用多少位編碼可以表示一個枚舉類型的集合

intx=2; while(x<MatterType.values().length){ b++; x=x<<1; }

longsimHash=matter.ordinal(); intend=64/b; for(inti=0;i<end;++i){ simHash=simHash<<b;//枚舉值按枚舉類型總個數(shù)向左移位

simHash+=matter.ordinal();//取得枚舉值對應(yīng)的整數(shù)值 } returnsimHash;//返回枚舉值的SimHash值}生成枚舉特征的散列碼//輸入枚舉值，返回對應(yīng)的SimHash11中文字符的散列碼publicstaticintbyte2int(byteb){//把字節(jié)轉(zhuǎn)換成整數(shù) return(b&0xff);}privatestaticintMAX_CN_CODE=6768;//最大中文編碼privatestaticintMAX_CODE=6768+117;//最大編碼//取得中文字符的散列編碼，每個中文字符用盡量小的正整數(shù)表示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;}中文字符的散列碼publicstaticintbyte12中文字符串的散列碼//取得中文字符串的散列碼publicstaticlonggetSimHash(Stringinput)throwsUnsupportedEncodingException{ intb=13;//記錄用多少位二進制編碼可以表示一個中文字符

longsimHash=getHashCode(input.charAt(0)); intmaxBit=b; for(inti=1;i<input.length();++i){ simHash*=MAX_CODE;//把漢字串看成是MAX_CODE進制的

simHash+=getHashCode(input.charAt(i)); maxBit+=b; }

longorigialValue=simHash; for(inti=0;i<=(64/maxBit);++i){ simHash=simHash<<maxBit; simHash+=origialValue; } returnsimHash;}中文字符串的散列碼//取得中文字符串的散列碼13海明距離問題SimHash:查找近似重復(fù)文檔轉(zhuǎn)換成查找最多差k位的語義指紋給出一個f位的指紋集合F和一個指紋fg，鑒別出F中是否存在與fg只有k位差異的指紋。窮舉探查探查法擴展指紋fg擴展指紋集合F分而治之法有限狀態(tài)機？海明距離問題14擴展待查指紋排好序的語義指紋集合S64位Q所有的Q’:hd(Q,Q’)≤k=3相等查找()probes!643擴展待查指紋排好序的64位Q所有的Q’:hd(Q,Q’逐次探查法-生成相似語義指紋longfingerPrint=1L;//語義指紋int[]indices;//組合數(shù)生成的一種組合結(jié)果//生成差2位的語義指紋CombinationGeneratorx=newCombinationGenerator(64,2);intcount=0;//計數(shù)器while(x.hasMore()){ indices=x.getNext();//取得組合數(shù)生成結(jié)果

longsimFP=fingerPrint; for(inti=0;i<indices.length;i++){ simFP=simFP^1L<<indices[i];//翻轉(zhuǎn)對應(yīng)的位

} System.out.println(Long.toBinaryString(simFP));//打印相似語義指紋

++count;}逐次探查法-生成相似語義指紋longfingerPrint16逐次探查法查找過程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;i<indices.length;i++){ simFP=simFP^1L<<indices[i]; }

if(contains(simFP)){//查找相似語義指紋 returntrue; } } } returnfalse;}逐次探查法查找過程publicbooleanconta17擴展指紋集合語義指紋集合S64位Q相等查找S’:與S最多k位差別的所有語義指紋(Sort)|S’|≈

|S|

()643擴展指紋集合語義指紋64位Q相等查找S’:與S最多k位差別SimHash排重流程查詢文檔提取特征生成SimHash文檔數(shù)據(jù)庫提取語義指紋語義指紋庫海明距離<指定閾值判為重復(fù)是無重復(fù)否查詢語義指紋庫SimHash排重流程查詢文檔提取特征生成SimHash文檔19快速查找近似的方法觀察到的情況：整個表中排列組合的部分很少，不太可能出現(xiàn)例如：一批8位SimHash，前4位都一樣，但后4位出現(xiàn)16種0-1組合的情況。整個表在前d位0-1分布不會有很多的重復(fù)。Q’Q海明距離(Q,Q’)=3精確匹配!快速查找近似的方法觀察到的情況：Q’Q海明距離(Q,Q’)20分而治之方法-準備把問題分解成更小的幾個子問題，降低問題需要處理的數(shù)據(jù)規(guī)模。利用空間（原空間的t倍）和并行計算換時間。分治法查找海明距離在k以內(nèi)的語義指紋算法步驟如下：先復(fù)制原表T為t份：T1,T2,…,Tt。每個Ti都關(guān)聯(lián)一個整數(shù)pi和一個置換函數(shù)πi，置換函數(shù)負責把來源于表T的pi個二進制位換到高位上。應(yīng)用置換函數(shù)πi到相應(yīng)的Ti表上，然后對Ti進行排序。分而治之方法-準備把問題分解成更小的幾個子問題，降低問題需要21分而治之方法-查找然后對每一個Ti和要匹配的指紋F、海明距離k做如下運算：使用指紋F通過置換函數(shù)πi

生成的F’的高pi位檢索，找出Ti中高pi位相同的集合，在檢索出的集合中比較剩下的f-pi位，找出海明距離小于或等于k的指紋。最后合并所有Ti中檢索出的結(jié)果。FF’πipif-pi分而治之方法-查找然后對每一個Ti和要匹配的指紋F、海明距離22分而治之例子在S中的語義指紋ABCD64位16位ABCD64位QQ1Q2Q3Q4Q1Q2Q3Q4在16位上的精確搜索分而治之例子在S中的語義指紋ABCD64位16位ABCD64準備表

publicstaticbooleanisLessThanUnsigned(longn1,longn2){

return(n1<n2)^((n1<0)!=(n2<0));

} staticComparator<SimHashData>comp=newComparator<SimHashData>(){

publicintcompare(SimHashDatao1,SimHashDatao2){ if(o1.q==o2.q)return0;

return(isLessThanUnsigned(o1.q,o2.q))?1:-1; } };//比較無符號64位

publicvoidsort(){//對四個表排序

t2.clear(); t3.clear(); t4.clear(); for(SimHashDatasimHash:t1) { longt=Long.rotateLeft(simHash.q,16); t2.add(newSimHashData(t,simHash.no));

t=Long.rotateLeft(t,16); t3.add(newSimHashData(t,simHash.no));

t=Long.rotateLeft(t,16); t4.add(newSimHashData(t,simHash.no)); } Collections.sort(t1,comp); Collections.sort(t2,comp); Collections.sort(t3,comp); Collections.sort(t4,comp); }準備表 publicstaticbooleanisLe24查找-探查某個表publicSpanprobe(ArrayList<SimHashData>t,longkey){//返回匹配區(qū)間 intlow=0;//采用折半查找的方式實現(xiàn) inthigh=t.size()-1; while(low<=high){ intmid=(low+high)>>>1; LongmidVal=t.get(mid).q; intcmp=compHpare(midVal,key);//比較高位，也就是高16位做精確匹配 if(cmp<0) low=mid+1; elseif(cmp>0) high=mid-1; else{//已找到，擴展匹配區(qū)間 intmatchStart=mid; intmatchEnd=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; } } returnnewSpan(matchStart,matchEnd); } } returnnull;//沒找到}查找-探查某個表publicSpanprobe(Arra25查找-選擇出差別在k位的語義指紋集合//從Span找出最多差k位的語義指紋集合publicArrayList<SimHashData>getSim(ArrayList<SimHashData>t,Spans,//區(qū)間 longfingerPrint,//待查找的語義指紋 intk//差k位 ){ ArrayList<SimHashData>result=newArrayList<SimHashData>(); for(inti=s.getStart();i<=s.getEnd();++i){ SimHashDatadata=t.get(i); longq=data.q; if(BitUtil.diffIn(fingerPrint,q,k)){//fingerPrint和q的海明距離是否在k位以內(nèi) result.add(data); } } returnresult;}查找-選擇出差別在k位的語義指紋集合//從Span找出最多差26查找4個表publicHashSet<SimHashData>g