基于局部敏感哈希（Locality-Sensitive Hashing, LSH）的文本相似搜索算法详解
字数 3401 2025-12-17 08:56:03

基于局部敏感哈希（Locality-Sensitive Hashing, LSH）的文本相似搜索算法详解

题目描述

在自然语言处理中，我们经常需要快速地从海量文本集合中找出与目标文本相似的文档，例如新闻去重、推荐系统或抄袭检测。传统的两两比较（如计算余弦相似度）时间复杂度为O(N²)，对于大规模数据集是不可行的。基于局部敏感哈希（LSH）的文本相似搜索算法，通过将高维文本向量（如TF-IDF或词向量）映射到低维哈希签名，并利用哈希碰撞的概率性质，使得相似的文本有高概率落入相同的哈希桶中，从而实现亚线性时间的近似相似搜索。

解题过程

第一步：问题建模与核心思想

  1. 目标：给定一个海量文档集合 D（例如100万篇新闻），对于任意查询文档 q，快速找出 D 中所有与 q 相似度超过阈值 t 的文档。
  2. 挑战：暴力比较需要为 q 计算它与 D 中每个文档的相似度（如余弦相似度），成本过高。
  3. 核心思想：LSH的核心是设计一组哈希函数，使得相似的文本以高概率哈希到相同的桶（bucket）中，不相似的文本以低概率哈希到相同的桶中。这样，我们只需在 q 落入的少数几个桶内进行精确比较，从而大幅减少计算量。

第二步：文本表示与相似度度量

  1. 文本向量化：

    • 首先，将每个文档表示为高维向量。常用方法有：
      • 词袋模型 + TF-IDF：每个维度对应一个词，值为该词的TF-IDF权重。
      • 词向量平均：使用预训练词向量（如Word2Vec、GloVe）对文档中的词向量取平均或加权平均。
      • 句子/文档嵌入：直接使用BERT等模型获得文档的稠密向量。
    • 假设每个文档被表示为 d 维向量，例如 d=10000（TF-IDF）或 d=300（词向量平均）。

  2. 相似度度量：

    • 对于向量表示，通常使用余弦相似度来衡量文档相似性：sim(u, v) = (u·v) / (||u|| ||v||)。
    • 我们的目标就是快速找到所有与 q 余弦相似度大于阈值 t 的文档。

第三步：局部敏感哈希（LSH）的基本原理

  1. LSH函数族：

    • LSH依赖于一个哈希函数族 H，满足：对于任意两个向量 u 和 v，有
      • 如果 sim(u, v) 很高，则 Pr[h(u) = h(v)] 很高。
      • 如果 sim(u, v) 很低，则 Pr[h(u) = h(v)] 很低。
    • 对于余弦相似度，一个经典的LSH函数族是随机投影（Random Projection），也称为SimHash。

  2. 随机投影（SimHash）的工作原理：

    • 生成一个随机向量 r，其每个分量从标准正态分布 N(0,1) 中独立采样。
    • 定义哈希函数 h_r(u) = sign(r·u)，其中 sign 是符号函数：
      • 如果 r·u ≥ 0，则 h_r(u) = 1。
      • 如果 r·u < 0，则 h_r(u) = 0。
    • 关键性质：两个向量 u 和 v 的哈希值相同的概率为： 
      Pr[h_r(u) = h_r(v)] = 1 - (θ / π)
其中 θ = arccos(sim(u, v))，即两者之间的夹角。
      这意味着，夹角越小（相似度越高），哈希碰撞的概率越大。

第四步：从单个哈希函数到哈希签名

  1. 单个哈希函数的问题：

    • 仅使用一个随机向量 r，碰撞概率随相似度线性变化，但无法提供足够的选择性（例如，相似度为0.8和0.3的碰撞概率差异不够大）。
    • 我们需要一种方式，使得高相似文档几乎肯定碰撞，低相似文档几乎肯定不碰撞。

  2. 构造哈希签名（Signature）：

    • 我们生成 k 个随机向量 r1, r2, ..., rk，每个对应一个独立的哈希函数。
    • 对于文档向量 u，计算它的 k 位哈希签名 s(u) = [h_{r1}(u), h_{r2}(u), ..., h_{rk}(u)]。
    • 这个签名可以看作一个长度为 k 的二进制串。

  3. 签名相似度与原始相似度的关系：

    • 两个文档签名中，对应位相同的比例（即签名间的汉明距离）是原始余弦相似度的无偏估计。
    • 具体地，Pr[s_i(u) = s_i(v)] = 1 - (θ/π)，所以签名中相同位的期望比例为 1 - (θ/π)。
    • 因此，我们可以通过比较签名来快速估计文档相似度。

