最近在做一些文件相似度、内容相似度相关的算法，调研一些论文，一些实用的算法放到库里 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%），因为插入和删除会让这部分完全不同
方案1
- 设定 “锚” anchors，然后找到这个锚后面的 50 个字符，
- 如果锚没出现，或者出现在修改过的地方，会有问题
- 因此需要设定多个锚，这样可以用多模式匹配去寻找
方案2：计算所有可能长度的子串的指纹
- 不能简单的把文本分成长度为 50 的组，因为如果把开头位置偏移 1 字节，所有指纹都会变化
- 我们需要考虑所有的 50-byte 的子串
如何计算？设计了这样一个迭代式：
如果一个 “50-byte 子串” 表示为 “$t_1t_2…t_n$” hash值就是：$F_1=(t_1\cdot p^{49} +t_2\cdot p^{48}+…+t_{50}) \mod M$
偏移1个字节的 hash 值不需要再遍历 50 次，而是用这个来迭代：
$F_2=(p\cdot F_1 + t_{51} - t1\cdot p^{49}) \mod M$
一般取 p 为素数，$M = 2^{30}$
建议方案2，因为锚需要有通用性，但实际上只能随机选择。对《华尔街日报》好用的锚，可能不适用于医学文章。一种语言的锚也不适用于另一种语言
方案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）系统使用尽可能少的机器
论文提出两个研究贡献
- finger-printing 方案：simhash 。并用实验证明 8Billion 大小的网页库，64-bit simhash fingerprints 和 k =3 是合适的。
- 快速检索：f-bit finger-printing 的库中，与 某个 fingerprint 最多 k bit 差别的是哪些，k 是个小整数
simhash 是一种 降维技术（a dimensionality reduction technique），它把高维向量映射成 fingerprint，在网页这样应用：
- 把网页转化为一组特征，每个特征对应权重。计算特征用到 standard IR techniques，例如 tokenization，case folding, stop-word removal，stemming and phrase detection
- 计算。给定一组特征和对应的权重，计算 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位留出几位记录文件大小
- 是否可以提前断言某些文档不可能有相似文档
- 把文档分为不同的类别。
- 自动检索网页中的广告和时间戳，移除它们。
