simhash如何检查重复文本？
大规模网页的近似重复检查
主要翻译自WWW07的检测网页抓取的近似重复。
WWW上有大量内容相似的网页。对于搜索引擎来说，去除相似网页可以提高检索效率，减少存储开销。
爬虫在抓取网页时，必须能够快速发现海量文本集中是否存在重复页面。
该论文有两个主要贡献:
1.这表明simhash可以用于海量文本的查重。
2.提出了一种实际应用中可行的算法。
Simhash算法
从文本中提取内容后，经过基本的预处理，如去除停用词、降根，甚至分块，最终可以得到一个向量。
对每个$ term进行哈希算法转换，得到长度为f位的哈希码，每个位上的1-0的值被转换成正负权值。例如，当f1的位是1时，权重被设置为+weight，当FK的位是0时，权重被设置为-weight。
将口语文本中所有的$ term转换后的权重向量按照F的对应比特进行累加，最终得到一个F比特的权重数组。如果该位为正，则设置为1，如果该位为负，则设置为0，然后将文本转换为新的F位1-0数组，这是一个新的哈希码。
Simhash有两个“冲突的属性”:
1.这是一种哈希方法
2.相似的文本有相似的哈希值。如果两个文本的simhash越接近，即海明距离越小，则文本越相似。
因此，如何通过海量文本中查重的任务转换位，快速确定海量simhash中是否存在汉明距离小的指纹。
即，在n个f位指纹中，查询汉明距离小于k的指纹。
在文章的实验中(见结尾)，simhash使用了64位哈希函数。海明距离=3在80亿网页的规模下刚刚好。
因此，任务的f位= 64，k = 3，n = 8 * 10 11。
任务明确，先看两个非常直观的方法:
1.枚举所有汉明距离小于3的simhash指纹，在80亿个排序指纹中查询每个指纹。
(这个方法需要进行单词C (64，3) = 465438+C(64)的simhash指纹，然后对每个单词进行查询。)
2.所有接近的指纹都排序在一起，最多是41664，需要巨大的空间。
提出的方法介于两者之间，是空间和时间的合理折衷。
假设我们有一组排序的2d、f位指纹。看每个指纹的高d位。高位和低位具有以下性质:虽然有许多2d位组合，但在高D位中只有少数重复。
现在找一个接近d的数d’，因为整个表都是有序的，所以一个搜索就能找到和目标指纹f有同样高d’位的指纹集合f’，因为d’和d很接近，所以找到的集合f’不会很大。
最后，在集合F '中找到F和F之间具有汉明距离k的指纹是非常快速的。
大意:首先缩小检索集，然后在小集中搜索f-d '位置的汉明距离。
根据示例，80亿页中有2 ^ 34页，因此理论上，34位可以代表80亿个唯一指纹。
我们假设前34位代表80亿个指纹，指纹的前30位相同，那么后4位也可以代表24个指纹，只需要比较这16个指纹的汉明距离是否小于3。
假设:您可以对任意34位中的30位执行此操作。
因此，在一次完整的搜索中，前q位必须完全匹配(假设这些指纹是q序的，可以使用二分搜索法，如果指纹数量非常大且分布均匀，甚至可以使用插值搜索)，后续2d-q指纹剩余的64-q位需要进行比较，汉明距离小于3。
所以问题就变成了如何截64位q。
把64位分成几份，比如ABCD 4份，每份16位。
假设这些指纹已经按照A部分排序，我们首先按照A的16位精确匹配到一个区间，检查这个区间的BCD位后汉明距离是否小于3。
同样的假设下，其次，我们根据b的16位精确匹配到另一个区间，这个区间内的所有指纹都需要比较ACD位上的汉明距离是否小于3。
同样的，还有C和d。
所以这里我们需要将所有指纹T复制4份，T1 T2 T3 T4，T1按A排序，T2按B排序……4份可以并行查询，最后合并结果。这样，即使在最坏的情况下，三位落在三个区域，ABC，ACD，BCD，ABD…也不会遗漏。
精确匹配的只有16位数，需要一个一个比对的指纹数量依然庞大，可能达到2d-16，我们也可以精确匹配更多。
比如把64位分成ABCD的4份，每份16位。在BCD的48位上，我们分成4部分，WXZY，每部分12位。汉明距离的3位可以分散在任意三个部分中，因此A和WXZY中的任何一个可以组合成精确的28位…剩余的3部分用于检查汉明距离。同理，B，C，D也可以。那么T需要复制16次，ABCD和WXYZ的组合匹配准确。每次精确匹配后，需要逐一比对的数量减少到2d-28。不同的组合是时间和空间的权衡。
最坏的情况是其中三个可能有1比特，汉明距离之差是1。
该算法描述如下:
1)首先将原表T复制成Tt份数:T1，T2、...TT。
2)每个Ti与一个pi和一个πi相关联，其中pi是一个整数，πi是一个置换函数，它负责将pi位变为高位。
3)将排列函数πi应用于相应的Ti表，然后对Ti进行排序。
4)然后，对每个Ti、待匹配的指纹f和汉明距离k执行以下操作:
a)然后使用F’的高pi位来搜索并找出Ti中的同一组高pi位。
b)比较检索到的集合中的f-pi位，找出汉明距离小于或等于k的指纹。5)最后合并所有Ti中的检索结果。