同义词levenshtein（两个字符串之间的距离）一般指莱文斯坦距离
- 中文名
- 莱文斯坦距离
- 外文名
- Levenshtein distance
莱文斯坦距离(LD)用于衡量两个字符串之间的相似度。 以下我们称这两个字符串分别为
莱文斯坦距离以俄国科学家Vladimir levenshtein命名，他于1965年发明了这个算法。 如果你对Levensht催厚ein酷企遥颂谅应这个词的发音有问题，也可以称这个距离为编辑距离。
在数学上，两个字符串a,b的莱文斯坦距离记作
这里，
莱文斯坦距离有一些简单的上下界，如 [1]
：
- 莱文斯坦距离至少是两个字符串长度的差值
- 莱文斯坦距离不大于较大的那个字符串的长度
- 如果两个字符串相等，那么它们的莱文斯坦距离为0
- 如果两个字符串等长，那么它们的汉明距离是莱文斯坦距离的上界
- 两字符串的莱文斯坦距离不大于它们与第三个字符串的莱文斯坦距离之和（三角性）
动态规划经常被用来作为这个问题的解决手段之一。
int LevenshteinDistance(string str1[1..lenStr1], string str2[1..lenStr2])
int d[0..lenStr1, 0..lenStr2]
int i, j, cost
for i = 0 to lenStr2
d[i, 0] := i
for j = 0 to lenStr1
d[0, j] := j
for i = 1 to lenStr2
for j = 1 to lenStr1
if str2[i-1] = str1[j-1]
cost := 0
else
cost := 1
d[i, j] := min(
d[i-1, j ] + 1, // 删除
d[i , j-1] + 1, // 插入
d[i-1, j-1] + cost // 替换
)
return d[lenStr1-1, lenStr2-1]
