简介
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++代码
包含递归与动态规划
动态规划矩阵示意图：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#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; //基本情况，若字符串s和t的最小距离为0，则返回其中的最大距离作为编辑距离 if(s_len == 0)return t_len; if(t_len == 0)return s_len; //测试s和t的各自最后一个字符是否匹配 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){ //levenshtein距离的自底向上方式的动态规划实现，把重复计算的距离存入一个矩阵中 int dp[s.length()+1][t.length()+1];//d[i][j]表示字符串s的前i字符和t的前j个字符的莱文斯坦距离 for(int i = 0; i <= s.length(); i++)dp[i][0] = i;//源字符串s到空字符串t只要删除每个字符 for(int j = 1; j <= t.length(); j++)dp[0][j] = j;//从空字符s到目标字符t只要添加每个字符 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; } |
结果：
可以看到DP时间很快
参考资料
https://en.wikipedia.org/wiki/Levenshtein_distance
https://blog.csdn.net/lhkaikai/article/details/25186255
