局部敏感哈希、SimHash、MinHash

局部敏感哈希是为了解决一个核心问题：在海量数据中快速找到相似或近似的项目，避免进行代价高昂的“两两比较”。

想象一下，你有几百万张图片、几百万篇文档，或者几亿个用户的行为记录。你想找出相似的图片、相似的文档，或者兴趣相似的用户。如果每对数据都去精确计算它们的相似度（比如余弦相似度、Jaccard相似系数），那计算量是天文数字。这就是 LSH 这类技术大展身手的地方。

1. LSH（局部敏感哈希）：核心思想

• “局部敏感”是什么意思？ 指的是哈希函数对输入数据的局部变化（相似性）敏感。
• 与传统哈希的区别：
  • 传统哈希（如MD5, SHA-1）： 核心目标是均匀分布和抗碰撞。输入数据哪怕只有一丁点不同（比如改了一个字符），哈希值就会变得天差地别。这是为了安全性和唯一性。
  • LSH： 核心目标是保持相似性。如果两个输入数据很相似，那么经过LSH哈希后，它们有很高的概率得到相同或非常接近的哈希值（比如在同一个“桶”里）。反之，如果两个输入数据很不相似，那么它们有很高的概率得到完全不同的哈希值（在不同的“桶”里）。
• 核心机制：
  • 设计一组特殊的哈希函数（LSH Family）。
  • 对每个数据点应用这些哈希函数，得到一个哈希签名（通常是一个由多个哈希值组成的短向量或一串比特）或者直接映射到桶ID。
  • 关键点： 相似的数据点有很大的概率会被映射到相同的桶或者哈希签名非常接近。
• 如何加速搜索？
  • 建立索引： 把所有数据点根据它们的LSH哈希值（或桶ID）放入不同的“桶”中。
  • 查询： 当你要找一个查询点 q 的相似点时：
    1. 计算 q 的LSH哈希值（或桶ID）。
    2. 只去 q 所在的那个（或那几个）桶里找候选点。
    3. 对这些少量的候选点进行精确的相似度计算（如果需要非常精确的结果）。
  • 巨大优势： 避免了与所有数据点进行精确比较！只需要比较桶里的少量候选点。
• LSH家族： LSH不是一个具体的算法，而是一类算法的框架。针对不同的相似度度量方式（如Jaccard相似度、余弦相似度、欧氏距离等），需要设计不同的LSH函数族。
• 核心目标： 用概率和近似换取速度和可扩展性。它可能漏掉一些相似点（假阴性），也可能放进一些不太相似的点（假阳性），但能极大提高效率。

简单比喻：
想象一个巨大的图书馆，书按照主题相似度（而不是精确的字母顺序）自动归类到书架上。如果你想找和《哈利波特》相似的书：

1. LSH 就像图书馆的归类系统，它会自动把《哈利波特》放到一个标记为“青少年奇幻魔法冒险”的书架上。
2. 你只需要去那个书架上找，而不用翻遍整个图书馆。
3. 这个书架上的书（候选集）很可能就是你要找的相似书。虽然可能漏掉一两本在别的奇幻架上的好书（假阴性），也可能混进来一两本不那么像的冒险书（假阳性），但大大缩小了搜索范围。

2. MinHash：针对集合相似度（Jaccard相似度）的LSH

• 解决什么问题？ 快速估计两个集合的 Jaccard相似度。
  • Jaccard相似度：。衡量两个集合的交集大小占并集大小的比例。范围在 [0, 1] 之间。常用于文档（词袋模型）、用户行为（）等。
• 核心思想： MinHash 是 LSH 框架下的一种具体实现，专门为 Jaccard 相似度设计的哈希函数。
• MinHash值（签名）计算：
  1. 准备： 假设全集包含所有可能出现的元素（如所有单词）。
  2. 选择哈希函数： 选择一个能将全集元素均匀映射到数字（比如0到某个大数）的哈希函数 h(e)。
  3. 计算单个MinHash值： 对于一个集合 S，计算它的MinHash值 m(S) 就是：**m(S) = min{ h(e) for e in S }。也就是用哈希函数 h 映射集合 S 中所有元素，然后取映射结果中最小的那个值**作为 S 的MinHash签名。
• 神奇的性质： P(m(A) = m(B)) = Jaccard(A, B)
  • 两个集合 A 和 B 的MinHash值相等的概率，恰好等于它们的Jaccard相似度！
  • 如果 A 和 B 完全一样（J=1），那它们的MinHash必然相等。
  • 如果 A 和 B 完全不同（J=0），那它们的MinHash不可能相等。
  • 如果 A 和 B 部分相同（0<J<1），它们MinHash相等的概率就是J。
