此条目没有列出任何参考或来源。 (2014年8月19日) 维基百科所有的内容都应该可供查证。请协助补充可靠来源以改善这篇条目。无法查证的内容可能会因为异议提出而移除。 |
莱文斯坦距离,又称Levenshtein距离,是编辑距离的一种。指两个字串之间,由一个转成另一个所需的最少编辑操作次数。
允许的编辑操作包括:
- 将一个字符替换成另一个字符
- 插入一个字符
- 删除一个字符
俄罗斯科学家弗拉基米尔·莱文斯坦在1965年提出这个概念。
定义
如果分别用 和 表示 两个字符串的长度,那么它们的列文斯坦距离为 ,它符合:
-
是一个指示函数(indicator function),当 时,其值为0,其他时候它等于 1 。
表示 的前 个字符与 的前 个字符之间的列文斯坦距离。( 和 都是从1开始的下标)
注意:min运算中的第一个公式代表( 从 中)删除字符(以到达 );第二个公式代表插入字符;第三个代表替换(取决于当前字符是否相同)
例如
将“kitten”一字转成“sitting”的莱文斯坦距离为3:
- kitten → sitten (k→s)
- sitten → sittin (e→i)
- sittin → sitting (插入g)
应用
算法
动态规划经常被用来作为这个问题的解决手段之一。
int LevenshteinDistcance(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] = str1[j]
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, lenStr2]
参见