引言
最近做大规模文本去重,我们基于 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

