简介
Levenshtein Distance是1965年由苏联数学家Vladimir Levenshtein发明的。Levenshtein Distance也被称为编辑距离(Edit Distance)。
在信息论和计算机科学中,Levenshtein Distance是一个度量两个字符序列之间差异的字符串度量标准,两个单词之间的Levenshtein Distance是将一个单词转换为另一个单词所需的单字符编辑(插入、删除或替换)的最小数量。
定义
对于两个字符串a, b
例子
1.kitten->sitten(用’s’取代‘k’)
2.sitten->sittin(用’i’取代’e’)
3.sittin->sitting(在末尾插入’g’)
因此距离为3
上下界
1.至少总是两个字符串大小的差值;
2.至多是较长字符串的长度;
3.当且仅当两个字符串相等时值为0;
4.如果两个字符串大小相等,汉明距离是其上界;
5.两个字符串的莱文斯坦距离不大于分别与第三个字符串的莱文斯坦距离之和(三角不等式)。
C++代码
包含递归与动态规划
动态规划矩阵示意图:
#include<iostream>
#include<vector>
#include<ctime>
using namespace std;
int min3(int a, int b, int c){
a = a < b ? a : b;
return a < c ? a : c;
}
int LevenshteinDis(string s, int s_len, string t, int t_len){
int cost;
if(s_len == 0)return t_len;
if(t_len == 0)return s_len;
if(s[s_len - 1] == t[t_len - 1])cost = 0;
else cost = 1;
return min3(LevenshteinDis(s, s_len - 1, t, t_len) + 1,
LevenshteinDis(s, s_len, t, t_len - 1) + 1,
LevenshteinDis(s, s_len - 1, t, t_len - 1) + cost);
}
int LevenshteinDP(string s, string t){
int dp[s.length()+1][t.length()+1];
for(int i = 0; i <= s.length(); i++)dp[i][0] = i;
for(int j = 1; j <= t.length(); j++)dp[0][j] = j;
for(int j = 0; j < t.length(); j++){
for(int i = 0; i < s.length(); i++){
if(s[i] == t[j])dp[i+1][j+1] = dp[i][j];
else dp[i+1][j+1] = min3(dp[i][j+1]+1, dp[i+1][j]+1, dp[i][j]+1);
}
}
return dp[s.length()][t.length()];
}
int main(){
string m = "kittesnsssdcjks";
string n = "sitdftingwcsdcc";
clock_t start,finish;
double totaltime;
start=clock();
cout<<"recursion: "<<LevenshteinDis(m, m.length(), n, n.length())<<endl;
finish=clock();
totaltime=(double)(finish-start)/CLOCKS_PER_SEC;
cout<<"递归运行时间为"<<totaltime<<"秒!"<<endl<<endl;
start=clock();
cout<<"Dynamic Programming: "<<LevenshteinDP(m, n)<<endl;
finish=clock();
totaltime=(double)(finish-start)/CLOCKS_PER_SEC;
cout<<"DP运行时间为"<<totaltime<<"秒!"<<endl<<endl;
return 0;
}
结果
更多内容访问
omegaxyz.com
网站所有代码采用Apache 2.0授权
网站文章采用知识共享许可协议BY-NC-SA4.0授权
© 2019 • OmegaXYZ-版权所有 转载请注明出处
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)