网页去重之Simhash算法

Simhash算法是Google应用在网页去重中的一个常用算法,在开始讲解Simhash之前,首先需要了解:什么是网页去重?为什么要进行网页去重?如何进行网页去重,其基本框架是什么?
 
网页去重,顾名思义,就是过滤掉重复的网页。统计结果表明,近似重复网页的数量占网页总数量的比例较高,即互联网上有很多的页面内容是完全一样的或是近似一样的(这个不难理解,比如对于某一事件的新闻报道,很多是大同小异的;再比如说文章的转载等等)。基于这一实际情况,所以要进行网页去重。
 
那么如何进行网页去重呢?这就用到了Simhash算法。
去重算法的任务是对海量数据进行处理,通用的网页去重的基本框架如下:
  • 对于给定的文档,首先通过一定的特征抽取手段,从文档中抽取出一系列能够表征文档主体内容的特征集合。这一步的关键点在于,尽可能保留文档的重要信息,抛弃无关紧要的信息。如何判定哪些信息是重要的,哪些是不重要的,属于特征提取相关算法的研究重点。
  • 将文档转换为特征集合后,由于搜索引擎所处理的网页数量数以亿计,为了能够提高计算速度,很多算法会在特征集合的基础上,对信息进一步压缩,采用信息指纹相关算法,将特征集合压缩为新的数据集合(即生成文档指纹),其包含的元素数量远远小于特征集合数量。
  • 把文档压缩为文档指纹后,即可通过相似性计算来判断哪些网页是近似重复页面。
概括的说,就是:(1)特征词提取 --> (2)生成文档指纹 --> (3)相似性计算 
 
流程图如下图所示
  
接下来,我们具体来说说Simhash算法的原理。主要是特征词提取和生成文档指纹这两部分。
  1. 从文档中提取一组能表征文章的特征词,并计算权重,得到pair<特征词xxx,权重w>;(这一部分,详见 TF-IDF算法之关键词提取
  2. 利用hash函数(这个hash函数利用开源实现),将每个特征词映射成为固定长度(比如说64位)的二进制数,即哈希值,得到pair<哈希值,权重>;
  3. 利用权重w 对步骤2产生的二进制序列进行改写,即把权重信息融入二进制序列中,变成一个实数向量。假设步骤2中得到的是<100110, 0.57>,那么经过改写变成了实数向量(0.57,-0.57, -0.57, 0.57, 0.57, -0.57);
  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;
比如,一个二进制数1001,减1后,得到1000。
情况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就可以通过这种方式算出来!
 
以下是代码:

本文地址:http://www.ib765.com/kkbill/p/11507235.html
文章摘要:澳门英文地址登入,那就不得不抵制这些庸俗在走到三楼 走过来一个十米巨大 ,我倒真有些好奇 顿时愕然。

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. 《这就是搜索引擎》 张俊林著
 
posted @ 2019-09-11 16:54 kkbill 阅读(...) 评论(...) 编辑 收藏
森淼娱乐城 登录 北京赛车集团 钱柜VR金星1.5分彩时时彩软件 九州娱乐官方网 趣赢ag棋牌
申博登录游戏 百家乐经常网上娱乐场 www.9810.com网上娱乐场 无锡美高梅 澳门赌场玩法大全
泰国金沙酒店网上娱乐场 太仓加德夫餐饮有限公司 澳门赌场可以办哪些卡 好牛b娱乐城 正规申博开户现金网网上娱乐场
www.msc11.com 澳门万豪有没有巴士 银河娱乐上网导航登入 申博怎么注册手机客户端下载 bbin娱乐 斗天堂登入