引言
“用户把 brother 打成 borther，客服把客户名抄错一位，爬虫抓到了 99% 相同的两篇文章”——模糊匹配要回答的就是"这两段文本像不像、差几个字符、是不是同一个东西"。本文从零搭一套匹配工具箱：先讲最经典的编辑距离（Levenshtein 及其优化、Damerau 的调换），再讲 token 级的 Jaccard/Dice 与擅长人名匹配的 Jaro-Winkler，接着讲模糊搜索怎么落地（fzf 原理、编辑距离阈值、候选集），再讲大规模去重的利器 SimHash/MinHash（为什么不是两两比较），最后给一个可落地的"匹配引擎"设计。
前置：/others-big-o-complexity-guide/（DP 的复杂度）、/regex-deep-dive/（文本模式 vs 模糊匹配的分野）。搜索与索引实践见 [[algorithm-interview]]、[[database]]。
目录
- 1. 模糊匹配的三种对象：字符、token 与语义
- 2. Levenshtein：编辑距离与动态规划
- 3. 优化：滚动数组、带宽与 Bitap
- 4. Damerau-Levenshtein：把调换算进去
- 5. Jaccard 与 Dice：token 级集合相似
- 6. Jaro-Winkler：人名的好帮手
- 7. 模糊搜索落地：阈值、候选集与 fzf 原理
- 8. 大规模去重：SimHash 与 MinHash
- 9. 匹配引擎设计：从算法到服务
- 10. 速查表与一句话记忆
- 延伸阅读
1. 模糊匹配的三种对象：字符、token 与语义
先想清楚在哪个粒度匹配，比选算法更关键：
| 粒度 | 衡量 | 算法 | 典型场景 |
|---|---|---|---|
| 字符 | 差几个字符 | 编辑距离 | 拼写纠错、人名 |
| token | 共享多少个词 | Jaccard/Dice | 文章去重、抄袭检测 |
| 语义 | 意思像不像 | 向量/嵌入 | 语义搜索、推荐（见 [[ai-ml]]） |
直觉："爱丽丝的奇幻冒险" 与 "爱丽丝梦游仙境"——字符层差很多，但 token/语义层是一个东西。选粒度 = 选问题：纠错用字符、去重用 token、语义搜索用向量。
两个文本的"像"可以来自三个层面，先问"我关心哪个层面"
混合策略：真实系统常先粗筛（token/SimHash）再精比（编辑距离）——这是第 7、9 节的主线。
记忆：字符管拼写、token 管内容、语义管意思——先定粒度，再选算法。
2. Levenshtein：编辑距离与动态规划
Levenshtein 距离：把一个字符串变成另一个所需的最少插入/删除/替换次数。
"kitten" → "sitting"
k→s（替换）, e→i（替换）, 末尾 +g（插入） → 距离 3
动态规划：dp[i][j] = 把 s[:i] 变成 t[:j] 的最小代价：
def lev(a, b):
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i # 删除 i 个
for j in range(n + 1):
dp[0][j] = j # 插入 j 个
for i in range(1, m + 1):
for j in range(1, n + 1):
cost = 0 if a[i-1] == b[j-1] else 1
dp[i][j] = min(
dp[i-1][j] + 1, # 删除 a[i-1]
dp[i][j-1] + 1, # 插入 b[j-1]
dp[i-1][j-1] + cost, # 替换
)
return dp[m][n]
print(lev("kitten", "sitting")) # 3
复杂度：时间 O(m·n)、空间 O(m·n)——m、n 各几千时就要优化（见下节）。
相似度归一化：距离是绝对值，跨长度比较要转成 0–1 相似度：
similarity = 1 - lev(a, b) / max(len(a), len(b))
"kitten" vs "sitting": 1 - 3/7 ≈ 0.57
记忆：Levenshtein 是"字符操作数"，DP 填表 O(mn)；跨长度比较要用归一化相似度。
3. 优化：滚动数组、带宽与 Bitap
Levenshtein 三档优化，对应三种规模：
① 滚动数组（省空间）：只保留上一行 → 空间 O(min(m,n))：
def lev_roll(a, b):
if len(a) < len(b): a, b = b, a
prev = list(range(len(b) + 1))
for i, ca in enumerate(a, 1):
cur = [i]
for j, cb in enumerate(b, 1):
cur.append(min(prev[j] + 1, cur[-1] + 1,
prev[j-1] + (ca != cb)))
prev = cur
return prev[-1]
② 带宽优化（限制最大距离）：只求"距离是否 ≤ K"（K 是阈值）时，对角线带内计算 → 时间 O(K·min(m,n))。模糊搜索正是这个模式——不问"精确距离"，只问"小于 2 吗"。
③ Bitap（位并行）：把 DP 行编码成整数位运算 → 对小串/模式匹配接近 O(m·n/word)，被 agrep 等工具使用。
选择矩阵：
| 场景 | 优化 |
|---|---|
| 一次精确算 | 滚动数组 |
| 模糊搜索（阈值 K） | 带宽优化 |
| 超短模式、高吞吐 | Bitap |
| 巨串 | 更激进：SIFT4 / 分块哈希 |
记忆：空间用滚动数组、阈值用带宽、吞吐用 Bitap——优化都是为了"别把 O(mn) 真跑满"。
4. Damerau-Levenshtein：把调换算进去
人类打字最常犯的错是"调换相邻字符"（teh ↔ the）。Levenshtein 把 teh→the 算成 2 次操作（删 e + 插 e 或替换两次），但直觉上只是"调换一下"。
Damerau-Levenshtein 增加第四种操作换位（transposition），teh→the 距离=1：
def damerau(a, b):
# 核心：四种操作取最小 + 相邻换位
# dp[i][j] = min(删, 插, 换, 换位(dp[i-2][j-2] + 1) 当 a[i-1]==b[j-2] and a[i-2]==b[j-1])
pass
Damerau vs Levenshtein：
| 操作 | Levenshtein | Damerau |
|---|---|---|
| 插入 / 删除 / 替换 | ✓ | ✓ |
| 相邻调换 | ✗（算 2 步） | ✓（算 1 步） |
| 典型用途 | 通用纠错 | 人名、拼写、键盘误输 |
工程含义：做"用户输入纠错"（搜索框、地址、人名）时，Damerau 更贴近人类错误模型——teh 应被当成距离 1 而不是距离 2，否则纠错建议会漏掉最常见的错误形态。
记忆：打字错误里调换是大头——要纠"teh→the"这类错，用 Damerau 而非 Levenshtein。
5. Jaccard 与 Dice：token 级集合相似
当关心"内容重了没"（去重、抄袭、摘要对比），把文本切成 token（词 / n-gram），比集合重合度：
Jaccard 系数：
J(A, B) = |A ∩ B| / |A ∪ B|
"小猫小狗" {小猫,小狗} vs "小猫小兔" {小猫,小兔}
J = 1/3 ≈ 0.33
Sørensen-Dice（给重合更多权重）：
Dice = 2|A∩B| / (|A| + |B|)
上例 Dice = 2/4 = 0.5
n-gram 的重要作用：按整词切分对"轻微改字"不敏感，按 字符 n-gram（如 2-gram）切分更鲁棒：
"hello" → {"he","el","ll","lo"} (2-gram)
"helloo" → {"he","el","ll","lo","oo"}
重合 3/5 → Dice = 2·4/(4+5) = 0.89 # 即便差一个字符也很相似
def jaccard(a, b):
sa, sb = set(a), set(b)
return len(sa & sb) / len(sa | sb)
def dice(a, b):
sa, sb = set(a), set(b)
return 2 * len(sa & sb) / (len(sa) + len(sb))
适用：文章/评论/代码去重、抄袭检测、相似摘要。上限：集合方法对"顺序敏感"的文本不敏感（"A B C" 与 "C B A" Jaccard 相同）——需要顺序就用编辑距离或 SimHash 的滑窗。
记忆：Jaccard/Dice 管"内容重合度"——字符 n-gram 切分对轻微改写鲁棒，比整词更耐用。
6. Jaro-Winkler：人名的好帮手
人名匹配用编辑距离并不理想："Smith" 与 "Smithson" 编辑距离大，但显然同源；且开头字符相同的人类直觉权重很高。
Jaro 相似度（基于匹配窗口 + 调换次数）：
Jaro(s1, s2) =
(m/|s1| + m/|s2| + (m - t/2)/m) / 3
m = 匹配字符数（窗口 = max(len)/2 - 1）
t = 匹配字符中的调换次数
"MARTHA" vs "MARHTA" → 高相似（仅调换）
Jaro-Winkler 在 Jaro 基础上给"共同前缀“加权重：
Jaro-Winkler = Jaro + 前缀长度(≤4) × 0.1 × (1 - Jaro)
"SMITH" vs "SMITHE": 前缀 5 截到 4 → 加权 → 更高
为什么适合人名：开头一致性强（姓前缀）、长度差异常见（敬语、后缀）、调换是手输常见错——三者都在 Jaro-Winkler 里被建模。
典型相似度对比：
"MARTHA" vs "MARHTA" 编辑距离 2 → Jaro-Winkler ≈ 0.96
"SMITH" vs "SMYTHE" 编辑距离 3 → Jaro-Winkler ≈ 0.87（前缀 SM 加权）
工程注意：Jaro-Winkler 对前缀依赖过强——若数据里有大量不同前缀的别名（"William"/"Bill"），会低估相似；要结合编辑距离兜底。
记忆：人名匹配选 Jaro-Winkler——匹配窗口 + 调换 + 前缀加权，三件事都建模。
7. 模糊搜索落地：阈值、候选集与 fzf 原理
模糊搜索（fzf / IDE 的 go-to-file、纠错建议）的工程本质：
用户输入 q → 从候选集里找出"编辑距离 ≤ K"或"fzf 打分高"的前几名
三步落地：
1. 候选集（过滤）：排除明显不可能的（前缀/词法过滤）→ 缩小到可算规模
2. 打分（精比）：编辑距离 / Jaro / fzf 自定义打分（连续匹配加分、首字母加分）
3. 截断（Top-K）：只返回前 N 个，带上分值供排序
fzf 的匹配直觉（子序列 + 打分）：
fzf 允许"跳着匹配"（子序列），不是严格的编辑距离：
输入 "abc" 匹配 "aXbYcZ"（跳过的字符扣分）
→ 连续匹配、命中前缀、命中 CamelCase 首字母 → 加分
阈值选型：
| 场景 | 阈值（相似度） |
|---|---|
| 文件名模糊搜索 | 无严格阈值，排序取 Top |
| 拼写纠错 | Damerau ≤ 2 |
| 去重判重 | Dice ≥ 0.8 或 SimHash ≤ 3 位差异 |
| 人名/地址匹配 | Jaro-Winkler ≥ 0.9 |
候选集如何不失控：对海量候选（百万级），先用 前缀索引 / 倒排 / n-gram 索引捞出一个小的候选桶，再精比——先索引粗筛、再精确细比是模糊搜索性能的核心。
记忆：模糊搜索 = 索引粗筛候选 → 精比打分 → Top-K 截断；阈值决定"算不算匹配”，索引决定"能不能算完"。
8. 大规模去重：SimHash 与 MinHash
两两计算编辑距离是 O(n²)——一亿条文本两两比不可行。去重需要"把文本变成可比指纹、按指纹快速分组"。
SimHash（近邻哈希）——Google 网页去重的经典：
1. 把文本切成 token，每个 token 算 64 位哈希
2. 对每个 token：位为 1 加权重、为 0 减权重
3. 按符号把每位归成 0/1 → 得到 64 位 SimHash
4. 两个文本的 Hamming 距离 ≤ K（如 3）→ 判为相似
def simhash(tokens, bits=64):
vec = [0] * bits
for t in tokens:
h = hash(t) & ((1 << bits) - 1)
for i in range(bits):
vec[i] += 1 if (h >> i) & 1 else -1
return sum((1 << i) for i in range(bits) if vec[i] > 0)
核心特性：相似的输入 → 相近的指纹（微小改动只翻转少数位），所以"Hamming ≤ K"就能聚类。
MinHash——估计 Jaccard 的指纹法：
对集合 S，取 k 个哈希函数，记录每个集合的最小哈希值（min-hash）
→ 两个集合的 min-hash 重合率 ≈ Jaccard
→ 用 min-hash 签名做 LSH 分桶，找候选相似对
SimHash vs MinHash：
| 维度 | SimHash | MinHash |
|---|---|---|
| 相似性 | Hamming（近邻） | Jaccard 估计 |
| 适合 | 内容级去重、近似文本 | 集合重合、推荐近邻 |
| 索引 | 分段桶（64 位切 4 段） | LSH 分桶 |
LSH（Locality-Sensitive Hashing）：把指纹切成段建桶，同一段相同的进同桶——桶内才两两比，把 O(n²) 降到近线性。
记忆：海量去重不做两两比——SimHash 给"近似文本指纹"、MinHash 估 Jaccard，LSH 分桶后只在桶内细比。
9. 匹配引擎设计：从算法到服务
把散落的算法组装成一个匹配引擎的模板：
请求：文本 A
1. 规范化：小写、去空白、简繁体归一、拼音归一（人名）
2. 候选检索：SimHash/倒排/n-gram 索引 → 候选桶
3. 精比打分：按对象选算法（人名 Jaro-Winkler、内容 Dice、拼写 Damerau）
4. 阈值与排序：相似度 ≥ T → 返回 Top-K 带分值
工程要点：
- 规范化是"免费的正确率"：大小写/全半角/空白不一致是最大噪声
- 多算法融合：粗筛（快、粗）+ 精比（慢、准）分层
- 阈值要校准：用标注样本（TP/FP）选阈值，别拍脑袋
- 缓存热结果：同 input 重复匹配直接命中
一个拼写纠错的组合拳：
def suggest(word, dictionary):
# 1. 完全命中直接返回
if word in dictionary: return word
# 2. 粗筛：前缀/首字母候选（避免全词典算距离）
cands = prefilter(word, dictionary)
# 3. 精比：Damerau ≤ 2 + 归一化相似度排序
ranked = sorted(cands, key=lambda w: -sim(word, w))
return ranked[0] if sim(word, ranked[0]) >= 0.7 else word
正确率靠数据：别指望单一算法完美——规则 + 统计 + 人工反馈一起调，匹配引擎才耐用。
记忆：匹配引擎 = 规范化 + 索引粗筛 + 分层精比 + 校准阈值 + 缓存——正确率靠规则统计人工三管齐下。
10. 速查表与一句话记忆
全篇速查：
| 需求 | 算法 | 关键点 |
|---|---|---|
| 字符级距离 | Levenshtein | DP O(mn)，滚动数组优化 |
| 键盘误输 | Damerau-Levenshtein | 调换算 1 步 |
| 阈值模糊搜索 | 带宽优化 / Bitap | 只算"≤K" |
| 内容重合 | Jaccard / Dice | n-gram 更鲁棒 |
| 人名匹配 | Jaro-Winkler | 前缀加权 |
| 文件/路径模糊 | fzf 子序列打分 | 连续命中加分 |
| 海量去重 | SimHash / MinHash | LSH 分桶 |
| 拼写纠错 | Damerau + 候选集 | 粗筛 + 精比 |
一句话记忆：匹配粒度定算法——字符用编辑距离（Damerau 补调换）、内容用 Jaccard/Dice（n-gram 切分）、人名用 Jaro-Winkler、海量去重用 SimHash/MinHash + LSH 分桶；工程上先规范化再粗筛再精比，阈值用样本校准，缓存热结果——模糊匹配不是玄学，是把’像不像’拆成可算的步骤。
延伸阅读
- /others-big-o-complexity-guide/ — 动态规划与复杂度预算
- /regex-deep-dive/ — 精确模式匹配 vs 模糊匹配的分野
- /time-timezone-handling/ — 规范化在匹配里的重要性
- [[ai-ml]] — 向量语义相似度（超越字符/token 层）
- [[algorithm-interview]] — DP 与字符串算法的面试视角
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。