第五步：哈希桶（Bucket）构建与搜索

  1. 直接使用签名的局限性：

    • 即使使用 k 位签名，如果 k 很大（例如1000位），两个文档签名完全相同的概率仍然很低，除非它们几乎完全相同。
    • 我们需要进一步“放大”相似与不相似文档之间的碰撞概率差异。

  2. 引入波段（Banding）技术：

    • 将 k 位的签名分成 b 个波段（band），每个波段包含 r 位（k = b * r）。
    • 对于每个波段 i，我们使用一个更高级的哈希函数（如常规字符串哈希）将整个波段映射到一个哈希桶。
    • 这样，每个文档在 b 个哈希表中各有 b 个桶位置。

  3. 索引构建：

    • 预处理阶段：对文档集合 D 中的每个文档，计算其 k 位 SimHash 签名，应用波段技术，将其插入 b 个哈希表中对应的桶。
    • 存储时，只需存储文档ID（或指针），而不是完整向量。

  4. 查询过程：

    • 对于查询文档 q，同样计算其 k 位签名和 b 个波段哈希值。
    • 对于每个波段 i，取出该波段哈希值对应桶中的所有候选文档。
    • 合并所有波段的候选文档，去除重复。
    • 最后，对候选文档子集（远小于N）进行精确的相似度计算（如计算余弦相似度），返回超过阈值 t 的文档。

第六步：参数选择与概率分析

  1. 相似度阈值 t 与参数 (b, r) 的关系：

    • 假设我们希望找到相似度 > t 的文档。
    • 对于两个相似度为 s 的文档：
      • 在一个波段（r位）内，签名完全相同的概率为 p = (1 - arccos(s)/π)^r。
      • 在 b 个波段中，至少有一个波段碰撞的概率为 P(s) = 1 - (1 - p)^b。
    • LSH的S曲线效应：通过调整 (b, r)，我们可以使 P(s) 在 s=t 附近急剧变化，即：
      • 当 s > t 时，P(s) 接近1（高召回率）。
      • 当 s < t 时，P(s) 接近0（低误报率）。

  2. 示例计算：

    • 设定阈值 t=0.8（余弦相似度）。
    • 选择 k=1000，b=50，r=20。
    • 对于 s=0.85 的文档对：
      • p ≈ (1 - arccos(0.85)/π)^20 ≈ (1 - 0.554/π)^20 ≈ 0.327
      • P ≈ 1 - (1-0.327)^50 ≈ 0.999，几乎肯定被检索到。
    • 对于 s=0.3 的文档对：
      • p ≈ (1 - arccos(0.3)/π)^20 ≈ (1 - 1.266/π)^20 ≈ 0.00034
      • P ≈ 1 - (1-0.00034)^50 ≈ 0.017，误报率很低。

第七步：算法总结与优化

  1. 算法步骤总结：

    • 离线索引构建：
      1. 将文档集 D 中每个文档表示为向量。
      2. 为每个向量生成 k 位 SimHash 签名。
      3. 将签名分成 b 个波段，用每个波段在 b 个哈希表中索引文档ID。
    • 在线查询：
      1. 计算查询 q 的向量和 SimHash 签名。
      2. 对每个波段，查找对应哈希桶，收集候选文档ID。
      3. 合并候选集，去重。
      4. 对候选文档计算精确相似度，过滤并返回结果。

  2. 优化与变体：

    • 多哈希表（L个哈希函数组）：为了进一步提高召回率，可以独立构建 L 套哈希表（每组使用不同的随机向量集）。查询时合并 L 套哈希表的候选集。
    • 动态调整阈值：通过调整 (b, r) 或 L，可以在召回率与计算效率之间取得平衡。
    • 适用于其他相似度度量：LSH 有多种函数族，例如对于 Jaccard 相似度可以使用 MinHash，对于欧氏距离可以使用 p-stable LSH。

总结

