1. 背景
1.1 重复网页的类型
在互联网中，近似重复网页(Near Duplicate Web Page)的数量占网页总数的比例高达29%，完全相同的页面占全部页面的22%，其中根据内容和布局又可以分为四种。
| 内容相同 | 部分重要内容相同 | |
|---|---|---|
| 布局相同 | 完全相同网页 | 布局重复页面 |
| 布局不同 | 内容重复页面 | 部分重复页面 |
1.2 网页去重的作用
网页去重的目的，就是为了全面且快速的发现这些重复页面。
去重对于搜索引擎有很多好处
- 对于重复页面，可以在数据库中删除以节省存储资源
- 如果可以预发现重复页面，就可以避开抓取，提高网页的收集速度
- 如果某网页的镜像程度高，也可以从侧面反映出页面质量，作为排序的参考因素
- 如果用户点击了死链，可以将其引导到重复的其他网页上，减少死链率。
1.3 搜索引擎中进行网页去重的难点
去重这一环节在很多场景下，在搜索引擎场景下难点主要在于两个
- 需要设计算法，能够检测两个网页之间的相似度，而设计的难点是需要兼顾检测算法的准确率与召回率，如果召回率低，会造成很多该去重的网页没有被去重掉，网页去重的效果会大打折扣，如果准确率低，则会误杀很多并不相似的网页，影响搜索质量。
- 增量数据需要能够快速的对海量存量数据进行比对，由于搜索引擎网页库的存量数据高达百亿，因此去重的效率也是必须考虑到的一环。
从难点中也可以看出，准确率、召回率、检测效率是设计网页去重的关键评价指标，这三者都很重要但又相互冲突。因此，权衡利弊是去重算法设计中的关键，大多数的去重算法，都是在三个指标中权衡出一个适合业务场景的平衡点。
2. 通用去重框架
网页去重一般发生在爬虫抓取之后进入数据库的环节，如果在入库过程中发现抓取到的网页与数据库中的存量网页有重复，就进行去重。
去重的过程五花八门，但大部分算法的整体流程可以归结为下图。
- 特征抽取：从原始文档中抽取一系列重要的特征形成特征集合，这一步是为了抽取出文档中的关键信息，抛弃无关紧要的信息。特征保留的越完整，就越能还原网页的关键信息，在后续的相似度检测中就越能保障准确性，而之所以要抛弃一些信息，则考虑到计算性能。因此在这一步，如何选取需要抽取的特征，就是算法需要权衡准确率与计算性能的一个点。
- 信息压缩：信息压缩的目的同样是为了加快计算速度，为了避免网页之间特征两两间比对带来的多次消耗，压缩成指纹可以再次减少网页之间比对的复杂度，压缩后的指纹数量将远远小于压缩前的特征集合。同样的，压缩也会带来文档信息的丢失，同样需要权衡计算性能与准确性。
- 相似性计算：将网页指纹与网页库中存量的网页集合比对。同样的，如果是两两比对的话，效率是很低的，因此不同的算法采用了不同的策略来加快比对效率，例如将存量数据分组，每条数据只比对自己分组的数据。
3. 去重算法
3.1 Shingling算法
3.1.1 特征抽取
Shingling算法以Shingles作为文档特征（将文档中出现的连续单词序列作为一个整体并哈希成数值，每个数值称为一个Shingles）。一篇文档可以转化为多个Shingles组成的特征集合。
如下图所示是将一个文本转换成Shingles集合的实例，以2个汉字长度为滑动窗口，从头开始向后移动，每移动一次就将窗口内的连续汉字作为一个整体进行Hash得到一个Singles，最终所有的Shingles组成了该文档的特征集合。
3.1.2 信息压缩
在抽取完特征之后，实际上利用Jacaard相似性已经可以对网页进行两两之间的相似性检测，但这种做法的效率并不高，原因在于Shingling转化之后的文档集合过大且与文档原长度相关，原文档的长度越长，特征集合就会越大。即使需要比对的网页很短，但由于网页库中的被比对网页可能很大，同样会造成计算量的负担。信息压缩的目的，就是为了解决这两个问题：
- 减少特征集合大小
- 固定特征集合数目
下图是信息压缩的示例图，信息压缩引入了n个哈希函数（图中为两个，一个蓝色的一个绿色的），原数据集合的每个Singles经过哈希函数都可以转化为一个新的Singles list，从中通过选取最小的值来作为压缩后的特征，这样就能固定生成一个新的包含n个特征的特征集合。这个步骤称为SuperShingle。
3.1.3 相似性检测
Shingling的相似性检测使用了Jaccard算法，其主旨就是查看特征集合之间相同特征的占比
\(Jaccard(A,B)=\frac{|C|}{|A + B|}\)
当然，上文也提过，针对全量数据两两比对的检测是低效的，针对文档集合的Jaccard相似性一般会采用并查集(Union-Find)算法来加速。
3.2 I-Match算法
3.2.1 算法流程
I-Match算法需要事先计算出一个全局的特征字典，即对存量数据进行一个大规模的语料统计，将单词按照IDF值排序，并且去掉得分过高或者过低的单词，实验证明保留中间的单词效果最好。
- IDF值指的是单词在文档中的区分度，IDF越大代表单词区分度越大。
在获取单词词典之后，针对每个网页扫描一遍，将其中的单词集合抽取出来，并用单词词典过滤，找出出现在词典中的单词，就形成了特征集合。利用哈希函数将特征集合整体进行计算，得到一个唯一的数值作为网页的指纹。将指纹与存量指纹比对是否相同，就可以认为是相似网页。
- 为什么这里选择将特征集合直接hash成一个值比对，而Shingling是将特征集合采用Jaccard比对，原因和算法设计有关，Jacaard的特征相同的条件太苛刻，只要稍有不同就会有部分特征不同，因此只要满足有一些特征相同就可判定为相同，I-Match基于的假设是重要单词全部相同的网页被认为是相似，因此只有特征集合完全相同的网页能够被判定为相似，不需要比对特征集合之间的相似程度，为了加速可以直接将特征集合hash成一个值。
3.3.2 算法改进
原始的I-Match算法存在两个比较突出的问题
- 当文档是短文本的时候，在过滤之后只有少量的单词作为文档的特征，单词的数量很少的时候很容易出现误判，将原本不相似的网页去重。
- i-Match的稳定性不佳，如果原网页做了一些微小的改动，例如新增或减少了一个词典中的关键单词，那原始的IMatch流程就完全应对不了这种情况，这也是上面说的，I-Match只检测最终特征完全相同的指纹，无法细化到特征集合之间的相似度。这是I-Match为了提升计算效率而付出的代价。
针对第一个问题，本质是因为特征词典的覆盖率不足造成的短文本网页信息丢失，这个问题主要是通过提升特征词典的覆盖率来解决——这也是准确率与性能需要权衡的一个点。
针对第二个问题，通过Shingling算法我们不难引申想到，如果能直接比对特征集合，而不是比对单一哈希值，就能够对这种“微小的差异”有所感知，但倘若不进行压缩，直接比对特征集合，同样会面临特征集合长度不固定、特征太多的问题。因此，改进算法采用的方式是引入多份特征词典，这几份特征词典也是大致相同又有微小差异，从而生成多个最终特征，而网页间的最终特征只要有一个重复的，就被认为是相似网页。
那么如何生成多份“大致相同又有微小差异”的特征词典呢，可以从将原始的特征词典作为主词典，然后从主词典中随机抽取很小比例的词典项丢弃，剩下的特征构成辅助词典，重复若干次就可以生产若干份辅助词典。
- 这种算法的改进与SuperShingle殊途同归，都是将大的特征集合压缩为了固定长度的小特征集合，从而降低检测的开销。
3.3 SimHash算法
实践证明，SimHash算法可能是目前最优秀的去重算法之一。
3.3.1 指纹计算
SimHash的指纹计算算法如下图分为几个步骤
- 从文档中抽取一批能够表征文档的特征（特征可以采用不同的策略），并且给每个特征以权值
- 用一个哈希函数将特征转化为不同的数据并转化为二进制
- 对每个特征每一位二进制的二进制数据附上权值，为1的那位为w，为0的那位为-w，将每个特征改为一个能够体现权重的向量
- 将所有特征的向量累加，得到一个累计的向量
- 将累加后的向量转化为二进制向量，其中每一维如果大于0，则对应位为1，反之为0，就得到了最终的指纹。
3.3.2 相似性比对
根据以上特征得到的指纹，可以通过比对指纹之间的海明距离来确定网页之间的差异性。一般对于64位二进制数来说，如果海明距离小于等于3，就可以认为是近似重复文档。
- 两个二进制数之间二进制位数不同被称为海明距离。
同样的，针对全量数据两两匹配是不可行的，SimHash采用了分组的办法，将存量数据进行分组，每个网页只对对应组内的数据进行匹配，具体的分组方式为：
- 对64位长度的二进制数值分块，每16位作为一块，划分为4块
- 依据分块进行聚类，例如如果两条数据的前16位都相同，则他们在A块中是一个相同的聚类
- 如此，就将所有网页聚合为多个小的数据集合
对于需要比对的网页，只要分别比对其在A、B、C、D中相同的聚类，就可以高效的找出与其相似的网页。
4. 总结
本文阐述了去重算法的大体框架以及3个去重算法，去重算法之间虽然具体是实现方式相同，但大致思路相似，且都想办法在准确性与计算性能中权衡。
搜索引擎场景下，具体说是在海量文本处理的场景下，大量使用到了局部敏感哈希框架，SimHash和改进之后的Shingling算法都是局部敏感哈希框架的一个具体实现。其原理是两个文本越相近，其哈希函数也越相近，而比较哈希值的性能显然要比文本计算高效多了，哈希值来表示文档也可以大大减少存储空间。