网页去重之Simhash算法

Simhash算法是Google应用在网页去重中的一个常用算法,在开始讲解Simhash之前,先了解——什么是网页去重?为什么要进行网页去重?如何进行网页去重,其基本框架是什么?网页去重,顾名思义,就是过滤掉重复的网页。统计结果表明,近似重复网页的数量占网页总数量的比例较高,即互联网上有很多的页面内容是完全一样的或是相近的(这个不难理解,比如对于某一事件的新闻报道,很多是大...

网页去重之Simhash算法
Simhash算法是Google应用在网页去重中的一个常用算法,在开始讲解Simhash之前,先了解——什么是网页去重?为什么要进行网页去重?如何进行网页去重,其基本框架是什么?
网页去重,顾名思义,就是过滤掉重复的网页。统计结果表明,近似重复网页的数量占网页总数量的比例较高,即互联网上有很多的页面内容是完全一样的或是相近的(这个不难理解,比如对于某一事件的新闻报道,很多是大同小异的)。基于这一实际情况,所以要进行网页去重。
那么如何进行网页去重呢?这就用到了Simhash算法。
去重算法的任务是对海量数据进行处理,通用的网页去重的基本框架如下。
  • 对于给定的文档,首先通过一定的特征抽取手段,从文档中抽取出一系列能够表征文档主体内容的特征集合。这一步的关键点在于,尽可能保留文档的重要信息,抛弃无关紧要的信息。如何判定哪些信息是重要的,哪些是不重要的,就是算法研究的重点。
  • 将文档转换为特征集合后,由于搜索引擎所处理的网页数量数以亿计,为了能够提高计算速度,很多算法会在特征集合的基础上,对信息进一步压缩,采用信息指纹相关算法,将特征集合压缩为新的数据集合(即生成文档指纹),其包含的元素数量远远小于特征集合数量。
  • 把文档压缩为文档指纹后,即可通过相似性计算来判断哪些网页是近似重复页面。
概括的说,就是:(1)特征词提取 --> (2)生成文档指纹 --> (3)相似性计算
流程图如下图所示
https://www.guoxiongfei.cn/cntech/26837.html