编辑距离

基本概念

编辑距离是从一个串变换到另一个串，需要的基础操作的数量，用来衡量两个串的相似度，用在

• 自然语言处理上，比如拼写检查；
• 生物学上，做 DNA 序列对比
• 其他

这里的基础操作包括：

• 插入一个字符
• 删除一个字符
• 替换一个字符（substitution）
• 交换两个字符（transposition）

编辑距离有：

莱文斯坦距离

Lavenshtein Distance，最常见的编辑距离，通常也会冠以“编辑距离”之名。

基本操作：

• 插入
• 删除
• 替换

达梅劳-莱文斯坦距离

Damerau-Lavenshtein Distance，莱文斯坦距离的变种，开始是用于拼写检查，补充了第四种基本的拼写错误，近邻序顺倒颠，但后来也推广用于衡量蛋白质序列间的变异。

基本操作：

• 插入
• 删除
• 替换
• （邻近）交换

LCS 距离：

最长公共子序列距离。

基本操作：

• 插入
• 删除

汉明距离

Hamming Distance，用于网络传输，作为学习网络传输都会了解到的流的校验码 。

基本操作：

• 替换

而且只允许同样长度的字符串。

哈罗距离

Jaro Distance，只允许交换两个字符。

DP 实现

这些编辑距离，特别是类似于莱文斯坦距离这样的编辑距离都有一个常规地运用 DP 概念的实现。

时间复杂度是 $O(nm)$ ，空间复杂度是 $O(\min(n,m))$ 。

具体参考 两串DP

注解