Levenshtein Distance

Levenshtein 距离是两字符串间通过插入、删除、替换单字符操作转为相同所需的最少操作数。

用途

度量字符串间编辑差异，用于模糊匹配与拼写纠错。

机制

动态规划：d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1]+cost)，cost 为 0 若字符相同否则 1。时间空间 O(m×n)，可优化空间至 O(min(m,n))。

用例

拼写检查与纠错
DNA 序列比对
模糊搜索与去重
自然语言处理

示例

输入
```
kitten → sitting
```
输出
```
3
```
Substitute k→s, e→i, and insert g

常见错误

Full O(mn) computation is too slow for long strings: Use a BK-tree or early termination by threshold

相关词条

Hamming Distance

Hamming 距离是等长字符串间对应位置不同字符的个数，仅适用于等长比较。

Jaro-Winkler Distance

Jaro-Winkler 距离是 Jaro 距离的改进，对公共前缀加权，更适合人名等前缀重要的短字符串匹配。

编辑距离是将一字符串转为另一字符串所需最少单字符编辑操作（插入、删除、替换）的数目，Levenshtein 距离为其最常用形式。

模糊搜索是容忍拼写差异的搜索技术，基于编辑距离、n-gram 或音标算法匹配近似结果。

相关工具

汉明距离计算器

Hamming Distance — 纯客户端工具。隐私优先，无服务器往返。

参考链接