Shingling算法
与上面说的通用去重算法框架相同，Shingling算法由两个大步骤组成，第一步是从文档中抽取能够代表文档内容的特征，第二步则是根据两个文档对应特征集合的重叠程度来判断文章是否近似重复。
第一步用一张图就能说清楚：
把文档按照上述方法拆分为若干个单词片段，并对每个片段进行哈希，即得到文档内容的特征集合，这样的一个特征就叫做一个shingle，进一步，如果单词片段长度为k，就叫做k-shingle。
另外，还有另一种基于词的shingle，这样的形式被证明在新闻报道近似重复检测中非常有效。对于新闻报道的重复检测，将shingle定义为一个停用词（the/for/a等）加上后续的两个词。
然后通过Jaccard相似度就可以计算两篇文章之间的相似度，这是原始的Shingling算法，k的选择依赖于文档的典型长度以及典型的字符表大小，如果k太小，很有可能会导致所有网页之间都有较高的Jaccard相似度。总之，k应该选择的足够大，以保证任意给定的shingle出现在任意文档中的概率较低。
有人提出了针对原始Shingling算法的优化算法，因为原始Shingling算法对于不同的网页，特征集合的长度也不同，而且往往长度都较大。优化后的Shingling算法不再采用一个哈希函数对所有的单词片段进行哈希，而是随机选择m种哈希函数，对所有的原始单词片段进行哈希，但是我们只保留每种哈希函数所有的结果里面，最小的那个，这样文档就能被转换为固定大小m的最小哈希签名。之后，我们就可以根据Jaccard相似度计算方法，计算最小哈希签名的相似度了。
I-Match算法
I-Match算法是先根据大规模语料进行统计，记录语料中的所有单词，然后去除掉一定比例IDF得分过高以及过低的单词，剩下的作为特征词典。
对于需要去重的网页，采用特征词典过滤，保留在特征词典中出现过的单词，然后对所有单词进行一次哈希，得到一个唯一的数值，通过比较该数值是否相同，来判定两个网页是否近似重复。
我们还可以进一步优化，就是不再只使用一个特征词典，而是使用多个大致相同而又有微小差异的词典，来避免I-Match算法对于增删单词过于敏感的问题。
SimHash算法
SimHash算法可能是目前最优秀的去重算法之一，是局部敏感哈希的一种。
第一步是文档指纹计算，首先从文档内容中抽取一批能表征文档的特征，然后将这些特征映射为固定长度的二进制表示，再利用权值改写特征的二进制向量，形成一个实数向量，之后将所有特征对应的实数向量相加，最后再将实数向量转换为二进制向量，方式为，如果对应位置数字大于0，则设置为1，小于等于0，则设置为0：
比如举个例子（本例不涉及权重）：
- 选择simhash的位数，请综合考虑存储成本以及数据集的大小，比如说32位
- 将simhash的各位初始化为0
- 提取原始文本中的特征，一般采用各种分词的方式。比如对于"the cat sat on the mat"，采用两两分词的方式得到如下结果：{"th", "he", "e ", " c", "ca", "at", "t ", " s", "sa", " o", "on", "n ", " t", " m", "ma"}
- 使用传统的32位hash函数计算各个word的hashcode，比如："th".hash = -502157718
，"he".hash = -369049682，…… - 对各word的hashcode的每一位，如果该位为1，则simhash相应位的值加1；否则减1
- 对最后得到的32位的simhash，如果该位大于1，则设为1；否则设为0
第二步是相似文档查找，SimHash的基本思想是这样的：将索引网页根据文档指纹进行分类，新网页只在部分分组内进行匹配，以减少新文档和索引网页的比较次数。
