3、编辑距离算法：从定义到纠错实战
好，咱们今天聊一个搜索引擎里特别实在的东西——编辑距离。
你想想看，用户输入「苹国」的时候，系统怎么知道他想搜的是「苹果」？说白了，就是靠算两个词之间的「距离」。这个距离越小，越有可能是拼写错误。
3.1 编辑距离的定义
编辑距离，英文叫 Edit Distance。它衡量的是：把一个字符串变成另一个字符串，最少需要多少次操作。
允许的操作就三种：
- 插入：加一个字符
- 删除：去掉一个字符
- 替换：换成一个别的字符
举个例子。「cat」变成「cars」：
- 把 t 替换成 r → 「car」
- 再插入一个 s → 「cars」
两步搞定，编辑距离就是 2。
核心理解：编辑距离越小，两个词越像。搜索引擎纠错时，就是找编辑距离最小的那个正确词。
3.2 Levenshtein 距离——最经典的编辑距离
Levenshtein 距离是编辑距离里最常用的一种。它把三种操作都算作「一步」，权重都是 1。
我记得刚入行那会儿，有个同事问我：「为什么不用汉明距离？」我说：「汉明距离只能处理等长字符串，用户输入『苹国』和『苹果』长度都不一样，怎么比？」
Levenshtein 距离就不挑长度。它用动态规划，把两个字符串的所有对齐方式都算一遍，找出最小代价。
小提示：实际项目中，我习惯把替换操作的代价设成 2，插入和删除设成 1。因为替换往往意味着用户「看错了」，比多打或少打一个字母更严重。这个调参技巧，能显著提升纠错准确率。
3.3 动态规划实现——手写一个 Levenshtein
动态规划听起来高大上，其实就是一个填表的过程。我带你手写一遍。
假设我们要算「kitten」和「sitting」的距离。
先画一个 (m+1) × (n+1) 的表格。行是第一个词，列是第二个词。
"" s i t t i n g
"" 0 1 2 3 4 5 6 7
k 1
i 2
t 3
t 4
e 5
n 6填表规则很简单：
- 如果两个字符相同，取左上角的值
- 如果不同，取「左、上、左上」三个值的最小值 + 1
我直接上代码吧，这是我最常用的版本：
def levenshtein_distance(s1, s2):
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 初始化边界
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
# 填表
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(
dp[i - 1][j] + 1, # 删除
dp[i][j - 1] + 1, # 插入
dp[i - 1][j - 1] + 1 # 替换
)
return dp[m][n]跑一下「kitten」和「sitting」：
| "" | s | i | t | t | i | n | g | |
|---|---|---|---|---|---|---|---|---|
| "" | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| k | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| i | 2 | 2 | 1 | 2 | 3 | 4 | 5 | 6 |
| t | 3 | 3 | 2 | 1 | 2 | 3 | 4 | 5 |
| t | 4 | 4 | 3 | 2 | 1 | 2 | 3 | 4 |
| e | 5 | 5 | 4 | 3 | 2 | 2 | 3 | 4 |
| n | 6 | 6 | 5 | 4 | 3 | 3 | 2 | 3 |
右下角是 3。所以「kitten」到「sitting」需要 3 步。
注意：我曾经在线上环境踩过一个坑——直接用这个算法处理中文。中文一个汉字占 2-3 个字节，直接按字符算会出大问题。一定要先做分词或按 Unicode 码点处理。
3.4 编辑距离在纠错中的应用
理论讲完了，咱们聊聊怎么用。
搜索引擎纠错的流程一般是这样的：
- 用户输入查询词 Q
- 在词典里找所有与 Q 编辑距离 ≤ 2 的词
- 按编辑距离从小到大排序
- 取前 N 个作为候选纠错结果
我建议你设一个阈值。距离为 0 就是完全匹配，不用纠错。距离为 1 基本是笔误，直接改。距离为 2 可能是同音字或形近字，需要结合上下文判断。
举个例子。用户搜「苹国」：
- 和「苹果」距离 = 1（把「国」换成「果」）
- 和「平果」距离 = 1（把「苹」换成「平」）
- 和「苹果园」距离 = 2（插入「园」，替换「国」）
距离最小的就是「苹果」和「平果」。再结合搜索热度，大概率选「苹果」。
实战经验：我在做电商搜索时发现，用户搜「苹国」有 80% 是想买苹果手机，只有 20% 是水果。所以不能只看编辑距离，还得加权重——热门词优先。
另外，性能问题也要考虑。词典如果有 100 万个词，每个查询都算一遍编辑距离，那服务器得炸。我常用的优化手段：
- 前缀过滤：只算首字母相同的词
- 长度过滤：只算长度差 ≤ 2 的词
- BK 树：用树结构加速查找，能把 O(n) 降到 O(log n)
嗯，这些优化技巧咱们后面章节会细讲。今天先把编辑距离吃透。
最后总结一句：编辑距离是搜索引擎纠错的基石。你把它搞明白了，后面学什么模糊匹配、拼音纠错，都会轻松很多。