LSH算法原理讲解：从文本相似到大规模候选检索

前置知识：什么是哈希（Hash）算法？

在深入 LSH 之前，我们需要先理解基础的哈希算法。

简单来说，哈希函数（Hash Function）就像是一个“数字指纹生成器”。它接收任意长度的数据（如一段文本、一篇文档），并将其映射为一个固定长度的较短字符串或数值（即哈希值或签名）。

传统哈希算法（如 MD5、SHA-256）的核心特征是：

唯一性与确定性：绝对相同的输入，一定会得到完全相同的哈希值。
雪崩效应：输入数据哪怕仅仅改变了一个标点符号，输出的哈希值也会变得面目全非、毫无规律。这在密码学中非常重要，能用来保证数据未被篡改。

然而，传统哈希的“雪崩效应”在相似度检索任务中反而成为了阻碍。如果我们想通过比对哈希值来判断两篇文章是否相似，传统哈希算法完全无能为力——因为两篇高度相似但不完全相同的文章，它们的哈希值是截然不同且没有任何关联的。

这也恰恰引出了本文的主角——LSH（局部敏感哈希）。它一反常态，特意设计出了一种**“让越相似的数据，越容易产生相同的哈希值（即越容易发生碰撞）”**的过滤机制。

算法背景：LSH解决了什么痛点？

在实际系统中，“相似检索/去重”的难点通常不在于“能否计算”，而在于计算代价是否可接受。当文档规模达到百万、千万级时，直接比较全部文档对几乎不可行。

LSH（Locality-Sensitive Hashing）的核心机制是：

使高相似对象以较高概率落入同一桶（进入候选集）
使低相似对象以较高概率在早期被过滤

因此，它特别适合“先粗筛、再精排”的检索流程。

常见应用领域

搜索与推荐：相似文章召回、相似商品召回、候选集构建。
数据清洗与去重：网页去重、日志去重、训练语料去重。
反作弊与内容安全：近重复内容识别、模板化刷屏检测。
大模型数据工程：预训练/微调语料去重，降低数据污染与过拟合风险。

示例文本集合

设文档集合：

D = \{d_1,d_2,d_3,d_4,d_5\}

$d_1=\text{“今天北京天气很好”}$
$d_2=\text{“今天北京天气真好”}$
$d_3=\text{“昨天上海天气很差”}$
$d_4=\text{“今天北京天气挺好”}$
$d_5=\text{“深度学习推荐系统”}$

直观上， $d_1$ 、 $d_2$ 和 $d_4$ 句式高度相似（仅一字之差），而 $d_3$ 、 $d_5$ 语义或结构上有显著差异。

Shingling（文本 → q-gram集合）

先将文本映射为字符 $q$ -gram 集合。这里取字符 3-gram。

文本	3-gram 集合
$d_1$	{今天北, 天北京, 北京天, 京天气, 天气很, 气很好}
$d_2$	{今天北, 天北京, 北京天, 京天气, 天气真, 气真好}
$d_3$	{昨天上, 天上海, 上海天, 海天气, 天气很, 气很差}
$d_4$	{今天北, 天北京, 北京天, 京天气, 天气挺, 气挺好}
$d_5$	{深度学, 度学习, 学习推, 习推荐, 推荐系, 荐系统}

随后可用 Jaccard 相似度刻画集合之间的相似性：

J(A,B)=\frac{|A\cap B|}{|A\cup B|}

小幅文本改动通常只影响局部 gram，因此 Jaccard 往往仍较高。

MinHash（集合 → 签名向量）

目的：不直接计算交并集，也能快速估计 Jaccard 相似度。

3.1 构造方式

设有 $k$ 个哈希函数 $h_1,\dots,h_k$ ，对集合 $S$ 定义：

m_{h_i}(S)=\min\{h_i(g):g\in S\},\quad i=1,\dots,k

于是签名向量为：

\text{sig}(S)=\big(m_{h_1}(S),m_{h_2}(S),\dots,m_{h_k}(S)\big)

