Edit Distance

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

用途

量化字符串间的差异程度，用于模糊匹配与纠错。

机制

通用框架：定义允许的操作集与代价，用动态规划求最小总代价。Levenshtein 允许插入/删除/替换（各代价 1）；Damerau-Levenshtein 额外允许相邻交换；Hamming 仅替换。

用例

拼写纠错
DNA 序列比对
OCR 错误纠正
模糊去重

示例

输入
```
cat → cut
```
输出
```
1 (substituting a→u)
```
Levenshtein

常见错误

Confusing different edit-distance variants: Make the operation set and costs explicit

相关词条

Levenshtein Distance

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

Hamming Distance

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

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

相关工具

汉明距离计算器

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

参考链接