XML地图 黑帽SEO培训为广大SEO爱好者提供免费SEO教程,致力于SEO优化、SEO服务
首页 > SEO教程 » 网页去重算法SimHash算法

网页去重算法SimHash算法

2018-10-13T11:34:29 | 人围观 | 关键词:网页去重算法SimHash算法--SEO培训


  网页去重算法SimHash算法
 

  经过实践证明,SimHash算法可能是目前最优秀的去重算法之一,Google内部应该采用以SimHash算法为基础的改进去重方法来对网页进行预处理,而且已对此算法申请了专利保护。
 

  严格来说,SimHash算法可以看做是局部敏感哈希框架(Locality Sensitive Hashing Schema)的一个实现特例。经过理论分析,本章前述章节讲到的“改进的Shingling算法”引入多个哈希函数,究其本质,也是局部敏感哈希框架的一个具体实现方式而已。
 

  局部敏感哈希框架之所以在海量文本处理方面大行其道,源于其有趣的特性:两个文档内容越相似,则其对应的两个哈希值也越接近,所以可以将文本内容相似性问题转换为哈希值的相近性问题。而利用哈希值,很明显比文本计算速度快得多,同时用哈希值表示文档,也大大节省了存储空间。这与一般哈希函数的使用目的截然相反,一般哈希函数为了减少冲突,尽可能均匀地将哈希值分布到不同数值空间。
 

  SimHash算法也可以划分为两个步骤:文档指纹计算和相似文档查找。文档指纹计算的目的是将一篇文本文档转换为固定大小的二进制数值,以此作为文档的信息指纹,相似性查找阶段则根据信息指纹来找出哪些文档是近似重复的。
 

  10.4.1 文档指纹计算
 

  图10-9是SimHash算法第1阶段的具体流程图,通过这个步骤将文档转换为二进制表示的文档指纹。其内容转换过程又可分为如下几个步骤。

 

  

 

  首先,从文档内容中抽取一批能表征文档的特征,至于具体实现,则可以采取不同的抽取方法,经过此步骤,获得文档的特征及其权值w。
 

  之后,利用一个哈希函数将每个特征映射成固定长度的二进制表示,如图10-9所示为长度等于6比特的二进制向量,这样每个特征就转换为6比特二进制向量及其权值。
 

  接下来,利用权值改写特征的二进制向量,将权重融入向量中,形成一个实数向量。假设某个特征的权值是w,则对二进制向量做如下改写:如果二进制的某个比特位是数值1,则实数向量中对应位置改写为数值w;如果比特位数值为0,则实数向量中对应位置改写为数值-w,即权值的负数。通过以上规则,就将二进制向量改为体现了特征权重的实数向量。
 

  当每个特征都进行了上述改写后,对所有特征的实数向量累加获得一个代表文档整体的实数向量。累加规则也很简单,就是将对应位置的数值累加即可。
 

  最后一步,再次将实数向量转换为二进制向量,转换规则如下:如果对应位置的数值大于0,则设置为二进制数字1;如果小于等于0,则设置为二进制数字0。在如图10-9所示的实例中,6个数值再次转换为长度为6比特的二进制数值110001。如此,就得到了文档的信息指纹,即最终的二进制数值串。
 

  10.4.2 相似文档查找
 

  对每个文档都按照上述规则进行映射,将文档转换为固定大小的二进制数值,在实际计算中,往往会将长度设定为64,即每个文档转换为64比特的二进制数值。
 

  对于两个文档A和B,其内容相似性可以通过比较二进制数值的差异来体现,内容越相似,则二进制数值对应位置的相同的0或者1越多,两个二进制数值不同的二进制位数被称为“海明距离”。比如假设文档A的二进制表示为1000001,而文档B的二进制表示为1100001,则只有第2个位置的二进制数字不同,所以其海明距离为1。不同的二进制数字个数越多,即海明距离越大,则文档越不相似,一般对于64位二进制数来说,判断两个文档是否近似重复的标准是:海明距离是否小于等于3,如果两个文档的二进制数值小于等于3位不同,则判定为近似重复文档。
 

  海量的网页经过上述步骤,转换为海量的二进制数值,此时如果新抓取到一个网页,如何找出近似重复的内容?
 

  一个很容易想到的方式是一一匹配(图10-10),将新网页Q转换为64比特的二进制数值,之后和索引网页一一比较,如果两者的海明距离小于等于3,则可以认为是近似重复网页。这种方法虽然直观,但是计算量过大,所以在以亿计的网页中,实际是不太可行的。

 

  

 

  为了加快比较速度,SimHash采取了变通方法,其本质思想是将索引网页根据文档指纹进行分组,新网页只在部分分组内进行匹配,以减少新文档和索引网页的比较次数。
 

  图10-11展示了这种思想的具体实现方法,首先对于64位长度的二进制数值进行分块,每16位作为一块,这样每个二进制数值被划分为4块,可分别以A、B、C、D块来命名。对于海量的索引网页,依据分块进行聚类,比如对于A块来说,根据其A块内16位二进制聚类,如果16位二进制都相同,则这些网页被看做是一个聚类,即一组,这样根据A块就可以将所有索引网页分成若干组数据。对于B、C和D来说也是如此,即相同的16位二进制网页作为一个分组。如此,就将所有索引网页聚合成很多组小的数据集合,每一组必有连续16位二进制数字是相同的。

 

  

 

  对于新抓取的网页,同样将64比特二进制数据分为4块:Q1、Q2、Q3、Q4。在索引网页的分组中,找到对应A块16位和Q1完全相同的那个分组,之后与分组内的网页一一比较来查找哪些网页是近似重复的。对于Q2、Q3和Q4也做同样处理。这样就可以用较少的代价,找到全部索引网页中和新抓取网页近似重复的内容。
 

相关内容推荐:

Top