搜索引擎去重算法.docx

搜索引擎去重算法了解搜索引擎原理的都知道，搜索引擎在创建索引前会对内容进行简单的去重处理那么，在动不动就会以亿计出现的网页面前，搜索引擎是如何在短时间内对这些页面进 行去重处理的呢？其实，说起来也很简单，主要有三步：特征抽取—＞文档指纹生成—＞相似性计算比较经典的几个去重算法，如下：—、Shingling 算法所谓Shingling，即将文档中出现的连续汉字序列作为一个整体，为了方便后续处理，对这个汉字片段进行哈希计算，形成—个数值，每个汉字片段对应的哈希值成为—个Shingle，而文档的特征集合就是有多个Shingle构成的举个简单的例子：【搜索引擎在创建索引前会对内容进行简单的去重处理】既定采用4 个汉字组成一个片段，那么这句话就可以被拆分为：搜索引擎、索引擎在、引擎在创、擎在 创建、在创建索、创建索引，直到的去重处、去重处理则这句话就变成了由20个元素组成的集合A，另外一句话同样可以由此构成一个集合B，将A与B求交得C，将A与B求并得D，则C除以D即为两句话的相似程度当然，在实际运用中，搜索引擎从效率计，对此算法进行了优化，新的方式被称之为SuperShingle，据说，此方法效率十分之高，计算一亿五千万个网页，该方法可以在3小 时内完成，而按照上述的方法，即便是3 千万个网页，也需要10 天。

二、SimHash 算法SimHash算法可能是目前最优秀的去重算法之一，Google内部应该采用以SimHash 算法为基础的改进去重方法来对网页进行预处理，而且已对此算法申请了专利保护SimHash算法中需要特别注意有文档指纹计算方式以及相似文档查找方式：1、文档指纹计算方式首先，从文档内容中抽取一批能代表该文档的特征，并计算出其权值w （这里可以延伸到 TF-IDF 算法）；然后，利用一个哈希函数将每个特征映射成固定长度的二进制表示，既定为6 比特的 二进制向量及其权值，则一篇文章就会变成如下所示“100110 w1110000 w2001001 wn接着，将权值融入向量，形成一个实数向量，规则为：特征1的权值为W1,如果二进 制比特位的值为1 ,则记录为W1，如果为0，则记录为-W1然后特征1就变成了 w1 -w1 -w1 w1w1-w1，其余类推，然后将这些进行进行简单的相加假定得到一个数值11 ， 205， -3， -105,1057,505最后一步，分别将大于0的值记录为1 ，将小于0的部分记录为0 ，则上述的数据就变 成了 110011，而这个数据，则可称之为这篇文章的指纹。

既定另一篇文章的指纹为100011 ，则二进制数值对应位置的相同的0或1越少，两篇 文章相似度越高而在实际的运用中，往往是将网页Q转换为64比特的二进制数值，如果两者对应位置 相同的0或1小于等于3，则可以认为是近似重复的网页。