网页去重之Simhash算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了网页去重之Simhash算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4181字，纯文字阅读大概需要6分钟。

内容图文

Simhash算法是Google应用在网页去重中的一个常用算法，在开始讲解Simhash之前，先了解——什么是网页去重？为什么要进行网页去重？如何进行网页去重，其基本框架是什么？ ? 网页去重，顾名思义，就是过滤掉重复的网页。统计结果表明，近似重复网页的数量占网页总数量的比例较高，即互联网上有很多的页面内容是完全一样的或是相近的（这个不难理解，比如对于某一事件的新闻报道，很多是大同小异的）。基于这一实际情况，所以要进行网页去重。 ? 那么如何进行网页去重呢？这就用到了Simhash算法。 去重算法的任务是对海量数据进行处理，通用的网页去重的基本框架如下。

• 对于给定的文档，首先通过一定的特征抽取手段，从文档中抽取出一系列能够表征文档主体内容的特征集合。这一步的关键点在于，尽可能保留文档的重要信息，抛弃无关紧要的信息。如何判定哪些信息是重要的，哪些是不重要的，就是算法研究的重点。
• 将文档转换为特征集合后，由于搜索引擎所处理的网页数量数以亿计，为了能够提高计算速度，很多算法会在特征集合的基础上，对信息进一步压缩，采用信息指纹相关算法，将特征集合压缩为新的数据集合（即生成文档指纹），其包含的元素数量远远小于特征集合数量。
• 把文档压缩为文档指纹后，即可通过相似性计算来判断哪些网页是近似重复页面。

? 概括的说，就是：(1)特征词提取 --> (2)生成文档指纹 --> (3)相似性计算? ? 流程图如下图所示 ?? 接下来，我们具体来说说Simhash算法的原理。主要是特征词提取和生成文档指纹这两部分

1. 从文档中提取一组能表征文章的特征词（这里首先需要利用开源的cppjieba进行分词），并计算权重（见笔记：利用tf-idf算法自动提取关键词），得到pair<特征词，权重>；
2. 利用hash函数（这个hash函数利用开源的），将每个特征词映射成为固定长度的二进制数，即哈希值，得到pair<哈希值，权重>；
3. 利用权值（w）对步骤2产生的二进制数进行改写，即把权重信息融入二进制序列中，变成一个实数向量。假设步骤2中得到的是<100110, w>，那么经过改写变成了实数向量(w,-w,-w,w,w,-w)；
4. 每个特征词都做了步骤3的改写后，对一篇文档中的所有特征词的实数向量进行累加（即对应位置相加），从而获得一个代表整个文档的实数向量。假设最后得到的实数向量是（13,108，-22，-5，-32,55）。
5. 将步骤4得到的实数向量规范化，即将实数向量转换为二进制序列，转换规则为正数变为1，负数变为0。即（13,108，-22，-5，-32,55） --> 110001。最终得到的这个二进制序列就是本文档的文档指纹。

? 流程示意图如下： ? 计算得到每一篇文档的文档指纹后，我们就要对文档集合中的所有文档进行相似性计算，把雷同的文档过滤掉。那么，怎么进行文档相似性的计算呢？ ? 对于文档A，B，其内容的相似性可以通过A，B对应的文档指纹的相似性程度来体现。即，内容越相似，二进制序列对应位置相同的位数就越多。而两个二进制序列之间的差异被称为“海明距离”，海明距离越小，表示两篇文档越相似。一般认为，当海明距离<=3时，两篇文档就被视为雷同。至此，问题就转移至——如何求海明距离？ ? 假设文档A的文档指纹是100110，文档B的文档指纹是100011，显然，有两个位置上的数不一样，即海明距离为2。那么，文档A，B的海明距离具体该如何计算呢？ A：100110 B：100011 ^? ? ?000101 ?--> 海明距离为2 通过上面的计算，我们可以知道，求海明距离，实际上是先对两个二进制序列进行异或运算（假设运算结果是ret），再对二进制序列ret求其1的个数。至此，问题又转移至——如何求一个二进制序列中"1"的个数？ ? 关于【如何求一个二进制序列中"1"的个数】这个问题，在此稍作讲解，其实这是一个经典而又巧妙的基础算法题。 ? 在分析这种算法前，我们先来看看把一个数减1会发生什么神奇的事情？ 如果一个整数不等于0，那么该整数的二进制表示中至少有一位是1。 情况1：假设这个数的二进制表示的最右边一位是1，那么经过减1操作后，最后一位变成了0而其他位不变，也就是最后一位相当于做了取反操作，由1变成0； 情况2：假设这个数的二进制表示的最后一位是0，而它的最右边的1 位于第m位，那么经过减1操作后，第m位由1变成0，而第m位之后的位取反，第m位之前的位保持不变。比如，一个二进制数1100，减1后，得到1011。 ? 在前面两种情况中，我们发现，把一个整数减去1，都是把它最右边的1变成0（假设最右边的1位于第m位），而第m位右边若还有0的话，把0变成1，第m位左边的位保持不变。接下来，我们把一个整数和它减去1的结果做与运算。如 a ? = 1100 a-1 = 1011 ret = a & (a-1) = 1000 可见，把一个整数a减去1，再和原整数a做与运算，会把该整数a最右边的一个1变成0，那么，一个整数的二进制序列中有多少个1就可以通过这种方式算出来！ ? 以下是代码：

int numOf_1(int n) {
     int cnt = 0;
     while(n){
          ++cnt;
          n = n & (n-1);
     }
     return cnt;
}

 

至此，Simhash算法就算全部讲完了。 ? 【总结】 1、网页去重的基本框架?(1)特征词提取 --> (2)生成文档指纹 --> (3)相似性计算? 2、simhash算法，将一篇文档转换成二进制序列来表示 3、文档相似性计算-->计算两篇文档的海明距离-->计算二进制序列中"1"的个数 ?

---

参考： 1. 《这就是搜索引擎-核心技术详解》 ?

内容总结

以上是互联网集市为您收集整理的网页去重之Simhash算法全部内容，希望文章能够帮你解决网页去重之Simhash算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---