文章目录

• 1. 编辑距离的定义
• 2. 基于动态规划的求解算法
• • 2.1. 递推公式

1. 编辑距离的定义

编辑距离（Minimum Edit Distance，MED），由俄罗斯科学家 Vladimir Levenshtein 在1965年提出，也因此而得名 Levenshtein Distance。编辑距离一般用于度量两个序列相似程度的指标，具体来说，它计算的是一个序列A最少可以经过多少次操作变成另一个序列。这里的操作包括以下三种：

1. 插入（Insert）
2. 删除（Deletion）
3. 替换（Substitution）

比如字符串australia和austrian，后者可以由前者进行三次操作得到（2次删除，分别是a和l；一次插入，n）；字符串ABCDE和AFGE进行3次操作得到。

2. 基于动态规划的求解算法

2.1. 递推公式

对于两个字符串 a , b a,b a,b，记 f ( i , j ) f(i,j) f(i,j)为 a a a中前 i i i个字符与 b b b中前 j j j个字符的编辑距离，则有：
f ( i , j ) = { m a x ( i , j ) , i f   m i n ( i , j ) = 0 m i n { f ( i − 1 , j ) + 1 f ( i , j − 1 ) + 1 f ( i − 1 , j − 1 ) + 1 ( a i ≠ b j ) i f   m i n ( i , j ) ≠ 0 f(i,j)=\left\{ \begin{aligned} &max(i,j),&if\ min(i,j)=0 \\ &min { \left\{ \begin{aligned} &f(i-1,j)+1\\ &f(i,j-1)+1\\ &f(i-1,j-1)+1_{(a_i\neq b_j)} \end{aligned} \right. } &if\ min(i,j)\neq 0 \end{aligned} \right. f(i,j)=⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​​max(i,j),min⎩⎪⎨⎪⎧​​f(i−1,j)+1f(i,j−1)+1f(i−1,j−1)+1(ai​​=bj​)​​​if min(i,j)=0if min(i,j)​=0​