3.2 为什么可行

对两个集合 $A,B$ ，MinHash 的核心定理是：

P(m_h(A)=m_h(B)) = J(A,B)

简要证明：哈希函数 $h$ 相当于对全集元素做了一次随机排列。考察两集合的并集 $A \cup B$ 中的所有元素：要使 $m_h(A) = m_h(B)$ ，意味着 $A \cup B$ 中经过哈希映射后值最小（即排在“最前面”）的那个元素，必须既属于 $A$ 也属于 $B$ ，也就是说必须属于交集 $A \cap B$ 。因为哈希是完全随机的， $A \cup B$ 中的每一个元素成为最小值的概率是完全相等的。所以这个最小元素正好属于交集 $A \cap B$ 的概率，就是交集元素个数占并集元素个数的比例，即 $\frac{|A \cap B|}{|A \cup B|} = J(A,B)$ 。

用 $k$ 个哈希后，可得无偏估计量：

\hat J(A,B)=\frac{1}{k}\sum_{i=1}^{k} I[m_i(A)=m_i(B)]

方差为：

\mathrm{Var}(\hat J)=\frac{J(1-J)}{k}

$k$ 越大，估计越稳定，但存储和计算成本也越高。

3.3 示例签名矩阵（ $k=6$ ）

文本	h1	h2	h3	h4	h5	h6
$d_1$	12	7	5	20	1	13
$d_2$	12	7	6	20	1	13
$d_3$	21	5	8	19	7	4
$d_4$	12	7	5	19	1	58
$d_5$	30	14	22	33	28	5

可以看出： $d_1$ 与 $d_4$ 在前三个哈希函数取值一致，而与 $d_2$ 在后三个哈希函数取值一致，这反映了它们较高的相似度。

LSH Banding（签名矩阵 → 候选对）

有了签名后，仍不想做全量比较，于是引入 Banding。

4.1 切分规则

将长度 $k$ 的签名切成 $b$ 个 band，每个 band 含 $r$ 行：

k=b\cdot r

例如： $k=6,b=2,r=3$ 。

Band 1: $(h_1,h_2,h_3)$
Band 2: $(h_4,h_5,h_6)$

4.2 候选判定

若两个文档在任一 band 完全相同，则在该 band 碰撞，成为候选对。

Band	桶	文档
1	B1-1	$d_1$ , $d_4$
1	B1-2	$d_2$
1	B1-3	$d_3$
1	B1-4	$d_5$
2	B2-1	$d_1$ , $d_2$
2	B2-3	$d_3$
2	B2-4	$d_4$
2	B2-5	$d_5$

在这里， $d_1,d_4$ 在 Band 1 碰撞、 $d_1,d_2$ 在 Band 2 碰撞，它们都会被成功召回送入下一阶段。

4.3 概率解释（S曲线）

若两篇文本的真实相似度为 $s$ ，则其被召回为候选的概率为：

P_{\text{cand}}(s)=1-(1-s^r)^b

这条曲线会在某一阈值附近快速上升，因此 LSH 能实现“高相似度优先召回、低相似度优先过滤”。

精确验证（候选对 → 最终结果）

对候选集合中的文档对再计算真实 Jaccard：

文本对	交集大小	并集大小	Jaccard
$d_1$ , $d_4$	4	8	0.5
$d_1$ , $d_2$	4	8	0.5

最终保留满足 $Jaccard \ge \tau$ 的文档对（ $\tau$ 为业务阈值）。

这里需要注意：精确验证负责“剔除误报（假阳性）”，而召回上限由前面的 LSH 候选阶段决定。

算法直观总结

Shingling：把文本变成可比较的集合表示。
MinHash：把集合压缩成固定长度签名，近似保留 Jaccard。
LSH Banding：用概率机制快速生成候选，避免全量比较。
精确验证：在候选上做高精度判定，得到最终相似对。

核心思想：用可控的概率近似换取数量级的效率提升，使海量文本相似检索在工程上可落地。