• 实际使用（签名矩阵）：
  • 单个MinHash值估计Jaccard相似度方差太大，不稳定。
  • 通常使用 k 个独立的哈希函数 h1, h2, ..., hk。
  • 对每个集合 S，计算 k 个MinHash值：[m1(S), m2(S), ..., mk(S)]。这个向量就是 S 的 MinHash签名。
  • 两个集合 A 和 B 的签名向量中，相同位置MinHash值相等的比例，就是 Jaccard(A, B) 的一个无偏估计。k 越大，估计越准，但计算和存储开销也越大。
• 如何用于LSH（分桶）：
  • 目标： 把 Jaccard 相似度大于某个阈值 s 的集合对找出来。
  • 方法（Band Partition）： 把 k 维的 MinHash 签名分成 b 个 band（段），每个 band 包含 r 行（k = b * r）。
  • 分桶规则： 对于每个集合的签名：
    • 对每个 band，把这个 band 里面的 r 个 MinHash 值拼接起来当作这个 band 的桶ID。
    • 同一个集合会被放入 b 个不同的桶（每个band一个桶）。
  • 碰撞（相似）条件： 如果两个集合 A 和 B 在至少一个 band 上，它们对应的 r 个值完全相等（即这个band的桶ID相同），那么它们就被认为是一个候选对。
  • 原理： 调整 b 和 r 可以控制召回率和精确率。r 越小（band越宽），越容易碰撞（召回高，精度可能低）；r 越大（band越窄），越难碰撞（召回低，精度高）。
• 应用场景： 文档去重（判断网页是否镜像/转载）、推荐系统（寻找有相似物品集合的用户）、基因序列分析（寻找有相似序列片段的基因）。

简单比喻：
假设每个顾客的购物车是一个集合（里面是商品ID）。MinHash 就像给每个顾客发一张“特征卡”：

1. 有 k 个考官（哈希函数），每个考官对购物车里的所有商品打分（哈希值）。
2. 每个考官只记录他看到的最低分（MinHash值）并写在顾客的特征卡对应位置上。
3. 比较两个顾客：看他们的特征卡上，有多少个考官记录的最低分是相同的。比例越高，说明他们购物车里的商品重合度（Jaccard相似度）越高。
4. LSH分桶：把特征卡撕成 b 条（band）。规定：只要两个顾客的某一条上的所有分数完全一样，就把他们当成“可能相似”的候选顾客，放到一起待查。

---

3. SimHash：针对高维特征向量（余弦相似度）的LSH

• 解决什么问题？ 快速估计高维特征向量之间的余弦相似度或海明距离关系。常用于文本相似度（Google用于网页去重）。
• 核心思想： SimHash 也是 LSH 框架下的一种具体实现。它把高维特征向量（如文档的词频/权重向量）降维、压缩成一个固定长度（如64位）的二进制指纹（Fingerprint）。关键是：原始向量越相似，生成的SimHash指纹之间的海明距离（Hamming Distance，二进制串不同比特位的数量）就越小。
• SimHash指纹计算步骤（以文本为例）：
  1. 特征提取： 将文档分词，提取特征（通常是词）及其权重（可以是词频、TF-IDF等）。得到特征-权重对 (feature_i, weight_i)。
  2. 传统哈希： 对每个特征 feature_i 用一个标准哈希函数（如MD5, MurmurHash）映射成一个 f 位的二进制串 H(feature_i)（例如64位）。
  3. 加权： 创建一个长度为 f 的向量 V（初始值全为0）。
     • 遍历 H(feature_i) 的每一位 j：
       • 如果 H(feature_i) 的第 j 位是 1，那么 V[j] += weight_i。
       • 如果 H(feature_i) 的第 j 位是 0，那么 V[j] -= weight_i。
     • 简单理解：每个特征根据其权重，对 f 个维度分别进行“投票”。1投正票，0投负票。
  4. 生成指纹： 遍历向量 V 的每一位 j：
     • 如果 V[j] > 0，则最终SimHash指纹的第 j 位设为 1。
     • 如果 V[j] < 0，则最终SimHash指纹的第 j 位设为 0。
     • (如果 V[j] == 0，可以随机设为0或1，但概率很小)
  5. 输出： 得到一个 f 位的二进制串（如 0101...1101），这就是文档的SimHash指纹。
