700字范文,内容丰富有趣,生活中的好帮手!
700字范文 > 【动态规划】字符串编辑距离(Levenshtein距离)算法

【动态规划】字符串编辑距离(Levenshtein距离)算法

时间:2020-02-10 18:41:52

相关推荐

【动态规划】字符串编辑距离(Levenshtein距离)算法

概述

Levenshtein Distance是一个度量两个字符序列之间差异的字符串度量标准,两个单词之间的Levenshtein Distance是将一个单词转换为另一个单词所需的单字符编辑(插入、删除或替换)的最小数量。Levenshtein Distance是1965年由苏联数学家Vladimir Levenshtein发明的。Levenshtein Distance也被称为编辑距离(Edit Distance)。

定义

对于两个字符串、,长度分别为、,它们的Levenshtein Distance 为:

其中当时,为0,否则为1。就是的前个字符与的前个字符的编辑距离。

、的相似度为。

原理

首先考虑极端情况,当或长度为0时,那么需要编辑的次数就是里一个字符串的长度。

然后再考虑一般情况,此时分为三种情况:

在k个操作中,将a[1...i]转换为b[1...j-1]

在k个操作中,将a[1...i-1]转换为b[1...j]

在k个操作中,将a[1...i-1]转换为b[1...j-1]

针对第一种情况,只需要在a[1...i]后加上字符b[j],即可完成a[1..i]到b[1...j]的转换,总共需要的编辑次数即为k+1。

针对第二种情况,只需要在a[i]字符从a中移除,即可完成a[1..i]到b[1...j]的转换,总共需要的编辑次数即为k+1。

针对第三种情况,只需要将a[i]转换为b[j],即可完成a[1..i]到b[1...j]的转换,如果a[i]与b[i]的字符相同,则总共需要的编辑次数为k,否则即为k+1。

所以上述三种情况分别对应于插入、删除、替换操作。

为了保证将a[1..i]转换为b[1..j]的操作数总是最少的,只需要从三种情况中选择操作次数最少的情况,同理为了保证三种情况的操作数也是最小的,只需要按此逻辑进行迭代保证每一步的操作数都是最小的即可。

示例

为方便理解,以字符串:abroad和:aboard为例,将求值过程中每一步的操作数放入一个i+1行j+1列的二维数组中, 即为将a[1..i]转换为b[1...j]所需要的最少的操作数。

1.首先是极端情况,即d[0][j]、d[i][0]即a为空字符串或b为空字符串时,需要操作的次数即为另一字符串的长度。

2.然后是一般情况,即d[i][j]的值,遍历这个二维数组,从第一行开始直到最后一行,由定义可知d[i][j]的值为d[i-1][j]+1、d[i][j-1]+1以及d[i-1][j-1]+1(如果a[i]==b[j])的最小值。即根据d[i][j]所在位置的正上方(d[i-1][j])、左方以(d[i-1][j])及左上方(d[i-1][j-1])的值计算出d[i][j]的值,由此得到二维数组中所有元素的值。

3.最后的d[i][j]即为字符串a转换为b的最少操作数。

求值过程如下图:

Levenshtein Distance

如图字符串、的Levenshtein Distance 为2,相似度为:

代码:

#include <bits/stdc++.h>#define max(x,y) (x>y?x:y)#define min(x,y) (x<y?x:y)using namespace std;char a[1005],b[1005];int f[1005][1005],n,m;int main(){scanf("%s%s",a+1,b+1);n=strlen(a+1);m=strlen(b+1);int w=max(n,m);for(int i=1;i<=w;++i)f[i][0]=f[0][i]=i;for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){if(a[i]==b[j])f[i][j]=f[i-1][j-1];else f[i][j]=min(f[i][j-1],min(f[i-1][j],f[i-1][j-1]))+1;}}printf("%d",f[n][m]);return 0;} --------------------- 原文:/jmsyzsfq/article/details/78369002

---------------------

原文:/asty9000/article/details/81384650

版权声明:本文为博主原创文章,转载请附上博文链接!

本内容不代表本网观点和政治立场,如有侵犯你的权益请联系我们处理。
网友评论
网友评论仅供其表达个人看法,并不表明网站立场。