1、搜索引擎开 发实 践第十三 讲 文档排重主 讲 人： 罗刚概 述l语义 指 纹lSimHashl基于 SimHash的文档排重l作 业 ： 实现 网 页 排重什么是近似重复网 页 ?内容相同，但是文档的少部分不同广告计 数器时间 戳不同的 标题文档 ID 文档 1 文档 2标题 北大清 华硕 士不嫁的 “最牛征婚女 ” 1米 4专 科女征婚 求 1米 8硕 士男 应 征者如云内容 24 岁 的 罗 玉 凤 ，在上海街 头发 放了 1300份征婚 传单 。 传单 上写了近乎苛刻的条件，要求男方北大或清 华硕 士，身高 1米 76至 1米83之 间 ， 东 部沿海 户 籍。而 罗 玉 凤 本人，只
2、有 1米 46，中文大 专 学 历 ，重 庆 綦江人。 此事 经 网 络 曝光后，引起了很多人的 兴 趣。 “每天都有打 电话 、 发 短信求 证 ，或者是 应 征。 ”罗 玉 凤说 ，她 觉 得 满 意的却寥寥无几， “到目前 为 止只有 2个，都 还 不是特 别满 意 ”。24 岁 的 罗 玉 凤 ，在上海街 头发 放了1300份征婚 传单 。 传单 上写了近乎苛刻的条件，要求男方北大或清 华硕 士，身高1米 76至 1米 83之 间 ， 东 部沿海 户 籍。而罗 玉 凤 本人，只有 1米 46，中文大 专 学 历，重 庆 綦江人。 此事 经 网 络 曝光后，引起了很多人的 兴 趣。 “每
3、天都有打 电话 、发 短信求 证 ，或者是 应 征。 ”罗 玉 凤说 ，她 觉 得 满 意的却寥寥无几， “到目前 为 止只有 2个，都 还 不是特 别满 意 ”。 为 什么要去除近似重复网 页为 什么需要 检测 近似重复 ?节 省存 储 空 间改 进 搜索体 验 (节约 用 户 的 时间 )互 联 网存在大量的重复内容，有研究 显 示，其中有 30%的网 页 内容重复。抄 袭论 文的情况也 经 常 发 生，文本去重 类 似的技 术还 可以用在抄 袭检测 上。爬虫架构 简 化版Web索引HTML文档Web近似重复?遍 历链 接新抓取的文档一个文档整个索引插入 垃圾语义 指 纹 (fingerp
4、rint)l每个文档 产 生一个 f位的 语义 指 纹lMD5方法的 语义 指 纹 无法找出特征近似的文档。例如， 对 于两个文档，如果两个文档相似，但 这 两个文档的 MD5值 却是完全不同的。关键 字的微小差 别 会 导 致 MD5的散列 值 差异巨大。 这 是 MD5算法中的雪崩效 应 (avalanche effect)的 结 果。 输 入中一位的 变 化，散列 结 果中将有一半以上的位改 变 。 l如果两个相似文档的 语义 指 纹 只相差几位或更少， 这样 的 语义 指 纹叫做 SimHash。l两个文档是近似重复文档，如果它 们 的 语义 指 纹 最多差 k位lGoogle的 实验
5、 表明 f=64, k=3取得不 错 的效果，我 们 的 实验 表明SimHash生成方法 对 排重准确度有重要影响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,55符号函数110001语义 指 纹理解 SimHash假 设 可以得到文档的一系列的特征，每个特征有不同的重要度。 计 算文档 对应 的 SimHash值 的方法是把每个特征的 Hash值 叠加到一起形成一
6、个 SimHash。可以把特征 权 重看成特征在 SimHash结 果的每一位上的投票 权 。 权重大的特征的投票 权 大， 权 重小的特征投票 权 小。所以 权 重大的特征更有可能影响文档的 SimHash值 中的很多位，而 权 重小的特征影响文档的 SimHash值 位数很少。根据特征生成 64位的 SimHashpublic 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编码 ，就要 让 完全不同的特征差 别 尽量大，而相似的特征差 别 比 较 小。特征是枚 举类 型，比如只有两个可能的取 值 ，例如是 Open和 Close。 Open返回二 进 制位全是 1的哈希 编码 ，而 Close则 返回二 进 制位全是 0的哈希 编码 。需要 为 指定的枚 举值 生成尽量不一 样 的哈希 编码 。考 虑 中文字符的 编码 范 围计 算中文字符串的散列 编码
