搜索引擎开发实践第十三讲排重课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《搜索引擎开发实践第十三讲排重课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 搜索引擎 开发 实践 第十 三讲 课件
- 资源描述:
-
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;/;/翻
展开阅读全文