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

网页去重算法SpotSig算法

2018-10-13T11:48:07 | 人围观 | 关键词:网页去重算法SpotSig算法--SEO培训


  网页去重算法SpotSig算法
 

  SpotSig是个很有趣的算法,最初算法设计者是为了解决新闻内容的近似重复判断而提出这个方法的。
 

  这个算法基于如下观察:很多新闻的主体内容大致相同,但是页面布局往往差异很大,比如有很多导航链接或者广告链接及其文字。那么,新闻主体和页面布局区域在使用文字上有何种明显差异呢?一个很明显的差异是:停用词在两者中的分布是不一样的,新闻正文中停用词一般是比较均匀而频繁出现的,但是在其他区域中却很少出现停用词。SpotSig提出者觉得这个差异可以被用来识别近似重复新闻。
 

  SpotSig算法整体框架也符合本章第1小节所述,但是在具体实现方法上有独特之处。
 

  10.5.1 特征抽取
 

  观察到上述的新闻正文和其他区域中停用词分布的差异,SpotSig算法考虑用停用词相关的词语片段作为文档的特征。图10-12给出了一个特征提取的实例。

 

  

 

  首先确定要使用的部分停用词,并以这些停用词在网页中出现的位置作为锚点,在图10-12的例子中,选取单词a、an、the、is,以这4个停用词作为锚点。从锚点向后顺序扫描,取固定个数的单词作为特征构成部分,比如例子中第1次出现的a,后面紧跟着单词序列“rally to kick”,假设锚点后跟单词个数设定为2,即取单词rally和kick作为这个锚点的特征组成部分,将停用词to过滤掉,这样a:rally:kick就组成了第1个特征。按照同样的方式可以获得文档所有的特征,组成特征集合,以此来表征这个文档。
 

  文档特征是根据停用词来选取的,如果两个网页内容相同,只是布局结构不同,因为页面布局文字很少包含停用词,所以从页面布局内几乎不会抽出特征。也就是说,页面布局对于判断后续内容近似文档基本没有负面影响,这也是SpotSig算法一个显著的特色。
 

  另外一个与前述去重算法的不同之处在于:SpotSig算法直接以文本串作为特征,而正如前述章节所讲,其他算法大都会将文本特征转换为数字特征,而SpoSig并未如此做。
 

  10.5.2 相似文档查找
 

  获得文档的特征集合后,与Shingling算法类似,SpotSig采用Jaccard来计算文档之间的相似性。考虑到计算量过大,SpotSig采取了两个技术手段来加速查找过程:文档分组和倒排索引。
 

  如果对文档分组,给定一个待判网页,则无须和全部索引网页一一比较,只需要找到合适的分组,与分组内网页比较即可,这样确实可以极大地提升系统速度。上节所述SimHash也采取了类似分组的思路来加快计算速度。
 

  但是如何对文档分组?其依据是什么呢?SpotSig算法对网页集合进行分组是基于如下观察:因为采用的是Jaccard公式来计算两个文档的相似性,而且我们只需要找到文档特征重叠度足够高的相似文档即可,那么对于相似性得分可能很低的文档,则尽可能不去匹配。仔细考察Jaccard公式,可以得出结论,如果两个文档A和B,其长度相差太大,利用Jaccard公式计算出的两者的相似性一定很低,即两者不可能是近似重复文档。所以对于某个待判文档A来说,与其相似的文档,长度一定与文档A的长度相差不远。既然如此,可以在文档转换为特征集合后,根据特征集合的大小对文档集合进行分组,而在进行相似性计算时,只在合适的分组内一一比较,以此加快查找速度。
 

  为了进一步加快匹配速度,SpotSig算法对于每个分组内的网页,分别建立一套倒排索引,如图10-13所示是分组k建立的倒排索引片段。对于每个特征,建立倒排列表,其中d代表文档编号,后面的数字代表这个特征在文档d出现的次数,即TF,同时,倒排列表项根据TF值由高到低排序。这样在计算Jaccard相似度的时候,可以通过动态裁剪的方式只匹配分组内的部分网页即可,不需要对分组内任意网页都计算Jaccard相似度,通过此种手段进一步加快了计算速度。

 

  

相关内容推荐:

Top