搜索引擎页面去重算法之I-Match算法

互联网中存在了大量的重复页面，据统计表明近似重复页面的数量占据网站总数量的29%，而完全重复页面占据了22%。这些重复的页面对搜索引擎来说占据了很多的资源，因此搜索引擎对页面的去重也是搜索引擎中很重要的一个算法。因此今天就跟大家分析下搜索引擎页面去重算法-I-Match算法。

对于I-Match算法来说主要是根据大规模的文本集合进行统计，对于文本中出现的所有单词，按照单词的IDF（逆文本词频因子）来进行由高到低的排序，除去得分最高和得分最低的单词，保留剩下的单词最为特征词典。这一步骤主要是删除文本中无关的关键词，保留重要关键词。下面是I-Match流程示意图：

I-Match流程示意图

获得全局特征词典之后，对需要去重的页面，扫描下就能获得该页面上出现的所有单词，对于这些单词根据特征词典过滤：保留在特征词典上出现的单词，用来表达文档的主要内容，删除没有在特征词典中出现的内容。提取出对应的特征词之后在利用哈希函数对特征词汇进行哈希计算，获得的数值就是该文档的文本指纹。

所有文档都统计完之后如果想查看两篇文档是否重复只需要查看文档的文本指纹是否近似，如果近似则表示两篇文档重复。这样的比对方式很直观而且效率也很高，去重效果比较明显。

我们seo在做文章伪原创的时候经常会把文章的词语和段落调换位置，以此想欺骗搜索引擎认为这是一篇原创的文章，但是I-Match对文档之间的单词顺序并不敏感。如果两篇文章中包含的单词一样仅仅是调换了单词的位置，那么I-Match算法还是将两篇文章认为是重复文章。

但是这个算法还是有很多问题存在。1，容易出现误判。尤其是面对短文本的时候，短文本本身单词比较少，经过特征词典过滤之后只保留很少的特证词，这样容易把两篇原本不重复的文档误认为重复，这个对短文档来说情况比较严重。2.稳定性不好，对文档修改敏感。假如对文档A做出一点小修改后生成文档B，那么这个算法很可能判断出两篇文档为不重复文档。例如：我们在文档A中加入一个单词H，生成文档B。I-Match算法在进行计算的时候，两篇文章仅仅相差一个单词H，如果单词H不再特征词典中那么两篇文章的特证词相同即判定为重复文档，但是会出现这种情况，单词H出现在特征词典中，那么文本B比文档A多出一个特征，该算法很可能就会判定两篇文档不重复。这就是I-Match最大的一个问题。

基于I-Match出现的这种问题，有人对该算法进行了改进。原算法对文档的改变非常敏感，主要是因为对单一特征词典的过度依赖，改进后的I-Match就是减少对特征词典的依赖性。可以采用多个特征词典，只要每个特征词典大体相近就可以忽略细小的差别。

改变后的I-Match算法主要是：类似I-Match原始算法，形成一个特征词典，为了和其他词典相区别可以成为主特征词典；然后根据主特征词典衍生出若干小的辅助特征词典。为了保证特征词典的主体相同，可以从主特征词典中随机删除若干词典项然后生成一个新的特征词典，这个特征词典就叫做辅助特征词典，重复若干次数后就可以获得若干辅助特征词典。当两篇文档进行对比的时候可以对主特征词典和辅助特征词典一起比对，只要保证每个特征词典的大体内容相同，忽略细小差异就能判定文档是否重复。下图是I-Match改进后的示意图：