【论文学习】Hash 类算法

最近在做一些文件相似度、内容相似度相关的算法，调研一些论文，一些实用的算法放到库里 https://github.com/guofei9987/pyLSHash。

Finding Similar Files in a Large File System

https://www.cs.princeton.edu/courses/archive/spr05/cos598E/bib/manber94finding.pdf 1993

目的：大量文件中寻找相似的那些。

• 这里引入的是指纹类算法，使运行时间变成线性的。
• 文本相似的概念在这里定义为词本身的相似。近义词不视为相似
• fingerprints 和 checksum 只适用于精确相等的测试。我们的目标是检测相似性
• 但我们又不能使用固定部分（例如文件中间的10%），因为插入和删除会让这部分完全不同

• 设定 “锚” anchors，然后找到这个锚后面的 50 个字符，
• 如果锚没出现，或者出现在修改过的地方，会有问题
• 因此需要设定多个锚，这样可以用多模式匹配去寻找

方案2：计算所有可能长度的子串的指纹

• 不能简单的把文本分成长度为 50 的组，因为如果把开头位置偏移 1 字节，所有指纹都会变化
• 我们需要考虑所有的 50-byte 的子串

如何计算？设计了这样一个迭代式：

如果一个 “50-byte 子串” 表示为 “t1t2…tnt_1t_2…t_nt1​t2​…tn​” hash值就是：F1=(t1⋅p49+t2⋅p48+…+t50)mod  MF_1=(t_1\cdot p^{49} +t_2\cdot p^{48}+…+t_{50}) \mod MF1​=(t1​⋅p49+t2​⋅p48+…+t50​)modM

偏移1个字节的 hash 值不需要再遍历 50 次，而是用这个来迭代：
F2=(p⋅F1+t51−t1⋅p49)mod  MF_2=(p\cdot F_1 + t_{51} - t1\cdot p^{49}) \mod MF2​=(p⋅F1​+t51​−t1⋅p49)modM

一般取 p 为素数，M=230M = 2^{30}M=230

建议方案2，因为锚需要有通用性，但实际上只能随机选择。对《华尔街日报》好用的锚，可能不适用于医学文章。一种语言的锚也不适用于另一种语言

• 需要禁止指纹重叠，识别出指纹后，移动到末尾。例如50个空格得到了指纹，而文章中有70个连续空格，就不要再生成21个重复指纹了。

如何查询？

• 一个文档可以提取多个指纹，建立 Query 数据库（例如 HashMap 或树结构），把每种指纹和文章id对应起来
• 如此输出1个相似度百分比，这个数字可能大于1，因为计数可能重复

另外还可以记录整个文件的 checksum 和 大小，以作为辅助使用

总结，这个论文是做了这些事：

• 生成指纹。
• 把海量的指纹片段做成数据库
• 查询时用了一些统计方法，来判断相似度

Detecting Near-Duplicates for Web Crawling

http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/33026.pdf

这是 Google 在 2007 年提出来的海量文档去重方案。快速找到 Near-Duplicate 的文档可以提升搜索爬虫的质量。

完全相同的文档很容易识别，困难的事识别几乎一样的文档。例如主要内容相同，只是少部分不同（如广告、计数器、时间戳），如果能够有效识别，就可以xxx（提升效率、降低成本）。
这里面有很多挑战：1）规模问题，数十亿网页，数TB。2）快速标记重复，每天数十亿网页，要快速标记是否已经在库中了。3）系统使用尽可能少的机器

论文提出两个研究贡献

1. finger-printing 方案：simhash 。并用实验证明 8Billion 大小的网页库，64-bit simhash fingerprints 和 k =3 是合适的。
2. 快速检索：f-bit finger-printing 的库中，与 某个 fingerprint 最多 k bit 差别的是哪些，k 是个小整数

simhash 是一种 降维技术（a dimensionality reduction technique），它把高维向量映射成 fingerprint，在网页这样应用：

1. 把网页转化为一组特征，每个特征对应权重。计算特征用到 standard IR techniques，例如 tokenization，case folding, stop-word removal，stemming and phrase detection
2. 计算。给定一组特征和对应的权重，计算 f-bit 的fingerprint。
   • 维护一个 f-bit fingerprint vector，记为 V，初始化为全 0
   • 如果 i-th bit 位置的值为1，就增加 weight，否则减少 weight
   • 得到的 V，其符号就是最终的 fingerprint

Google 的文档数量为 8 Billion，综合考虑，hash长度为 64，k = 3 是最优的。这时候的准召都是 0.75

为了降低计算量，这样设计：

• 把 64 位 simhash 平均分为 4个 part
• 如果两个 simhash 相似（也就是 hamming 距离小于3），必然有一个 part 是完全相同的

• 适用于长文本去重，对短文本不合适，容易冲突生成相同simhash值

• 特征可以用 IDF 模型来做

• 文件大小也很重要。例如，一个简单的算法，如果两个文档的术语有 80%重合，并且大小相差 20% 之内。就往往可以视为相同。
  • 或许可以区分文件大小。或者64位留出几位记录文件大小
• 是否可以提前断言某些文档不可能有相似文档
• 把文档分为不同的类别。
• 自动检索网页中的广告和时间戳，移除它们。