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

1、搜索引擎開發(fā)實踐第十三講文檔排重,主講人： 羅剛luogang@gmail.com,概 述,語義指紋SimHash基于SimHash的文檔排重作業(yè)：實現(xiàn)網(wǎng)頁排重,什么是近似重復(fù)網(wǎng)頁?,內(nèi)容相同，但是文檔的少部分不同廣告計數(shù)器時間戳不同的標(biāo)題,為什么要去除近似重復(fù)網(wǎng)頁,為什么需要檢測近似重復(fù)?節(jié)省存儲空間改進(jìn)搜索體驗(節(jié)約用戶的時間)互聯(lián)網(wǎng)存在大量的重復(fù)內(nèi)容，有研究顯示，其中有30%的網(wǎng)頁內(nèi)容重復(fù)。抄襲論文的

2、情況也經(jīng)常發(fā)生，文本去重類似的技術(shù)還可以用在抄襲檢測上。,爬蟲架構(gòu)簡化版,Web索引,HTML文檔,Web,,,,,近似重復(fù)?,遍歷鏈接,新抓取的文檔,一個文檔,整個索引,插入,垃圾,No,Yes,,語義指紋(fingerprint),每個文檔產(chǎn)生一個f位的語義指紋MD5方法的語義指紋無法找出特征近似的文檔。例如，對于兩個文檔，如果兩個文檔相似，但這兩個文檔的MD5值卻是完全不同的。關(guān)鍵字的微小差別會導(dǎo)致MD5的散列值差異巨大。這

3、是MD5算法中的雪崩效應(yīng)(avalanche effect)的結(jié)果。輸入中一位的變化，散列結(jié)果中將有一半以上的位改變。 如果兩個相似文檔的語義指紋只相差幾位或更少，這樣的語義指紋叫做SimHash。兩個文檔是近似重復(fù)文檔，如果它們的語義指紋最多差k位Google的實驗表明f=64, k=3取得不錯的效果，我們的實驗表明SimHash生成方法對排重準(zhǔn)確度有重要影響,Simhash,文檔,,,w1,,w2,,wn,特征,權(quán)重,,,,1

4、00110,w1,散列碼,權(quán)重,110000,w2,001001,wn,,,,w1 -w1 -w1 w1 w1 -w1,w2 w2 -w2 -w2 -w2 -w2,-wn -wn wn -wn -wn wn,,按列加,13,108,-22,-5,-32,55,,符號函數(shù),110001,語義指紋,理解SimHash,假設(shè)可以得到文檔的一系列的特征，每個特征有不同的重要度。計算文檔對應(yīng)的SimHash值的方法是把每個特征的Hash值疊加到

5、一起形成一個SimHash?？梢园烟卣鳈?quán)重看成特征在SimHash結(jié)果的每一位上的投票權(quán)。權(quán)重大的特征的投票權(quán)大，權(quán)重小的特征投票權(quán)小。所以權(quán)重大的特征更有可能影響文檔的SimHash值中的很多位，而權(quán)重小的特征影響文檔的SimHash值位數(shù)很少。,根據(jù)特征生成64位的SimHash,public static long simHash(String[] features,int[] weights){int[] hist =

6、new int[64];//創(chuàng)建直方圖for(int i=0;i=0)?1:0);//符號函數(shù)t <<= c;simHash |= t ;} return simHash;},生成特征的散列碼,要生成好的SimHash編碼，就要讓完全不同的特征差別盡量大，而相似的特征差別比較小。特征是枚舉類型，比如只有兩個可能的取值，例如是Open和Close。Open返回二進(jìn)制位全是1的哈希編碼，而

7、Close則返回二進(jìn)制位全是0的哈希編碼。需要為指定的枚舉值生成盡量不一樣的哈希編碼?？紤]中文字符的編碼范圍計算中文字符串的散列編碼,生成枚舉特征的散列碼,//輸入枚舉值，返回對應(yīng)的SimHash值public static long getSimHash(MatterType matter){int b=1; //記錄用多少位編碼可以表示一個枚舉類型的集合int x=2;while(x<MatterType.va

8、lues().length){b++;x = x<<1;}long simHash = matter.ordinal();int end = 64/b;for(int i=0;i<end;++i){simHash = simHash << b; //枚舉值按枚舉類型總個數(shù)向左移位simHash += matter.ordinal(); //取得枚舉值對應(yīng)的整數(shù)值

9、}return simHash;//返回枚舉值的SimHash值},中文字符的散列碼,public static int byte2int(byte b) {//把字節(jié)轉(zhuǎn)換成整數(shù)return (b & 0xff);}private static int MAX_CN_CODE = 6768;//最大中文編碼private static int MAX_CODE = 6768+117;//最大編碼//取得中文字

10、符的散列編碼，每個中文字符用盡量小的正整數(shù)表示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

11、 index = (byte2int(b[0]) - 176) * 94 + (byte2int(b[1]) - 161);return index;}else if(b.length==1){int index = byte2int(b[0]) - 9 + MAX_CN_CODE;return index;}return c;},中文字符串的散列碼,//取得中文字符串的散列碼public st

12、atic long getSimHash(String input) throws UnsupportedEncodingException{int b=13; //記錄用多少位二進(jìn)制編碼可以表示一個中文字符long simHash = getHashCode(input.charAt(0));int maxBit = b;for(int i=1;i<input.length();++i){simHash

13、*= MAX_CODE; //把漢字串看成是MAX_CODE進(jìn)制的simHash += getHashCode(input.charAt(i));maxBit += b;}long origialValue = simHash;for(int i=0;i<=(64/maxBit);++i){simHash = simHash << maxBit;simHash += origi

14、alValue;}return simHash;},海明距離問題,SimHash:查找近似重復(fù)文檔轉(zhuǎn)換成查找最多差k位的語義指紋給出一個f位的指紋集合F和一個指紋fg，鑒別出F中是否存在與fg只有k位差異的指紋。窮舉探查探查法擴(kuò)展指紋fg擴(kuò)展指紋集合F分而治之法有限狀態(tài)機(jī)？,擴(kuò)展待查指紋,排好序的語義指紋集合S,,所有的 Q’: hd(Q,Q’)≤k=3,相等查找,逐次探查法-生成相似語義指紋,long fin

