网页去重时机一般在爬虫新抓取到网页后，对网页建立索引前。一个典型的去重算法由特征抽取、文档指纹生成和相似性计算3个关键环节构成。

能够快速处理海量数据是搜索引擎对去重算法的内在要求，去重算法设计必须兼顾准确性和运行效率，在两者之间取得平衡。

4种典型的去重算法：Shingling算法、I-Match算法、SimHash算法、SpotSig算法。看似迥异，很多基本思路相近。

统计结果表明，近似重复网页（NearDuplicateWebPage）的数量占网页总数的比例高达全部页面的29%，而完全相同的页面大约占全部页面的22%，即互联网页面中有相当大比例的内容是完全相同或者大体相近的。主体内容是几乎完全相同的，但是两个页面的网页布局有较大差异，此种情况在互联网中非常常见。

近似重复网页有多种类型，这些重复网页有的是没有一点儿改动的副本，有的在内容上稍做修改，比如同一文章的不同版本，一个新一点，一个老一点，有的则仅仅是网页的格式不同（如HTML、Postscript）。内容重复可以归结为以下4种类型。

类型一：如果两篇文档内容和布局格式上毫无差别，则这种重复可以叫做完全重复页面。

类型二：如果两篇文档内容相同，但是布局格式不同，则叫做内容重复页面。

类型三：如果两篇文档有部分重要的内容相同，并且布局格式相同，则称为布局重复页面。

类型四：如果两篇文档有部分重要的内容相同，但是布局格式不同，则称为部分重复页面。

所谓近似重复网页发现，就是通过技术手段快速全面发现这些重复信息的手段，如何快速准确地发现这些内容上相似的网页已经成为提高搜索引擎服务质量的关键技术之一。

发现完全相同或者近似重复网页对于搜索引擎有很多好处：

1、首先，如果我们能够找出这些重复网页并从数据库中去掉，就能够节省一部分存储空间，进而可以利用这部分空间存放更多的有效网页内容，同时也提高了搜索引擎的搜索质量和用户体验。

2、其次，如果我们能够通过对以往收集信息的分析，预先发现重复网页，在今后的网页收集过程中就可以避开这些网页，从而提高网页的收集速度。有研究表明重复网页随着时间不发生太大变化，所以这种从重复页面集合中选择部分页面进行索引是有效的。

3、另外，如果某个网页的镜像度较高，往往是其内容比较受欢迎的一种间接体现，也就预示着该网页相对重要，在收集网页时应赋予它较高的优先级，而当搜索引擎系统在响应用户的检索请求并对输出结果排序时，应该赋予它较高的权值。

4、从另外一个角度看，如果用户点击了一个死链接，那么可以将用户引导到一个内容相同页面，这样可以有效地增加用户的检索体验。因而近似重复网页的及时发现有利于改善搜索引擎系统的服务质量。

实际工作的搜索引擎往往是在爬虫阶段进行近似重复检测的，当爬虫新抓取到网页时，需要和已经建立到索引内的网页进行重复判断，如果判断是近似重复网页，则直接将其抛弃，如果发现是全新的内容，则将其加入网页索引中。

对于网页去重任务，具体可以采取的技术手段五花八门，各有创新与特色，但是如果仔细研究，大部分算法的整体流程和框架有诸多相似之处，本节参考一些实践效果较好的去重算法，并归纳整理，总结了相对通用的算法框架。尽管很多算法看似迥异，其框架实则雷同，这与去重任务本身的要求有密切关系，即需要算法能够对海量数据进行快速处理。

对于给定的文档，首先通过一定的特征抽取手段，从文档中抽取出一系列能够表征文档主体内容的特征集合。这一步骤往往有其内在要求，即尽可能保留文档重要信息，抛弃无关紧要的信息。之所以要抛弃掉部分信息，主要是从计算速度的角度考虑的，一般来说，抛弃的信息越多，计算速度会越快，但是如果抛弃得过多，在此步骤可能会丢失重要信息，所以不同的算法在此步骤需要做出权衡，在速度和准确性方面要通盘考虑，尽可能兼顾两者。