• 关键性质： 两个原始向量的余弦相似度越高，它们对应的SimHash指纹之间的海明距离就越小。存在理论上的概率保证。
• 如何用于LSH（分桶）：
  • 目标： 把海明距离小于某个阈值 d 的指纹对（即原始向量相似度高）找出来。
  • 方法： 有多种分桶策略，一种常见且高效的是多表索引：
    • 投影（Projection）： 将 f 位的指纹分成 k 个不相交的片段（称为“关键码”或“索引码”）。例如，一个64位指纹分成4个16位的片段。
    • 分桶： 对每个片段位置（如第1个16位、第2个16位…），建立一个独立的哈希表。
    • 存储： 对于一个指纹 F：
      • 将其 k 个片段分别作为 k 个哈希表的键（Key）。
      • 将指向原始数据（或ID）的指针放入这 k 个哈希表中对应键的桶里。（同一个数据点会被放入 k 个桶）
    • 查询： 对于查询指纹 Q：
      1. 同样将其分成 k 个片段。
      2. 分别用这 k 个片段作为键，去对应的 k 个哈希表里查找。
      3. 把 k 个桶里找到的所有数据点的指针合并起来，作为候选集。
    • 原理： 如果两个指纹的海明距离很小（很相似），那么它们有很大概率在至少一个片段上完全相同（因为海明距离小意味着大部分比特相同，而片段是随机划分的，相同的部分很可能落在同一个片段内）。因此，相似的指纹有很大概率在至少一个桶里发生碰撞。
  • 调参： k（片段数/表数）和片段长度影响召回率和精度。k 越大，召回率越高（因为碰撞机会多），但桶的数量也越多，内存开销和候选集可能变大。片段长度越短，碰撞越容易（召回高精度低）；越长，碰撞越难（召回低精度高）。
• 应用场景： 大规模网页去重（检测内容相似的网页）、论文查重、新闻聚合（聚合报道同一事件的新闻）。Google 爬虫使用该算法来查找接近重复的页面。

简单比喻：
想象给每篇文档拍一个“模糊照片”（SimHash指纹）：

1. 文档里的每个词（特征）根据它的重要性（权重）投出一张模糊的选票（加权哈希），这张选票上画满了 f 个小格子（比特位），有些格子标+（1），有些标-（0）。
2. 把所有词的选票叠在一起。对于每个小格子：
   • 如果总的“+”票多于“-”票，照片的这个格子涂黑（1）。
   • 如果总的“-”票多于“+”票，照片的这个格子留白（0）。
3. 最终得到一张黑白格子组成的照片（二进制指纹）。内容相似的文章，拍出来的照片（指纹）看起来也相似（海明距离小）。
4. LSH分桶：把这张照片切成 k 个条带（片段）。规定：只要两篇文章的照片有任意一个条带完全一样，就把它们当成“可能相似”的候选文章，放到一起待查。

总结与比较

特性	LSH (框架)	MinHash (具体LSH实现)	SimHash (具体LSH实现)
核心目标	快速近似近邻搜索	快速估计集合的Jaccard相似度	快速估计高维向量的余弦相似度
数据表示	取决于具体实现	集合 (元素)	高维特征向量 (特征+权重)
相似度度量	取决于具体实现	Jaccard相似系数()	余弦相似度 / 海明距离
输出	桶ID / 哈希签名 (用于分桶)	MinHash签名 (整数向量)	SimHash指纹 (固定长度二进制串)
关键性质	相似点高概率同桶/签名接近	P(m(A)=m(B)) = Jaccard(A,B)	原始向量相似度高 => 指纹海明距离小
主要应用	海量数据近邻搜索、去重、聚类	文档去重、推荐(用户-物品集合)、基因	网页/文档去重、查重、新闻聚合
分桶方式	取决于具体实现	Band Partition	多表索引 (按片段分桶)
优势	框架通用，大幅降低比较次数	理论漂亮，直接估计Jaccard	指纹紧凑，海明距离计算快
权衡	概率性(假阴/假阳)，需调参	签名较长，存储开销可能大	对特征权重敏感

核心思想再强调：

1. LSH 是指导思想： 设计哈希函数，让相似的东西有高概率“撞”到一起（得到相同/相近的哈希值或桶ID），从而可以只在小范围内进行精确比较。
2. MinHash 是 LSH 的“打集合相似度”专家： 专门解决“这两个集合（比如购物车、词袋）有多像？”的问题，用签名相等比例估计Jaccard相似度。
3. SimHash 是 LSH 的“打高维向量相似度”专家： 专门解决“这两个高维向量（比如TF-IDF向量）有多像？”的问题，把向量压缩成指纹，用指纹的海明距离反映原始余弦相似度。

通过利用 LSH 的思想，以及 MinHash 或 SimHash 这样的具体工具，我们就能在浩瀚的数据海洋中，高效地捞出那些“相似”的鱼儿。万篇文档，或者几亿个用户的行为记录。你想找出相似的图片、相似的文档，或者兴趣相似的用户。如果每对数据都去精确计算它们的相似度（比如余弦相似度、Jaccard相似系数），那计算量是天文数字。这就是 LSH 这类技术大展身手的地方。

rust开源实现：https://github.com/serega/gaoya

• https://en.wikipedia.org/wiki/Locality-sensitive_hashing
• https://en.wikipedia.org/wiki/MinHash
• https://en.wikipedia.org/wiki/SimHash