曾接触的一个历史系统，里面有一段拼写检查的代码，判断两个词"像不像"的逻辑是——先比长度，长度一样就逐字符比，允许多少个字符不同。这方法对等长词还行，一遇到"KITTEN"和"SITTING"这种长度不一样的，直接歇菜。
后来我翻了翻那段代码的注释，写着"TODO：有空改成 Levenshtein"。这个"有空"拖了至少两年。
Levenshtein 距离，也叫编辑距离。简单说就是：把一个字符串变成另一个字符串，最少需要多少次操作。操作只有三种：插入一个字符、删除一个字符、替换一个字符。为什么是这三种？因为这是人类编辑文本最自然的方式——你改错字时无非就是加字、删字、换字。
从一个例子开始，KITTEN 怎么变成 SITTING
KITTEN 到 SITTING，肉眼一看就知道要改几个地方。但计算机需要精确的算法来计算。
我把过程拆开看：
第一步：K → S，替换。这一步花费 1 次操作。
第二步：I → I，字符相同，不动。花费 0 次。
第三步：T → T，相同。花费 0 次。
第四步：T → T，相同。花费 0 次。
第五步：E → I... 不对。到了第五步开始出问题了。KITTEN 是 6 个字符，SITTING 是 7 个字符。不能简单对应着比，因为 SITTING 比 KITTEN 多了一个 G。
这就是最容易被忽视的地方——长度不一样的时候，需要的操作数不能光靠替换来算，必须有插入或删除参与。
所以正确的编辑序列是：
- 替换 K → S（K 变成 S）
- I 保持不变
- T 保持不变
- T 保持不变
- E 保持不变
- 插入 G（末尾补一个 G）
一共 3 次操作。这就是 Levenshtein 距离 = 3 的含义。
但问题来了：计算机怎么知道"保留 E 然后插入 G"比"把 E 替换成 I 然后把 N 替换成 NG"更优？这需要我们设计一个算法让计算机能自己找最短路径。
动态规划矩阵，计算机怎么"看见"最短路径
第一次看动态规划的代码时有个疑惑：它怎么保证找到的是"最少"操作数？后来画了一遍矩阵就明白了。
构建一个 (m+1)×(n+1) 的矩阵，行对应源字符串 KITTEN，列对应目标字符串 SITTING。多出来的 1 行 1 列表示空字符串。
矩阵初始化很简单：
- dp[0][j] = j：空字符串变成 SITTING 的前 j 个字符，需要 j 次插入
- dp[i][0] = i：KITTEN 的前 i 个字符变成空字符串，需要 i 次删除
为什么第一行第一列的值是递增的？因为从空串到" S"需要 1 次插入，到"SI"需要 2 次，以此类推。同理，删除也是。
然后填充矩阵的规则是：
dp[i][j] = min(
dp[i-1][j] + 1, // 删除
dp[i][j-1] + 1, // 插入
dp[i-1][j-1] + cost // 替换，cost = 0（字符相同）或 1（不同）
)
这个公式看着抽象，实际含义很直观。拿 dp[2][2] 举例，它要算 KI 变成 SI 的最小距离。
从三个方向来：
- 从 dp[1][2]（K→SI）加一次删除 K → KI→SI 实际上是 K→SI 已经算好了，再多删一个 K。不对等等，这解释得绕。
我换种更直白的理解方式：
你站在 dp[i][j] 这个格子往回看：
- 从上面来（dp[i-1][j]）：源字符串的前 i-1 个字符已经变成目标的前 j 个字符了，但源还有个多余字符，所以需要删除。花费 +1。
- 从左边来（dp[i][j-1]）：源的前 i 个字符已经变成目标的前 j-1 个字符了，目标还缺一个，所以需要插入。花费 +1。
- 从左上角来（dp[i-1][j-1]）：双方都少一个字符，如果当前字符相同，不需要操作（cost=0）；如果不同，就替换。花费 +1。
这样理解就好记了：上=删，左=插，左上=替。
又一个坑，大小写和空白字符
编辑距离算的是"字符是否相同"，但什么时候两个字符算"相同"？
在实际项目中，或许你也踩过这样的坑。
有人在代码里用 toLowerCase() 把两个字符串都转小写再去算 Levenshtein 距离。"Hello"和"hello"的编辑距离变成 0 了。但如果是文件名对比，大小写敏感的系统里这两个文件是不同文件。所以距离是不是应该算 1？没有标准答案，完全看你业务的场景。
空白字符。一个字符串是 "abc def"，另一个是 "abc def"（中间多了个空格）。Levenshtein 距离算出来是 1，因为多了一个空格。但用户在界面上根本看不出区别。这种情况在爬虫抓取数据对比时特别常见。
在计算距离之前，先把空白字符做规范化——连续多个空格合并成一个，去除首尾空格。但这只适用于"语义对比"，如果你需要做"精确对比"（比如 Git diff），就不应该做这种预处理。
在做文本对比的时候，先想清楚一个事：你到底是在对比"内容"还是对比"文本"？这两个概念不一样。对比内容，需要先标准化。对比文本，一个字都不能改。
工程优化，从 O(mn) 到 O(min(m,n))
标准的 Levenshtein 算法时间复杂度是 O(mn)，空间复杂度也是 O(mn)。对大文本来说，这个空间开销太大了。
一个 10000 字的文章，矩阵就有 1 亿个格子，每个格子存一个整数（4 字节），光是矩阵就占 400MB。这在浏览器里跑是不可能的。
优化的关键点在于：计算 dp[i][j] 只需要当前行和上一行的数据。更激进一点，只需要上一行和当前行的数据就够了。
function levenshtein(s, t) {
const m = s.length, n = t.length
// 保证 n 是较小的那个，减少空间
if (m < n) return levenshtein(t, s)
let prev = new Array(n + 1)
let curr = new Array(n + 1)
// 初始化第一行
for (let j = 0; j <= n; j++) prev[j] = j
for (let i = 1; i <= m; i++) {
curr[0] = i
for (let j = 1; j <= n; j++) {
const cost = s[i-1] === t[j-1] ? 0 : 1
curr[j] = Math.min(
prev[j] + 1,
curr[j-1] + 1,
prev[j-1] + cost
)
}
;[prev, curr] = [curr, prev]
}
return prev[n]
}
这段代码把空间复杂度降到了 O(min(m, n))。每次只保留两行数组，用完就交换。
第一次实现这个优化时，交换数组那里写的是 prev = curr; curr = new Array(n+1)，导致了内存泄漏——每次迭代都 new 一个新数组，旧的数组没有被及时回收。用解构交换引用是最干净的方式。
进一步，那个值 2 是怎么算出来的
Levenshtein 距离的定义听起来很客观，但实际应用时经常需要加"权重"。
比如拼音输入法的纠错场景：用户输入了"tian qi"，想打的是"天气"。如果你算"tian qi"到"天气"的编辑距离，这涉及到子串匹配问题，已经不是简单的 Levenshtein 能处理的了。
但有个简单一点的场景：用户输入了"teim"（他想打"time"）。"teim"到"time"的 Levenshtein 距离是 2——替换 e→i，再替换 i→e。但用键盘布局来看，这两个字母互换位置，更像是用户打反了。如果能检测到"相邻字符交换"也算一次操作就更合理了。
这就是 Damerau-Levenshtein 距离，在三种操作的基础上加了第四种：相邻字符互换（transposition）。大部分搜索引擎的 "Did you mean" 功能背后用的就是这个变体。
但别急着用 Damerau-Levenshtein。它有一个限制：你不能对一个字符先互换再修改。这个限制叫"互斥性条件"，具体就是同一个子串不能被多次编辑。实现时如果没注意这个条件，会出现一些反直觉的结果。
实际项目里的 Levenshtein
拼写建议。词典里几十万个词，对用户的输入逐个算 Levenshtein 距离不现实。优化的办法是用 BK 树（Burkhard-Keller Tree）做预筛选。建树的时候拿一个词做根，剩下的按与根的距离分到子节点。查询时设定最大距离，剪枝跳过大量无关词。实测能过滤掉 80% 以上的无关词。
剽窃检测。有人把一段话改几个词来规避查重。如果逐句对比，句子和句子之间的 Levenshtein 距离很小但又不完全相等。设定一个阈值（比如距离/句子长度 < 0.2），就能找出改动不大的"伪原创"。这个思路在学术不端检测系统里很常见。
数据库模糊匹配。拿来做用户输入的自定义校正。比如用户填地址时把"朝阳区"写成了"潮阳区"，距离为 1，系统自动纠错。代价是要维护一个标准地名词典。
代码 Diff 预览。比如文本对比工具就是基于 Levenshtein 距离的思路来做的，但做了两个重要改进。第一，行级别的 diff 用的是 Myers 算法，它在大部分实际场景下比标准 Levenshtein 快得多。第二，合并了连续相同行的区块，只显示有差异的部分。
写在最后说两个容易忽略的点
第一，Levenshtein 距离的三角不等式性质：distance(a, c) ≤ distance(a, b) + distance(b, c)。这个性质看起来像废话，但它是 BK 树能正常工作的数学基础。如果你自己魔改了 Levenshtein 距离（比如加了权重），先验证一下三角不等式还成立不成立。不成立的话，所有依赖这个性质的优化方案都会出 bug。
第二，Unicode 字符的处理。JavaScript 的字符串是 UTF-16 编码的。像 emoji "😂" 这样的字符在 JavaScript 里 length 是 2（它用两个 UTF-16 码元表示）。如果直接对字符串做 Levenshtein 计算，一个 emoji 会被当作两个字符处理，但它的"语义长度"应该是 1。解决方案是用 Array.from(str) 或者 [...str] 把字符串转成真实字符数组再计算。这个坑我修了两次才修彻底。
Levenshtein 距离的原理并不复杂，一个二维矩阵加上几个 min 就搞定了。但工程落地上有很多细节——空间优化、权重调整、Unicode 处理、搜索剪枝。理解这些之后，你自己也能根据业务场景定制合适的文本比较算法。