关于编辑距离
limingzhe
·
·
算法·理论
编辑距离是针对二个字符串的差异程度的量化量测
常见分类及其定义
莱文斯坦距离
允许对一个字符串作任意次操作，每一次操作可以为删除、插入、替换字符串中的任何一个字元，求将该字符串编辑为另一个字符串最少的操作次数
LCS（最长公共子序列）距离
允许对一个字符串作任意次操作，每一次操作可以为删除、插入字符串中的任何一个字元，求将该字符串编辑为另一个字符串最少的操作次数
算法
莱文斯坦距离
考虑使用动态规划
定义两字符串分别为 a, b ，其第 i 个字符分别为 a_i, b_i ，长度分别为 |a|, |b| 。
定义 lev_{a,b}(i, j) 为 a 的前 i 个字符与 b 的前 j 个字符的编辑距离。
状态转移方程
lev_{a,b}(i, j)=\begin{cases}
max(i, j) & min(i, j)=0 \\
min \begin{cases}
lev_{a,b}(i-1, j)+1 & (1)\\
lev_{a,b}(i, j-1)+1 & (2)\\
lev_{a,b}(i-1, j-1)+\begin{cases}0 & i=j\\1 & i \ne j\end{cases} & (3)
\end{cases} & otherwise
\end{cases}
解释
$(2)$ 表示在 $b_{i-1}$ 后插入 $a_{j}$ (或删除 $a_{j}$)情况下的最小操作次数
$(3)$ 表示将 $b_{j}$ 替换为 $a_{i}$ 情况下及 $a_{i} = b_{j}$ 时不做处理的最小操作次数
## LCS（最长公共子序列）距离
### 状态转移方程
$$$
lev_{a,b}(i, j)=\begin{cases}
max(i, j) & min(i, j)=0 \\
min \begin{cases}
lev_{a,b}(i-1, j)+1 \\
lev_{a,b}(i, j-1)+1 \\
lev_{a,b}(i-1, j-1)+\begin{cases}0 & i=j\\2 & i \ne j\end{cases}
\end{cases} & otherwise
\end{cases}
$$$
### 解释
在LCS距离中，替换操作相当于一次插入操作和一次删除操作
# 实现
## C++
```cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
string a, b;
cin >> a >> b;
int la=a.size(), lb=b.size();
int lev[2005][2005];
for(int i=0;i<=la;i++)lev[i][0]=i;
for(int j=0;j<=lb;j++)lev[0][j]=j;
for(int i=1;i<=la;i++){
for(int j=1;j<=lb;j++){
lev[i][j]=min(min(lev[i-1][j]+1, lev[i][j-1]+1), lev[i-1][j-1]+(a[i-1]!=b[j-1]));//莱文斯坦距离
//lev[i][j]=min(min(lev[i-1][j]+1, lev[i][j-1]+1), lev[i-1][j-1]+2*(a[i-1]!=b[j-1]));//LCA距离
}
}cout << lev[la][lb];
}
```
## Python
```python
a=input()
b=input()
dp=[[0]*(len(b)+1) for i in range(len(a)+1)]
for i in range(len(a)+1):
for j in range(len(b)+1):
if min(i, j)==0:
dp[i][j]=max(i, j)
else:
dp[i][j]=min(
dp[i-1][j]+1,
dp[i][j-1]+1,
dp[i-1][j-1]+int(a[i-1]!=b[j-1])*2
)
print(dp[-1][-1])
```