15、gerPrint = 1L; //語義指紋int[] indices; //組合數(shù)生成的一種組合結(jié)果//生成差2位的語義指紋CombinationGenerator x = new CombinationGenerator(64, 2);int count =0; //計數(shù)器while (x.hasMore()) {indices = x.getNext();//取得組合數(shù)生成結(jié)果long simFP = finger

16、Print;for (int i = 0; i < indices.length; i++) {simFP = simFP ^ 1L << indices[i];//翻轉(zhuǎn)對應(yīng)的位}System.out.println(Long.toBinaryString(simFP));//打印相似語義指紋++count;},逐次探查法查找過程,public boolean containSim(long f

17、ingerPrint,int k) {//輸入要查找的語義指紋和k值，如果找到相似的語義指紋則返回真，否則返回假if(contains(fingerPrint)){//首先用二分法直接查找語義指紋return true;}//然后用逐次探查法查找int[] indices;for(int ki=1;ki<=k;++ki){//找差1位直到差k位的CombinationGenerator x =

18、new CombinationGenerator(64, ki);while (x.hasMore()) {indices = x.getNext();long simFP = fingerPrint;//存放相似的語義指紋for (int i = 0; i < indices.length; i++) {simFP = simFP ^ 1L << indices[i];

19、}if(contains(simFP)){//查找相似語義指紋return true;}}}return false;},擴(kuò)展指紋集合,語義指紋集合S,相等查找,S’:與S最多k位差別的所有語義指紋,,(Sort),SimHash排重流程,快速查找近似的方法,觀察到的情況：整個表中排列組合的部分很少，不太可能出現(xiàn)例如：一批8位SimHash，前4位都一樣，但后4位出現(xiàn)16種0-1組合的情況

20、。整個表在前d位0-1分布不會有很多的重復(fù)。,Q’,Q,海明距離(Q,Q’) = 3,,,,,精確匹配!,分而治之方法-準(zhǔn)備,把問題分解成更小的幾個子問題，降低問題需要處理的數(shù)據(jù)規(guī)模。利用空間（原空間的t倍）和并行計算換時間。分治法查找海明距離在k以內(nèi)的語義指紋算法步驟如下：先復(fù)制原表T為t份：T1,T2,…,Tt。每個Ti都關(guān)聯(lián)一個整數(shù)pi和一個置換函數(shù)πi，置換函數(shù)負(fù)責(zé)把來源于表T的pi個二進(jìn)制位換到高位上。應(yīng)用置換函數(shù)πi

21、到相應(yīng)的Ti表上，然后對Ti進(jìn)行排序。,分而治之方法-查找,然后對每一個Ti和要匹配的指紋F、海明距離k做如下運算：使用指紋F通過置換函數(shù)πi 生成的F’的高pi位檢索，找出Ti中高pi位相同的集合，在檢索出的集合中比較剩下的f-pi位，找出海明距離小于或等于k的指紋。最后合并所有Ti中檢索出的結(jié)果。,F,F’,,πi,,pi,,f-pi,分而治之例子,,在S中的語義指紋,A,B,C,D,,64位,,16位,,在16位上的精確

22、搜索,準(zhǔn)備表,public static boolean isLessThanUnsigned(long n1, long n2) {return (n1 comp = new Comparator(){public int compare(SimHashData o1, SimHashData o2){if(o1.q==o2.q) return 0;return (isLessThanUnsigned(o

23、1.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.

24、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, c

25、omp);Collections.sort(t3, comp);Collections.sort(t4, comp);},查找-探查某個表,public Span probe(ArrayList t, long key) {//返回匹配區(qū)間int low = 0;//采用折半查找的方式實現(xiàn)int high = t.size() - 1;while (low >> 1;Long midVal

26、= t.get(mid).q;int cmp = compHigh.compare(midVal, key);//比較高位，也就是高16位做精確匹配if (cmp 0)high = mid - 1;else {//已找到，擴(kuò)展匹配區(qū)間int matchStart = mid;int matchEnd = mid;while (matchStart > 0) {midVa

27、l = t.get(matchStart - 1).q;if (compHigh.compare(midVal, key) == 0) {--matchStart;} else {break;}}while (matchEnd < (t.size() - 1)) {midVal = t.get(matchEnd + 1).q;if (comp

28、High.compare(midVal, key) == 0) {++matchEnd;} else {break;}}return new Span(matchStart, matchEnd);}}return null; //沒找到},查找-選擇出差別在k位的語義指紋集合,//從Span找出最多差k位的語義指紋集合public ArrayList getS

29、im(ArrayList t, Span s,//區(qū)間 long fingerPrint,//待查找的語義指紋 int k//差k位 ) {ArrayList result = new ArrayList();for (int i = s.getStart(); i <= s.getEnd(); ++i) {SimHashData data = t.get(i);

30、long q = data.q;if (BitUtil.diffIn(fingerPrint, q, k)) {//fingerPrint和q的海明距離是否在k位以內(nèi)result.add(data);}}return result;},查找4個表,public HashSet getSimSet(long fingerPrint, int k) {HashSet retAll = new HashS

31、et();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 (

32、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); //找第三個

33、表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;},局限,僅能在網(wǎng)頁下載后實現(xiàn)，因