地址模糊匹配实测:长度剪枝会丢 7% 召回,2-gram 倒排 + Myers 提速 33 倍
一、问题:数据治理里最贵的一步是"找相似"
做地址、企业名、商品标题清洗时,真正耗时的不是清洗规则,而是把一条脏数据和标准库里的 N 条标准值做匹配。业界默认做法是算编辑距离取最小,也就是 O(N×M) 的全部两两比较。5000 条待清洗地址 × 300 条标准地址只有 150 万次比较,听起来不多,但纯 Python 跑一次要 48 秒;换成 10 万条、1 万条标准库,就变成 10 亿次,单机一天都跑不完。
本文用可复现的实测回答三个问题:编辑距离能不能更快算、长度剪枝能不能放心用、倒排预筛值不值得加。
二、实验设置
- 标准库:30 个城市 × 10 条街道组合,共 300 条,平均长度 16 字。
- 脏数据:随机取标准值后施加 1~2 次噪声(删字、插字、换成形近/音近字),固定种子,5000 条。
- 环境:Python 3.13,纯标准库,单线程,Windows。三组方法跑同一批数据,与暴力 DP 结果逐条比对。
三、结论一:暴力 DP 是准确率天花板,但不能当生产方案
暴力 DP 5000 条耗时 48.55 秒,Top-1 命中率 100%。它是基线,也是后面所有加速手段的对照物:任何优化只要和它不一致,就是优化带来了精度损失。
单对比较耗时 37.6 μs,说明瓶颈纯粹在比较次数上。所以要提速只有两条路——让每次比较更快,或者让比较次数更少。
四、结论二:长度剪枝是陷阱,会静默丢掉 7% 的召回
最常见的"优化"是先按长度过滤:只要 |len(q)-len(s)| > 1 就跳过。这样做比较次数从 150 万降到 107 万,耗时只从 48.55 s 降到 38.18 s(1.3 倍),但 Top-1 命中率掉到 93.06%。
原因很直接:一条地址如果被连续删了两个字,长度就差 2。长度窗口 ±1 会把这些样本直接排除,而它们恰恰是最难、最需要被纠正的一批。
把窗口放宽到 ±2,命中率回到 100%,耗时反而涨到 51.49 s——比不做剪枝还慢。这就是长度剪枝的本质:它省下的比较次数,被"多做一轮长度分桶查找"吃掉了。 结论:长度只能当粗过滤的第一层,不能作为唯一的剪枝手段。
五、结论三:Myers 位并行让单次比较快 3.4 倍
编辑距离的递推里,每一列只有"匹配/插入/删除"三种状态,可以用位运算并行处理整列。Python 的大整数天然支持任意位宽,正好拿来当位向量:
def myers(a, b):
peq = {}
for i, ch in enumerate(a):
peq[ch] = peq.get(ch, 0) | (1 << i) # 每个字符的位置掩码
m, full = len(a), (1 << len(a)) - 1
pv, mv, score = full, 0, m
for ch in b:
eq = peq.get(ch, 0)
xv = eq | mv
xh = (((eq & pv) + pv) ^ pv) | eq
ph = mv | (~(xh | pv) & full)
mh = pv & xh
score += 1 if ph & (1 << (m - 1)) else (-1 if mh & (1 << (m - 1)) else 0)
pv = ((mh << 1) & full) | (~(xv | ph) & full)
mv = (ph << 1) & full & xv
return score
实测单对 11.1 μs,比 DP 的 37.6 μs 快 3.4 倍;抽查 2000 对距离值与 DP 完全一致,零精度损失。不做任何预筛、只换成 Myers,5000 条全量比对也只要约 15 秒。
六、结论四:2-gram 倒排把比较次数砍掉 93%,叠加后提速 33 倍
真正的数量级提升来自"少比"。把标准库每条地址切成 2-gram 建倒排索引,查询时统计候选命中的 gram 数,取 Top-K 候选再精算距离。索引构建只要 1.0 ms,305 个词项、4497 个倒排项。
| 方案 | 耗时 | 比较次数 | Top-1 |
|---|---|---|---|
| 暴力 DP | 48.55 s | 1,500,000 | 100% |
| 长度剪枝 ±1 | 38.18 s | 1,071,354 | 93.06% |
| Myers 全量 | ~15 s | 1,500,000 | 100% |
| 倒排 + Myers (K=5) | 0.61 s | 25,000 | 100% |
| 倒排 + Myers (K=20) | 1.44 s | 100,000 | 100% |
K 值不需要很大:K=5 已经把 5000 条全部命中正确,比较次数只有暴力方案的 1.67%。K 从 5 加到 50,耗时线性涨 5 倍而准确率没有任何提升——K 应该由候选质量决定,而不是拍一个"越大越保险"的数字。
七、落地建议
- 分层:倒排负责召回(要宽),编辑距离负责精排(要准),不要指望一层解决。
- 别用长度剪枝换精度:它省的时间可以用位并行拿回来,但丢的召回补不回来。
- K 取 5~10 就够:先看候选覆盖率再调,盲目加大只是把省下的时间还回去。
- 索引按增量维护:标准库变化远慢于数据流,倒排可以常驻内存,1 ms 重建成本完全可忽略。
150 万次比较听起来很小,但乘以真实数据量就是天壤之别。把 48 秒压到 0.61 秒的,不是更快的 CPU,而是换掉了"全部两两比较"这个默认假设。
- 点赞
- 收藏
- 关注作者
评论(0)