《搜索引擎开发实践第十三讲文档排重》由会员分享，可在线阅读，更多相关《搜索引擎开发实践第十三讲文档排重（30页珍藏版）》请在金锄头文库上搜索。
1、搜索引擎开发实践第十三讲文档排重,主讲人： 罗刚 ,概 述,语义指纹 SimHash 基于SimHash的文档排重 作业：实现网页排重,什么是近似重复网页?,内容相同，但是文档的少部分不同 广告 计数器 时间戳 不同的标题,为什么要去除近似重复网页,为什么需要检测近似重复? 节省存储空间 改进搜索体验(节约用户的时间) 互联网存在大量的重复内容，有研究显示，其中有30%的网页内容重复。抄袭论文的情况也经常发生，文本去重类似的技术还可以用在抄袭检测上。,爬虫架构简化版,Web 索引,HTML 文档,Web,近似重复?,遍历链接,新抓取的文档,一个文档,整个索引,插入,垃圾,No,Yes,语义指纹
2、(fingerprint),每个文档产生一个f位的语义指纹 MD5方法的语义指纹无法找出特征近似的文档。例如，对于两个文档，如果两个文档相似，但这两个文档的MD5值却是完全不同的。关键字的微小差别会导致MD5的散列值差异巨大。这是MD5算法中的雪崩效应(avalanche effect)的结果。输入中一位的变化，散列结果中将有一半以上的位改变。 如果两个相似文档的语义指纹只相差几位或更少，这样的语义指纹叫做SimHash。 两个文档是近似重复文档，如果它们的语义指纹最多差k位 Google的实验表明f=64, k=3取得不错的效果，我们的实验表明SimHash生成方法对排重准确度有重要影响,S
3、imhash,文档,w1,w2,wn,特征,权重,100110,w1,散列码,权重,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,符号函数,110001,语义指纹,理解SimHash,假设可以得到文档的一系列的特征，每个特征有不同的重要度。计算文档对应的SimHash值的方法是把每个特征的Hash值叠加到一起形成一个SimHash。 可以把特征权重看成特征在SimHash结果的每一位上的投票权。权重大的特征的投票权大，权重
4、小的特征投票权小。所以权重大的特征更有可能影响文档的SimHash值中的很多位，而权重小的特征影响文档的SimHash值位数很少。,根据特征生成64位的SimHash,public static long simHash(String features,int weights) int hist = new int64;/创建直方图 for(int i=0;i=0)?1:0);/符号函数 t = c; simHash |= t ; return simHash; ,生成特征的散列码,要生成好的SimHash编码，就要让完全不同的特征差别尽量大，而相似的特征差别比较小。 特征是枚举类型，比如只有
5、两个可能的取值，例如是Open和Close。Open返回二进制位全是1的哈希编码，而Close则返回二进制位全是0的哈希编码。需要为指定的枚举值生成尽量不一样的哈希编码。 考虑中文字符的编码范围计算中文字符串的散列编码,生成枚举特征的散列码,/输入枚举值，返回对应的SimHash值 public static long getSimHash(MatterType matter) int b=1; /记录用多少位编码可以表示一个枚举类型的集合 int x=2; while(xMatterType.values().length) b+; x = x1; long simHash = matter
6、.ordinal(); int end = 64/b; for(int i=0;iend;+i) simHash = simHash b; /枚举值按枚举类型总个数向左移位 simHash += matter.ordinal(); /取得枚举值对应的整数值 return simHash;/返回枚举值的SimHash值 ,中文字符的散列码,public static int byte2int(byte b) /把字节转换成整数 return (b ,中文字符串的散列码,/取得中文字符串的散列码 public static long getSimHash(String input) throws
7、UnsupportedEncodingException int b=13; /记录用多少位二进制编码可以表示一个中文字符 long simHash = getHashCode(input.charAt(0); int maxBit = b; for(int i=1;iinput.length();+i) simHash *= MAX_CODE; /把汉字串看成是MAX_CODE进制的 simHash += getHashCode(input.charAt(i); maxBit += b; long origialValue = simHash; for(int i=0;i=(64/maxBi
8、t);+i) simHash = simHash maxBit; simHash += origialValue; return simHash; ,海明距离问题,SimHash:查找近似重复文档转换成查找最多差k位的语义指纹 给出一个f位的指纹集合F和一个指纹fg，鉴别出F中是否存在与fg只有k位差异的指纹。 穷举探查探查法 扩展指纹fg 扩展指纹集合F 分而治之法 有限状态机？,扩展待查指纹,排好序的 语义指纹 集合S,所有的 Q: hd(Q,Q)k=3,相等查找,逐次探查法-生成相似语义指纹,long fingerPrint = 1L; /语义指纹 int indices; /组合数生成
9、的一种组合结果 /生成差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);/打印相似语义
10、指纹 +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() i
11、ndices = 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,相等查找,S:与S最多k位差别的所有 语义指纹,(Sort),SimHash排重流程,快速查找近似的方法,观察到的情况： 整个表中排列组合的部分很少，不太可能出现例如：一批8位SimHash，前4位都一样，但后
12、4位出现16种0-1组合的情况。 整个表在前d位0-1分布不会有很多的重复。,Q,Q,海明距离(Q,Q) = 3,精确匹配!,分而治之方法-准备,把问题分解成更小的几个子问题，降低问题需要处理的数据规模。利用空间（原空间的t倍）和并行计算换时间。分治法查找海明距离在k以内的语义指纹算法步骤如下： 先复制原表T为t份：T1,T2,Tt。 每个Ti都关联一个整数pi和一个置换函数i，置换函数负责把来源于表T的pi个二进制位换到高位上。 应用置换函数i到相应的Ti表上，然后对Ti进行排序。,分而治之方法-查找,然后对每一个Ti和要匹配的指纹F、海明距离k做如下运算：使用指纹F通过置换函数i 生成的F
13、的高pi位检索，找出Ti中高pi位相同的集合，在检索出的集合中比较剩下的f-pi位，找出海明距离小于或等于k的指纹。 最后合并所有Ti中检索出的结果。,F,F,i,pi,f-pi,分而治之例子,在S中的语义指纹,A,B,C,D,64位,16位,在16位上的精确搜索,准备表,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) retu
14、rn 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);
15、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;
16、 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 (comp
