引言
最近做大规模文本去重，我们基于 Fast Similarity Sketching 论文搞了一个 Python 去重包 fastsketchlsh，跟 datasketch 和 rensa 对比了一下。这里主要聊聊传统 k-mins 为什么慢，FastSketch 怎么做到更快，以及跟 LSH 搭配在工程里怎么落地。
经典 MinHash + LSH 回顾
做去重前，先想清楚要去哪种重复。
精确匹配最简单：规范文本后算哈希，查到就删。但对'近似重复'不太管用，比如少量增删改、顺序变化、模板填充之类。
近似去重就用 Jaccard 相似度，文本变 shingle/n-gram 集合，再算交集并集。经典操作是 MinHash 估计 Jaccard，再配 banding LSH 做候选召回。
MinHash 的做法：用 k 个独立哈希函数，每个取集合的最小值。用签名中相等维的比例估计 Jaccard：
Ĵ(A,B) = (1/k) * Σ_{i=1 to k} 1[sig_i(A) = sig_i(B)]
性质是 Pr[sig_i(A) = sig_i(B)] = J(A,B)，无偏估计。例子略（原文保留）。
LSH 方面，把 k 维签名切成 b 个 band，每个 band 有 r 行，如果任意 band 完全相等，就作为候选对。候选概率 P = 1 - (1 - s^r)^b，s 是单行相等概率。这就是经典的 S-curve，通过调 b,r 可以在阈值附近做软门槛。
这条路理论漂亮，工程也用得多，但瓶颈确实存在。
慢在哪里？
拿 datasketch 来说，纯 Python 实现在大规模循环和哈希更新上吞吐不行。rensa 用 Rust 实现了 MinHash，速度上去了很多，但算法复杂度还是没变，依然是 O(k · n)：每个元素都要过 k 个哈希。
实际工作中，n 往往是几千甚至上万 token，k 用 128 或 256，这个乘法开销就挺大了。
那能不能只用一个轮次（或期望常数轮次）就把 k 维签名搞定？FastSketch 的思路就是改为按轮次更新所有桶，桶填满了就停。
FastSketch 原理
核心论文：Fast Similarity Sketching (arXiv:1704.04370v4)。想法很简单：维护 k 个桶，每轮对所有 token 算一个哈希，根据哈希值决定落到哪个桶，每个桶保留自己见到的最小 key（key 是轮次和哈希值的组合，保证早轮次优先）。一旦所有桶都非空，立即停止，不再继续扫。
伪代码（工程版）：
Input : set A, sketch size k, regular rounds 2k
Output: sketch S[1..k]
Initialize S[i] = EMPTY for i = 1..k
# regular rounds
for r = 1..2k:
for each token a in A:
h = hash(r, a)
bin = 1 + (h mod k)
key = (r, h) # 早轮次优先、同轮按哈希最小
S[bin] = min(S, key)
if all bins filled: break
while exists empty bin:
= r +
for each token a in A:
= hash(r, a)
= + (h mod k)
if S is EMPTY:
= (r, h)
S = min(S, key)
return S