在将文档转换为特征集合后，很多算法就可以直接进入查找相似文档的阶段，但是对于搜索引擎来说，所要处理的网页数量以亿计，算法的计算速度至关重要，否则算法可能看上去很美，但是无实用效果。为了能够进一步加快计算速度，很多高效实用的算法会在特征集合的基础上，对信息进一步压缩，采用信息指纹相关算法，将特征集合压缩为新的数据集合，其包含的元素数量远远小于特征集合数量，有时候甚至只有唯一的一个文档指纹。在此处与在特征抽取阶段一样，有可能会有信息丢失，所以也需权衡压缩率和准确性的问题。

当把文档压缩为文档指纹后，即可开始通过相似性计算来判断哪些网页是近似重复页面。对于去重来说，最常用的文本相似性计算是Jaccard相似度，大部分去重算法都是以此作为评估两个文档是否近似的标准。另外，由于数据量太大，在计算相似性的时候，如果一一进行比较显然效率很低，在此处不同算法往往会采用各种策略来加快相似性匹配过程，比较常见的做法是对文档集合进行分组，对于某个文档，找到比较相似的分组，和分组内的网页进行一一比较，这样可以大大减少比较次数，有效提升系统效率。

Shingling算法可以被视为由两个大的步骤组成：第1步从文档中抽取能够代表文档内容的特征，第2步则根据两个文档对应特征集合的重叠程度来判断是否近似重复。

之所以被称为Shingling算法，是因为该方法以Shingles作为文档的特征。所谓Shingles，即将文档中出现的连续单词序列作为一个整体，为了方便后续处理，对这个单词片段进行哈希计算，形成一个数值，每个单词片段对应的哈希值称为一个Shingle，而文档的特征集合就是由多个Shingle构成的。

可以假想有一个固定大小的移动窗口从文档第1个单词（单字）开始依次移动，每次向后移动一个单词（单字），直到文本末尾。图中是以3个汉字作为移动窗口的大小，所以第1个长度为3的汉字串是“新浪发”，对这个汉字串进行哈希计算（Shingling算法在此处采用RabinFingerPrint算法），即得到一个shingle，然后窗口向后移动一个汉字，形成第2个汉字串“浪发布”，同样对汉字串进行哈希计算，得到第2个shingle，依此类推，窗口不断后移，直到末尾的汉字串“户破亿”为止，这样所有的shingle组成的集合就是文档对应的特征集合。

如果每个文档都通过如上方式转换为特征集合，如何计算两个文档是否是近似重复网页？Shingling算法考察两个特征集合的重叠程度，重叠程度越高，则越可能是近似重复网页。具体而言，采用了Jaccard相似性来计算这个重叠程度。

Jaccard相似性计算的示意图，这是一种计算集合相似性的经典方法，对于两个集合A和B来说，两者的重叠部分由C来表示。图中集合A包含4个元素，集合B包含5个元素，而两者相同的元素有2个，即集合C的大小为2。Jaccard计算两个集合相同的元素占总元素个数的比例，因为图中集合A和B共有7个不同元素，相同元素个数为2，所以集合A和集合B的相似性即为2/7。

Shingling算法通过以上两个步骤即可计算哪些网页是近似重复网页，但是这种方法在实际运行时，计算效率并不高，如果网页数量大，运行时间会过长，并不实用。原因在于把一个文档转换为以shingles表示的特征集合形式后，这个文档对应的特征集合仍然太大。同时对于不同长度的文档来说，转换后的特征集合大小各异。而这两点对于高效计算来说都是不利因素。为了加快计算速度，能否将文档的特征集合变为固定长度，同时使得这个长度远远小于原始的特征集合？

Fetterly等人提出了针对原始Shingling算法改进的算法，其基本思想即如上所述，对于不同的网页，将其转换为固定大小的特征集合，而且这个特征集合的大小要远小于原始Shingling转换后特征集合的大小，以此手段来大大提升运算效率。

改进的Shingling算法思路示意图