基于局部敏感哈希（LSH）的文本相似搜索算法，通过巧妙的概率哈希将高维相似搜索问题转化为低维哈希碰撞问题，利用波段技术放大相似与不相似文档的碰撞概率差异，从而实现了海量文本集合中高效的近似相似搜索。其核心是在可接受的小误差（漏报或误报）下，将时间复杂度从 O(N) 降至亚线性，是大规模文本去重、检索和聚类的关键技术之一。

基于局部敏感哈希（Locality-Sensitive Hashing, LSH）的文本相似搜索算法详解 题目描述 在自然语言处理中，我们经常需要快速地从海量文本集合中找出与目标文本相似的文档，例如新闻去重、推荐系统或抄袭检测。传统的两两比较（如计算余弦相似度）时间复杂度为O(N²)，对于大规模数据集是不可行的。基于 局部敏感哈希（LSH） 的文本相似搜索算法，通过将高维文本向量（如TF-IDF或词向量）映射到低维哈希签名，并利用哈希碰撞的概率性质，使得相似的文本有高概率落入相同的哈希桶中，从而实现亚线性时间的近似相似搜索。 解题过程 第一步：问题建模与核心思想 目标 ：给定一个海量文档集合 D（例如100万篇新闻），对于任意查询文档 q，快速找出 D 中所有与 q 相似度超过阈值 t 的文档。 挑战 ：暴力比较需要为 q 计算它与 D 中每个文档的相似度（如余弦相似度），成本过高。 核心思想 ：LSH的核心是设计一组哈希函数，使得 相似的文本以高概率哈希到相同的桶（bucket）中，不相似的文本以低概率哈希到相同的桶中 。这样，我们只需在 q 落入的少数几个桶内进行精确比较，从而大幅减少计算量。 第二步：文本表示与相似度度量 文本向量化 ： 首先，将每个文档表示为高维向量。常用方法有： 词袋模型 + TF-IDF ：每个维度对应一个词，值为该词的TF-IDF权重。 词向量平均 ：使用预训练词向量（如Word2Vec、GloVe）对文档中的词向量取平均或加权平均。 句子/文档嵌入 ：直接使用BERT等模型获得文档的稠密向量。 假设每个文档被表示为 d 维向量，例如 d=10000 （TF-IDF）或 d=300 （词向量平均）。 相似度度量 ： 对于向量表示，通常使用 余弦相似度 来衡量文档相似性： sim(u, v) = (u·v) / (||u|| ||v||) 。 我们的目标就是快速找到所有与 q 余弦相似度大于阈值 t 的文档。 第三步：局部敏感哈希（LSH）的基本原理 LSH函数族 ： LSH依赖于一个哈希函数族 H ，满足：对于任意两个向量 u 和 v ，有 如果 sim(u, v) 很高，则 Pr[h(u) = h(v)] 很高。 如果 sim(u, v) 很低，则 Pr[h(u) = h(v)] 很低。 对于余弦相似度，一个经典的LSH函数族是 随机投影（Random Projection） ，也称为 SimHash 。 随机投影（SimHash）的工作原理 ： 生成一个随机向量 r ，其每个分量从标准正态分布 N(0,1) 中独立采样。 定义哈希函数 h_r(u) = sign(r·u) ，其中 sign 是符号函数： 如果 r·u ≥ 0 ，则 h_r(u) = 1 。 如果 r·u < 0 ，则 h_r(u) = 0 。 关键性质 ：两个向量 u 和 v 的哈希值相同的概率为： 这意味着，夹角越小（相似度越高），哈希碰撞的概率越大。 第四步：从单个哈希函数到哈希签名 单个哈希函数的问题 ： 仅使用一个随机向量 r ，碰撞概率随相似度线性变化，但无法提供足够的选择性（例如，相似度为0.8和0.3的碰撞概率差异不够大）。 我们需要一种方式，使得高相似文档几乎肯定碰撞，低相似文档几乎肯定不碰撞。 构造哈希签名（Signature） ： 我们生成 k 个随机向量 r1, r2, ..., rk ，每个对应一个独立的哈希函数。 对于文档向量 u ，计算它的 k 位哈希签名 s(u) = [h_{r1}(u), h_{r2}(u), ..., h_{rk}(u)] 。 这个签名可以看作一个长度为 k 的二进制串。 签名相似度与原始相似度的关系 ： 两个文档签名中，对应位相同的比例（即签名间的汉明距离）是原始余弦相似度的无偏估计。 具体地， Pr[s_i(u) = s_i(v)] = 1 - (θ/π) ，所以签名中相同位的期望比例为 1 - (θ/π) 。 因此，我们可以通过比较签名来快速估计文档相似度。 第五步：哈希桶（Bucket）构建与搜索 直接使用签名的局限性 ： 即使使用 k 位签名，如果 k 很大（例如1000位），两个文档签名完全相同的概率仍然很低，除非它们几乎完全相同。 我们需要进一步“放大”相似与不相似文档之间的碰撞概率差异。 引入波段（Banding）技术 ： 将 k 位的签名分成 b 个波段（band），每个波段包含 r 位（ k = b * r ）。 对于每个波段 i ，我们使用一个更高级的哈希函数（如常规字符串哈希）将整个波段映射到一个哈希桶。 这样，每个文档在 b 个哈希表中各有 b 个桶位置。 索引构建 ： 预处理阶段：对文档集合 D 中的每个文档，计算其 k 位 SimHash 签名，应用波段技术，将其插入 b 个哈希表中对应的桶。 存储时，只需存储文档ID（或指针），而不是完整向量。 查询过程 ： 对于查询文档 q ，同样计算其 k 位签名和 b 个波段哈希值。 对于每个波段 i ，取出该波段哈希值对应桶中的所有候选文档。 合并所有波段的候选文档，去除重复。 最后，对候选文档子集（远小于N）进行精确的相似度计算（如计算余弦相似度），返回超过阈值 t 的文档。 第六步：参数选择与概率分析 相似度阈值 t 与参数 (b, r) 的关系 ： 假设我们希望找到相似度 > t 的文档。 对于两个相似度为 s 的文档： 在一个波段（r位）内，签名完全相同的概率为 p = (1 - arccos(s)/π)^r 。 在 b 个波段中，至少有一个波段碰撞的概率为 P(s) = 1 - (1 - p)^b 。 LSH的S曲线效应 ：通过调整 (b, r) ，我们可以使 P(s) 在 s=t 附近急剧变化，即： 当 s > t 时， P(s) 接近1（高召回率）。 当 s < t 时， P(s) 接近0（低误报率）。 示例计算 ： 设定阈值 t=0.8 （余弦相似度）。 选择 k=1000 ， b=50 ， r=20 。 对于 s=0.85 的文档对： p ≈ (1 - arccos(0.85)/π)^20 ≈ (1 - 0.554/π)^20 ≈ 0.327 P ≈ 1 - (1-0.327)^50 ≈ 0.999 ，几乎肯定被检索到。 对于 s=0.3 的文档对： p ≈ (1 - arccos(0.3)/π)^20 ≈ (1 - 1.266/π)^20 ≈ 0.00034 P ≈ 1 - (1-0.00034)^50 ≈ 0.017 ，误报率很低。 第七步：算法总结与优化 算法步骤总结 ： 离线索引构建 ： 将文档集 D 中每个文档表示为向量。 为每个向量生成 k 位 SimHash 签名。 将签名分成 b 个波段，用每个波段在 b 个哈希表中索引文档ID。 在线查询 ： 计算查询 q 的向量和 SimHash 签名。 对每个波段，查找对应哈希桶，收集候选文档ID。 合并候选集，去重。 对候选文档计算精确相似度，过滤并返回结果。 优化与变体 ： 多哈希表（L个哈希函数组） ：为了进一步提高召回率，可以独立构建 L 套哈希表（每组使用不同的随机向量集）。查询时合并 L 套哈希表的候选集。 动态调整阈值 ：通过调整 (b, r) 或 L，可以在召回率与计算效率之间取得平衡。 适用于其他相似度度量 ：LSH 有多种函数族，例如对于 Jaccard 相似度可以使用 MinHash，对于欧氏距离可以使用 p-stable LSH。 总结 基于局部敏感哈希（LSH）的文本相似搜索算法，通过巧妙的概率哈希将高维相似搜索问题转化为低维哈希碰撞问题，利用波段技术放大相似与不相似文档的碰撞概率差异，从而实现了海量文本集合中高效的近似相似搜索。其核心是在可接受的小误差（漏报或误报）下，将时间复杂度从 O(N) 降至亚线性，是大规模文本去重、检索和聚类的关键技术之一。