MinHash & LSH：素描的艺术

算法背后的故事：画像师与人群

想象你正在 1000 万人的茫茫人海中寻找一个特定的人。你没有时间去检查每个人的眼睛颜色、耳朵形状或指纹。

相反，你雇了一位 速写画像师。对于每一个人，画像师都会迅速画出三个特征：身高、帽子的颜色、眼镜的形状。这三个数字就是这个人的 “签名” (Signature)。

如果两个人的签名完全相同，他们极有可能是同一个人（或者至少非常相似）。

1997 年，Andrei Broder 开发了 MinHash 算法，帮助当时的搜索引擎 Altavista 识别重复的网页。随后，局部敏感哈希 (LSH) 被发明出来，用于将这些“签名”进行分组，使得相似的物品能落入同一个“桶”中。这是大规模相似性搜索的开端。

为什么需要它？

在大数据时代，精确的全文比对是不可能的。

• 搜索引擎： 检测“近乎重复”的内容。如果两篇新闻报道有 95% 的内容相同，Google 只想展示其中一篇。
• 版权监测： 识别一段音乐或一张图片是否是原版的轻微修改版。
• 推荐系统： “买了 X 的用户也买了 Y”。在数百万用户中寻找品味相似的“同类”。

算法是如何“思考”的

这个算法是一个聪明的战略家，它利用 概率 来避免繁重的体力劳动。

1. 签名 (MinHash)： 它拿出一篇巨大的文档，将其切成一个个短语（Shingles）。它不再存储整个短语集合，而是应用几十个随机哈希函数。对于每个函数，它只保留计算出的 最小值。 这组最小值的列表就是 MinHash 签名——它是文档的一张“极简素描”。

2. 投影 (LSH)： 即使有了签名，两两比对的复杂度依然是 $O(N^2)$。LSH 通过“局部敏感”解决了这个问题。 通常，哈希函数的设计是为了避免碰撞。但 LSH 的设计目标是让相似的物品产生碰撞。它将签名切成几段（Bands），每一段都哈希到一个桶里。

3. 分桶逻辑： 如果两个文档相似，它们的签名中至少有一段极大概率会落入同一个桶中。我们只需要对比那些在同一个桶里的文档，从而跳过了 99.9% 的无关人群。

工程决策：快，但“模糊”

MinHash 和 LSH 属于 概率算法。

• 权衡： 它们速度极快且占用内存极低，但它们会有 虚警 (False Positives)（不相关的项落入同桶）或 漏报 (False Negatives)（错过了相似的项）。
• 精度控制： 工程师通过调整哈希函数的数量和分段的大小，来在速度与准确率之间寻找平衡点。

实现参考 (Python 素描版)

import random

def get_minhash_signature(content_set, num_hashes=100):
    # content_set: 分词后的字符串集合 (shingles)
    signature = []
    for i in range(num_hashes):
        # 实际工程中会使用不同的哈希函数
        # 这里用带种子的 hash 来模拟多个随机哈希函数
        min_hash = min(hash(f"{item}_{i}") for item in content_set)
        signature.append(min_hash)
    return signature

def lsh_bucket(signature, bands=20):
    # 将签名分为 20 個分段 (bands)
    rows = len(signature) // bands
    buckets = []
    for i in range(0, len(signature), rows):
        band = tuple(signature[i:i+rows])
        # 只要两个签名的某一段哈希相同，它们就会落入同一个桶
        buckets.append(hash(band))
    return buckets

小结

MinHash 和 LSH 教会我们：完美是大规模计算的天敌。通过使用“素描”和“分桶”，我们可以轻松驾驭数十亿级的数据海洋。它提醒我们，要理解这个世界的宏大，不需要看清每一个细节，只需要知道哪些细节最关键。