编辑距离是针对二个字符串的差异程度的量化量测

常见分类及其定义

莱文斯坦距离

允许对一个字符串作任意次操作，每一次操作可以为删除、插入、替换字符串中的任何一个字元，求将该字符串编辑为另一个字符串最少的操作次数

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}

解释

(1)

表示在

a_{i-1}

后插入

b_{j}

(或删除

b_{j}

)情况下的最小操作次数

(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])

关于编辑距离

文章操作

常见分类及其定义

莱文斯坦距离

LCS（最长公共子序列）距离

算法

莱文斯坦距离

状态转移方程

解释

LCS（最长公共子序列）距离

状态转移方程

解释

实现

C++

Python

相关推荐

评论

关于编辑距离