前面若干计算过程与原始Shingling算法是一致的，即首先将一个文档转换为由shingles构成的特征集合。为了能够将文档特征映射为固定大小，引入m个不同的哈希函数，形成哈希函数簇。对于某个特定的哈希函数F，对每个shingle都计算出一个对应的哈希数值，取其中最小的那个哈希数值作为代表。这样m个哈希函数就获得了m个哈希数值，如此就把文档的特征集合转换为固定大小m，同时这个数值也比很多由shingles构成的特征集合小很多。通过如上方式，即可把文档对应的特征集合映射为一个固定大小，而且长度比原始方法小很多的数值向量，以加快后续相似度计算的速度。

图中为了方便说明问题，哈希函数簇只包含了两个哈希函数，而实际使用的时候往往会使用84个不同的哈希函数，即将一个文档映射成为由84个数值构成的数值向量。为了进一步加快计算速度，可以将84个数值进一步压缩：以14个连续数值作为一块，将84个数值分为6块，利用另外一个哈希函数对每一块的14个数值进行哈希计算，进一步将文档特征转换为6个哈希数值，如果任意两个文档有两个以上的哈希数值是相同的，即可认为是近似重复文档，这个技巧被称为SuperShingle。

至于计算文档集合的Jaccard相似性，一般会采用Union-Find算法。Union-Find算法是经典的计算等价类的高效算法，参考文献众多，此处即不赘述其细节，重点仍然放在去重算法本身。

经过如上诸般优化措施，改进的Shingling算法计算效率已非常高。实验表明，计算一亿五千万个网页，该方法可以在3小时内计算完毕，而原始的Shingling算法即使是处理三千万网页，也需10天才可完成，应该说速度的提升是非常显著的。

最初的I-Match算法是由Abdur等人于2002年提出的，其基本流程也遵循通用去重算法框架。

图是I-Match算法流程的示意图。对于该算法来说，非常重要的一个步骤是事先计算出一个全局的特征词典，具体到I-Match算法来说，则是根据大规模语料进行统计，对语料中出现的所有单词，按照单词的IDF值由高到低进行排序，之后去除掉一定比例IDF得分过高及得分过低的单词，保留得分处于中间段的单词作为特征词典，实验表明以这些单词作为特征，其去重效果较好。

获得全局的特征词典后，对于需要去重的网页，扫描一遍即可获得在该页面中出现过的所有单词，对于这些单词，用特征词典进行过滤：保留在特征词典中出现过的单词，以此作为表达网页内容的特征；没有在特征词典中出现过的单词则直接抛弃。通过这种方式，抽取出文档对应的特征，之后利用哈希函数（I-Match算法采取SHA1作为哈希函数）对文档的所有特征词汇整体进行哈希计算，得到一个唯一的数值，以此哈希数值作为该网页的信息指纹。

对网页集合里所有网页都计算出相应的信息指纹后，如何判断两个网页是否是近似重复网页？I-Match算法于此很直观，可以直接比较两个网页对应的信息指纹，如果两者相同则被认为是近似重复网页。

Shingling算法的特征抽取过程，从上述对应的1-Match算法的特征抽取过程可以看出，1-Match算法抽取出的文档特征是一个个独立的单词，单词之间的顺序没有被考虑进来，所以1-Match算法对于文档之间单词顺序的变化并不敏感，如果两个文档所包含的单词相同，但是单词顺序进行了变换，I-Match算法一定会将其算做重复内容。

1-Match算法的优点在于其效率很高，因为每个文档被映射为单一的哈希值，以单一数值作为文档的表征，必然在计算速度上优于多值表征，因为可以避免复杂的集合运算。

但是1-Match算法也包含不少问题，首先，对于短文本来说，很容易出现误判，也就是说两个文档本来不是近似重复网页，但是I-Match算法容易将两者判断为重复内容。之所以会如此，原因就在上文提到的特征词典，假设两个短文本内容并不相似，但是经过特征词典过滤后，只能保留很少几个单词作为文档的特征，而如果这几个单词是相同的，那么自然会将这两个文档误判为近似重复网页。其根本原因在于特征词典覆盖不足，导致文档很多信息被过多过滤，对于短文本这个问题尤其严重。

另外一个更加突出的问题是，I-Match算法的稳定性不好。所谓稳定性不好，指的是对于某个文档Ａ做了一些较小的内容变动，形成新文档B，本来应该将两者看做近似重复文档，但是I-Match算法很可能无法将其计算为我们希望的结果，即I-Match算法对于增删单词这种变化比较敏感，这是由于I-Match算法所采用的特征词典机制和SHA1哈希算法共同导致的。

