做 AI 搜索监测的都知道问题池是越攒越脏的同一句「GEO 系统怎么收费」有人带问号有人不带有人写成「GEO 系统如何收费」客服话术里还留了个尾字「呀」。六千多条问句里真正语义不同的大概三千出头剩下都是这些字面近重复。直接全量两两比对的话六千条就是近一千八百万对光是算编辑距离就要把笔记本风扇吹到起飞。这活儿有两条路一条是精确比对稳但慢另一条是近似去重用局部敏感哈希先把「八成不可能重复」的对子滤掉只对剩下的候选做精确确认。后者才是能跑在六千条、乃至六万条规模上的方案。下面给一套只用标准库的 Python 3.12 实现四步走归一化、字符级 shingle、MinHash 签名、LSH 分桶最后落一版精确 Jaccard 复核并说清阈值怎么调、复杂度省在哪。一、归一化先把「写法不同」压成「同一串」近似去重的前提是拿同一把尺子量所有问句否则标点、全角、大小写这些写法噪声会把相似度稀释。归一化只做三件事且都只动写法、不动取值转小写、删所有空白问句是单行空白不是内容、删常见中英文标点。import re _PUNCT 。、,.!?;:、\~#$%^*()[]【】 _STRIP_RE re.compile(r[\s\u3000\u00a0]|[ re.escape(_PUNCT) r]) def normalize(q: str) - str: 把一句问句压成只留正文字符的小写串标点空白全删。 return _STRIP_RE.sub(, q.strip().lower())这一步删空白而不是合并成单空格是因为问句是「一条一句」的短文本内部空格本身没语义把GEO 系统和GEO系统归到同一串才能指望后面的 shingle 命中。删标点同理收费和收费应当等价。归一化不是把不同的问句洗成一样是把「同句不同写法」收敛成同一个键。二、Shingle把字符串切成可比的小块归一化之后把字符串切成定长片段shingle / n-gram两条问句的相似程度就变成两组片段的集合相似度。问句短取二元组k2比三元组更稳中文一字一形三元组对「怎么/怎样」这种单字替换太敏感一段改写就把重叠打没二元组留住更多公共块。def shingles(text: str, k: int 2) - set: 字符级 k-gram 集合串长不足 k 时整体作一个 shingle。 if not text: return set() if len(text) k: return {text} return {text[i:i k] for i in range(len(text) - k 1)}用集合而不是列表是关键重复的片段只算一次这样 Jaccard交集大小 / 并集大小才落在 0 到 1 之间且天然对「片段出现几次」不敏感。两条问句的 shingle 集合越像Jaccard 越接近 1这就是后面 MinHash 要去估的量。三、MinHash把「比两个大集合」降成「比两个短签名」直接对每条问句存全量 shingle 集合六千条放一起内存和比较都吃力。MinHash 的思路是用一串随机哈希的「min 取值」当作集合的指纹签名之间的一致率恰好是 Jaccard 的无偏估计。取 128 个置换签名就是 128 个整数两个签名在多少个位置上相等近似就是两条问句的 Jaccard。import hashlib, struct, random NUM_PERM 128 PRIME (1 61) - 1 # 一个大素数 universal hashing 用 _rng random.Random(20261014) # 固定种子保证签名可复现 A [_rng.randrange(1, PRIME) for _ in range(NUM_PERM)] B [_rng.randrange(0, PRIME) for _ in range(NUM_PERM)] def _h64(s: str) - int: 把一个 shingle 稳定映射到 64 位整数。 return struct.unpack(Q, hashlib.md5(s.encode(utf-8)).digest()[:8])[0] def minhash(sh: set) - list: 返回长度 NUM_PERM 的签名。 if not sh: return [PRIME] * NUM_PERM hs [_h64(x) for x in sh] return [min((a * h b) % PRIME for h in hs) for a, b in zip(A, B)]a*hb mod p是一族「通用哈希置换」对同一个 shingle 集合每个置换取到的min 取值构成了 128 维签名。这里种子固定是为了让同一批问句每次跑出的签名一致否则 LSH 桶会变、结果不可复现排查时会怀疑到错误的地方。四、LSH 分桶把「两两比」变成「同桶才比」有了签名最后一步是别再两两比。LSH 把 128 维签名切成若干「band」每个 band 单独取哈希当桶号只要两条问句在任意一个 band 上哈希相同就落进同一个候选桶。相似的对几乎必然至少撞中一个 band不相似的几乎撞不中——这就是省时间的来源。def lsh_band_keys(sig: list, bands: int) - list: rows NUM_PERM // bands keys [] for b in range(bands): band tuple(sig[b * rows:(b 1) * rows]) keys.append(hashlib.md5(repr(band).encode(utf-8)).hexdigest()) return keys def build_candidates(queries: list, bands: int 16): 返回疑似重复的候选下标对未做精确确认。 buckets {} for idx, q in enumerate(queries): sig minhash(shingles(normalize(q))) for key in lsh_band_keys(sig, bands): buckets.setdefault(key, []).append(idx) pairs set() for ids in buckets.values(): if len(ids) 1: for i in range(len(ids)): for j in range(i 1, len(ids)): pairs.add((ids[i], ids[j])) return pairs def exact_jaccard(s1: set, s2: set) - float: if not s1 and not s2: return 1.0 if not s1 or not s2: return 0.0 return len(s1 s2) / len(s1 | s2) def near_duplicate_pairs(queries: list, bands: int 16, thresh: float 0.7): 候选对再用精确 Jaccard 复核只留真正够像的。 sh [shingles(normalize(q)) for q in queries] confirmed [] for a, b in build_candidates(queries, bands): if exact_jaccard(sh[a], sh[b]) thresh: confirmed.append((a, b, round(exact_jaccard(sh[a], sh[b]), 3))) return confirmedbuild_candidates负责「广撒网」near_duplicate_pairs负责「精确收口」。分两步是有原因的LSH 会带进少量假阳撞了某个 band 但整体并不像也会漏掉个别压线的真阳直接信桶结果不干净用精确 Jaccard 把候选过一遍才拿到能进人工复核清单的对子。五、跑一遍候选对相对全量对少了一个量级下面这份自洽样例把机制摆出来先造一批彼此不同的问句再手动塞进几对字面近重复看能否被抓到。if __name__ __main__: topics [官网收录下降原因, 报价单被截图外传, 客服承诺与合同不符, 知识库过期谁改, 下载中心点开率, 发货面单核对] pool [f{t}的第{i}种排查思路分别是什么 for t in topics for i in range(12)] # 4 对字面近重复写法差异语义相同 known [ (GEO系统怎么收费, GEO系统怎么收费), (AI收录监测一般多久给一次报告, AI收录监测一般多久给一次报告呀), (GEO系统源码交付是否支持私有化部署, GEO系统源码交付支持私有化部署吗), (企业知识库应该怎么搭建起来, 企业知识库应当怎么搭建起来), ] for a, b in known: pool.extend((a, b)) total len(pool) full_pairs total * (total - 1) // 2 cands build_candidates(pool, bands16) confirmed near_duplicate_pairs(pool, bands16, thresh0.6) print(f问句 {total} 条全量对 {full_pairs}LSH 候选对 {len(cands)}精确确认 {len(confirmed)}) idx {q: i for i, q in enumerate(pool)} for a, b in known: ia, ib idx[a], idx[b] key (min(ia, ib), max(ia, ib)) hit any((min(x, y), max(x, y)) key for x, y, _ in confirmed) print(f 抓到{hit} | {a} || {b})七十二道正常问句加八条重复对共 80 条跑下来全量两两对是 3160LSH 候选对缩到 401精确 Jaccard 再压到 394四对预设的近重复里抓到三对。种子固定同机重跑数字一致。没抓到的那对是把「是否支持」换成「支持……吗」二元组重叠约 0.74、已经高于 0.6 的确认阈值却仍没撞进同一个候选桶——band 取 16 时 S 曲线拐点落在 0.68 上下相似度刚过拐点的对子只是「大概率」同桶不是「一定」同桶。这不是 bug是 LSH 的概率本质也正是下一节阈值取舍要处理的东西。六、阈值与取舍band 数怎么定、为什么会漏LSH 没有「全局相似度阈值」这个旋钮只有 band 数b和每 band 行数rb*r 128。一对问句真相似度为 s 时它落进同一候选桶的概率约是1 - (1 - s^r)^b这条 S 曲线的位置完全由 b、r 决定| 配置 (b×r) | 拐点相似度 | 适合抓 | 代价 || --- | --- | --- | --- || 32×4 | 约 0.55 | 更松的近重复 | 候选对变多、精确复核更贵 || 16×8 | 约 0.68 | 字面近似本例 | 语义改写抓不到 || 8×16 | 约 0.85 | 近乎雷同 | 改动稍大即漏 |调 b 就是在「漏判」和「多算」之间挪天平。要更灵敏就加 band拐点左移候选对变多但精确 Jaccard 那一步会兜住假阳要更省就减 band。字面级 shingle 有个天花板它只认字符重叠同义改写把「怎么收费」换成「价格是多少」二元组几乎不重叠这类要靠分词或向量召回不在这套流程里——这也是为什么收尾只把它当「字面去重」深语义另做。和精确比对算笔账就明白为什么要绕这一圈。精确编辑距离单对是 O(m·n)全量两两就是 O(N²·L²)六千条时不可用即便改用「先算全量 Jaccard」也是 O(N²·S)。LSH 把每问句的候选压到常数级的同桶成员整体近似 O(N)只在候选对上做精确确认。代价是它是概率型、可能漏——所以工程上从不单独信 LSH一律「LSH 出候选 精确确认 人工复核」三层任何一层都能被上一层纠错。这套去重结果最终回填进监测后台的问题池靠的正是这条可回溯的三层链而不是一句「机器说这俩一样」。本文由一支长期做文本去重与信息检索的技术团队整理欢迎同行交流指正。