两个单词间的编辑距离 The distance between two words

目录

• The Levenshtein distance
• The LCS distance
• The Hamming distance
• The Damerau–Levenshtein distance
• The Jaro distance
• wiki百科里给了算edit distance的通用算法
• 参考

经常能见到，但是结论总是记不住，这里记录一下。
两个word间的距离有不同的定义方式，在NLP里可能有用
注意几点：
有的时候需要指明使用的alphabet(字母表)是什么
两个单词间的距离并不一定总是metric,因为：
两个单词间的距离一般来说都满足非负性
两个单词间的距离可能不是对称的，默认说成字符串str1到字符串str2的距离
3个单词间的距离可能不服从三角不等式

面向维基百科写博文/(ㄒoㄒ)/~~维基百科搬运工
这个API也很多，我猜mma或者R里有？
有时间我造个轮子

The Levenshtein distance 允许删除，插入和替换

EditDistance["abc",?"cba"](*mma*)

#?python版本
a=input()
b=input()
if?a==b:
????print("0")
else:????
????na=len(a)
????nb=len(b)
????dp=[[0?for?i?in?range(1005)]for?j?in?range(1005)]
????for?i?in?range(1,na+1):
????????dp[i][0]=i
????for?j?in?range(1,nb+1):
????????dp[0][j]=j
????for?i?in?range(1,na+1):
????????for?j?in?range(1,nb+1):
????????????if?a[i-1]==b[j-1]:
????????????????dp[i][j]=dp[i-1][j-1]
????????????else:
????????????????dp[i][j]=min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])+1
????print(dp[na][nb])

The LCS distance 允许插入和删除

(*mma*)
LCSDistance[str1_,?str2_]?:=?
?StringLength@str1?+?StringLength@str2?-?
??2*StringLength@LongestCommonSequence[str1,?str2]
LCSDistance["abcd",?"bd"]

The Hamming distance 只允许替换
和通信理论和信息论中见到的汉明距一致

#?python
a="abce"
b="abdf"
n=len(a)
m=len(b)
if?m!=n:
????????print("len(a)!=len(b)")
print(sum(int(a[i]!=b[i])?for?i?in?range(0,n)))

HammingDistance["abc",?"cba"](*mma*)

The Damerau–Levenshtein distance 允许删除，插入和替换，以及交换相邻元素

这里\(1_{\left(a_{i} \neq b_{j}\right)}\)是个指标函数

DamerauLevenshteinDistance["abc",?"cba"](*mma*)

或者叫做Jaro Similarity,归一化后为1表示完全匹配，为0表示完全不匹配

只允许交换相邻元素
算法如下

\[\operatorname{sim}_{j}=\left\{\begin{array}{ll} 0 & \text { if } m=0 \\frac{1}{3}\left(\frac{m}{\left|s_{1}\right|}+\frac{m}{\left|s_{2}\right|}+\frac{m-t}{m}\right) & \text { otherwise } \end{array}\right. \]

放弃造轮子X，我从RosettaCode里找了一份cpp代码
顺带一提，RosettaStone是埃及的那份罗赛塔石碑

//modified?from?https://rosettacode.org/wiki/Jaro_distance#C.2B.2B
#include#define?uint?unsigned?int
double?jaro(const?std::string?s1,?const?std::string?s2)?{
????const?uint?l1?=?s1.length(),?l2?=?s2.length();
????if?(l1?==?0)
????????return?l2?==?0???1.0?:?0.0;
????const?uint?match_distance?=?std::max(l1,?l2)?/?2?-?1;
????bool?s1_matches[l1];
????bool?s2_matches[l2];
????std::fill(s1_matches,?s1_matches?+?l1,?false);
????std::fill(s2_matches,?s2_matches?+?l2,?false);
????uint?matches?=?0;
????for?(uint?i?=?0;?i?<?l1;?i++)
????{
????????const?int?end?=?std::min(i?+?match_distance?+?1,?l2);
????????for?(int?k?=?std::max(0u,?i?-?match_distance);?k?<?end;?k++)
????????????if?(!s2_matches[k]?&&?s1[i]?==?s2[k])
????????????{
????????????????s1_matches[i]?=?true;
????????????????s2_matches[k]?=?true;
????????????????matches++;
????????????????break;
????????????}
????}
????if?(matches?==?0)
????????return?0.0;
????double?t?=?0.0;
????uint?k?=?0;
????for?(uint?i?=?0;?i?<?l1;?i++)
????????if?(s1_matches[i])
????????{
????????????while?(!s2_matches[k])?k++;
????????????if?(s1[i]?!=?s2[k])?t?+=?0.5;
????????????k++;
????????}
?
????const?double?m?=?matches;
????return?(m?/?l1?+?m?/?l2?+?(m?-?t)?/?m)?/?3.0;
}
?
int?main()?{
????using?namespace?std;
????cout?<<?jaro("MARTHA",?"MARHTA")?<<?endl;
????cout?<<?jaro("DIXON",?"DICKSONX")?<<?endl;
????cout?<<?jaro("JELLYFISH",?"SMELLYFISH")?<<?endl;
????return?0;
}
/*
0.944444
0.766667
0.896296
*/

Wagner-Fischer algorithm公式如下(实际是个很容易理解的dp)

这种算法的递归方程加上其他项还可以来处理允许交换相邻元素的场景

更多的距离和相似度测量可以看Wolfram的这个参考文档

两个单词间的编辑距离 The distance between two words

原文：https://blog.51cto.com/u_15247503/2866094