局部敏感哈希（LSH）详解：原理、算法、应用与实战

内容纲要

局部敏感哈希（Locality-Sensitive Hashing, LSH）是一种经典且高效的近似最近邻搜索（Approximate Nearest Neighbor, ANN）技术，尤其适用于处理高维空间中的相似度搜索问题。LSH 利用特定设计的哈希函数族，使得原始空间中相似的数据点在哈希空间中具有较高的碰撞概率，从而实现高效的向量索引与查找。

一、为什么需要 LSH？

在高维数据场景中（如图像特征向量、文本向量、音频向量等），传统的暴力搜索（Brute-Force）方法虽然精确，但时间复杂度高（O(Nd)，N为数据量，d为维度），不适合大规模数据。而 LSH 提供了一种“以空间换时间”的思路，在牺牲少量精度的前提下，实现了近似相似搜索，大大提升了检索效率。

二、LSH 的基本思想

LSH 的核心思想是：为每个数据点构造多个哈希函数，使得相似的数据点落入同一个哈希桶（Bucket）的概率高，不相似的概率低。

其设计遵循以下形式的概率不等式：

如果 $sim(p,q)\geqs1\RightarrowPr[h(p)=h(q)]\geqP1$
如果 $sim(p,q)\leqs2\RightarrowPr[h(p)=h(q)]\leqP2$

其中 $s1>s2s_1 > s_2, P1>P2P_1 > P_2$ 。sim 是定义的相似度度量（如余弦相似度、欧氏距离等），h 是 LSH 函数。

三、LSH 的类型与对应的相似度度量

相似度度量	哈希函数类型	常用方法
欧氏距离（L2）	p-stable 分布哈希	E2LSH（使用高斯分布）
余弦相似度	Sign Random Projection	SimHash（随机超平面）
Jaccard 相似度	MinHash	Minwise Independent Permutations
汉明距离	Bit Sampling	直接采样某些 bit 位

四、LSH 算法结构与流程

LSH 通常由以下几个步骤组成：

构建哈希函数族
设计或选择适合相似度度量的哈希函数集合，如随机投影、MinHash 等。
多组哈希表构建（AND-OR 放大策略）
- AND 操作：多个哈希函数组合成一个签名（signature），使得不相似点更难碰撞。
- OR 操作：构建多个哈希表，以提高召回率。
- 关键参数：L（哈希表个数），k（每个表的哈希函数数量）
向量插入
将每个数据点通过所有哈希函数映射到对应桶中。
查询
对目标向量使用相同哈希过程，查询所有桶内的数据点并计算真实距离，选取最相似者。

五、代码实现（以余弦相似度 + Sign-Random-Projection 为例）

import numpy as np

class LSHCosine:
    def __init__(self, dim, k=10, L=5):
        self.dim = dim
        self.k = k
        self.L = L
        self.planes = [np.random.randn(k, dim) for _ in range(L)]
        self.hash_tables = [{} for _ in range(L)]

    def _hash(self, v, planes):
        return tuple((np.dot(planes, v) > 0).astype(int))

    def insert(self, vec_id, vec):
        for i in range(self.L):
            h = self._hash(vec, self.planes[i])
            self.hash_tables[i].setdefault(h, []).append((vec_id, vec))

    def query(self, vec):
        candidates = set()
        for i in range(self.L):
            h = self._hash(vec, self.planes[i])
            bucket = self.hash_tables[i].get(h, [])
            for vec_id, candidate in bucket:
                candidates.add((vec_id, tuple(candidate)))
        return list(candidates)

六、LSH 的优缺点

优点：

对高维数据效果良好，突破“维度诅咒”
支持大规模近似检索
理论基础扎实，可调参数灵活

缺点：

精度不如精确搜索
需要调参（L, k）以达到 Recall/Precision 平衡
多哈希表空间占用较大

七、LSH 的应用场景

搜索引擎：文本或图片的相似性检索（如百度、Google 以图搜图）
推荐系统：相似用户/商品搜索
音频指纹识别：Shazam 利用 LSH 实现音频检索
去重检测：网页/文档去重（SimHash）

八、LSH 与现代向量检索的关系

随着深度学习的发展，现代向量检索（如 FAISS、Annoy、ScaNN）也引入了很多先进的近似搜索算法（如 IVF、PQ、HNSW 等）。但 LSH 仍具有“无训练”“快速构建”“理论清晰”的优势，特别适合快速原型验证、小型离线任务或可解释性要求高的场景。

九、总结

LSH 是连接理论与实践的一座桥梁，它以概率的方式简化了复杂问题，带来了优雅又高效的近似搜索手段。在高维相似性检索场景中，它依然是一种值得关注与应用的重要技术。

引用资料

Gionis, A., Indyk, P., & Motwani, R. (1999). Similarity Search in High Dimensions via Hashing. VLDB.
Datar, M., Immorlica, N., Indyk, P., & Mirrokni, V. S. (2004). Locality-sensitive hashing scheme based on p-stable distributions. SCG.
Andoni, A., & Indyk, P. (2008). Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. CACM.
Erik Bernhardsson. Annoy: Approximate Nearest Neighbors in C++/Python. https://github.com/spotify/annoy
Facebook AI Research. FAISS: A library for efficient similarity search. https://github.com/facebookresearch/faiss