搜索引擎去重算法

搜索引擎去重算法

rude 暂无评论
搜索引擎技术

了解搜索引擎原理的都知道,搜索引擎在创建索引前会对内容进行简单的去重处理。

那么,在动不动就会以亿计出现的网页面前,搜索引擎是如何在短时间内对这些页面进行去重处理的呢?

其实,说起来也很简单,主要有三步:特征抽取—>文档指纹生成—>相似性计算。比较经典的几个去重算法,如下:

一、Shingling算法

所谓Shingling,即将文档中出现的连续汉字序列作为一个整体,为了方便后续处理,对这个汉字片段进行哈希计算,形成一个数值,每个汉字片段对应的哈希值成为一个Shingle,而文档的特征集合就是有多个Shingle构成的。

举个简单的例子:【搜索引擎在创建索引前会对内容进行简单的去重处理】。既定采用4个汉字组成一个片段,那么这句话就可以被拆分为:搜索引擎、索引擎在、引擎在创、擎在创建、在创建索、创建索引,直到的去重处、去重处理。

则这句话就变成了由20个元素组成的集合A,另外一句话同样可以由此构成一个集合B,将A与B求交得C,将A与B求并得D,则C除以D即为两句话的相似程度。

当然,在实际运用中,搜索引擎从效率计,对此算法进行了优化,新的方式被称之为SuperShingle,据说,此方法效率十分之高,计算一亿五千万个网页,该方法可以在3小时内完成,而按照上述的方法,即便是3千万个网页,也需要10天。

So,有兴趣的同学,建议自行研究下其原理。

二、SimHash算法

大神们说:SimHash算法可能是目前的去重算法之一,Google内部应该采用以SimHash算法为基础的改进去重方法来对网页进行预处理,而且已对此算法申请了专利保护。

比较有意思的,是其文档指纹计算方式以及相似文档查找方式。

1、文档指纹计算方式

首先,从文档内容中抽取一批能代表该文档的特征,并计算出其权值w(瞬间想起了TF-IDF算法);

然后,利用一个哈希函数将每个特征映射成固定长度的二进制表示,既定为6比特的二进制向量及其权值,则一篇文章就会变成如下所示“

100110 w1

110000 w2

……

001001 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,则可以认为是近似重复的网页。
文军二维码

今日说说

    问:做什么事情会让你成就感爆棚?

    答:做让你感觉心理畏惧的事情,做完之后你会发现,去TMD,不过如此。

站内搜索