我们可以考虑如下的极端情形：对于某个文档A，我们向其中加入一个新的单词w（即w没有在A中出现过），形成文档B。通过I-Match算法的特征词典对两个文档进行特征过滤，因为两者的差别只有这个新加入的单词w，所以如果单词w不在特征词典中，那么文档A和文档B的对应特征集合相同，所以哈希后的信息指纹也一定相同，1-Match会认为两个文档是近似重复文档，这是我们想要的结果；但是，如果单词w出现在特征词典中，那么文档B的特征集合会比文档A多一个特征，即单词w，而SHA1哈希算法对于这种差异很敏感，会将两个文档映射成两个不同的信息指纹，即出现了稳定性不佳的问题。很明显，这个问题是由特征词典和SHAI哈希算法共同决定的，可以看做是I-Match算法为了计算效率所付出的代价。

为了解决原始I-Match算法存在的稳定性不佳问题，Kolcz等人提出了改进算法。其基本出发点也很直观：原始I-Match算法对于文档内容改变过于敏感，原因在于其严重依赖于特征词典的选择，为了减少这种依赖性，可以考虑同时采用多个特征词典而每个特征词典大体相近，同时又必须有微小的差异。

对于某个需要判别是否重复的文档A，对应每个特征词典，生成多个信息指纹。如果向文档A增加新的单词w形成文档B，因为存在多个大致相同但有微小差异的特征词典所以有很大可能某个特征词典不包含这个单词，所以通过这个特征词典算出的文档B的信息指纹和文档A是相同的。在判断A和B两个文档是否重复时，同时考虑多个信息指纹的情况，只要两个文档对应的众多信息指纹中有任意一个是相同的，则可以判定两者是重复文档。这样就解决了I-Match算法对增删单词过于敏感的问题。

那么如何形成多个“大致相同又有微小差异”的特征词典呢？Kolcz是如此解决这个问题的：类似于原始1-Match算法，形成一个特征词典，为了和其他词典区分，可以称为主特征词典；然后根据主特征词典衍生出其他若干个辅助特征词典，为了能够达到词典内容大致相同，又能有微小差异，可以考虑从主特征词典中随机抽取很小比例的词典项，之后将其从主特征词典中抛弃，剩下的词典项构成一个辅助特征词典，如此重复若干次就可以形成若干个辅助特征词典，这些辅助特征词典和主特征词典一起作为算法采用的多个特征词典。通过如此做法，即可保证每个词典大致内容相同，其间又有微小差异，能够达到所期望的效果。

原始的I-Match算法将文档映射成唯一的信息指纹，虽然增加了计算效率，但是明显存在信息表达不足的问题，改进的1-Match算法本质上是将一个文档映射成多个信息指纹，可以认为是将文档里更多的信息进行了编码，这种做法与前述章节的SuperShingle的做法类似，SuperShingle也是将文档压缩成多个信息指纹，区别在于：SuperShingle是将信息由多到少进行进一步压缩，而改进的I-Match算法是从唯一的信息指纹将信息由少到多进行扩展。虽是殊途，毕竟同归。

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

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

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

SimHash算法第1阶段的具体流程图

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

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

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

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

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

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

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

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

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

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

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

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

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

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

观察到上述的新闻正文和其他区域中停用词分布的差异，SpotSig算法考虑用停用词相关的词语片段作为文档的特征。

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

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

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

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

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

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

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

若有收获，就点个赞吧

搜索引擎高级命令

搜索引擎核心技术详解8—网页反作弊

搜索引擎核心技术详解6—链接分析

搜索引擎核心技术详解5—检索模型与搜索排序

搜索引擎核心技术详解3—搜索引擎索引

搜索引擎核心技术详解2—网络爬虫

搜索引擎核心技术详解1—搜索引擎及其技术架构

搜索引擎工作原理介绍

知识像烛光，能照亮一个人，也能照亮无数人

搜索引擎发展简史

搜索引擎工作原理介绍

搜索引擎核心技术详解5—检索模型与搜索排序