莱文斯坦距离(英語:Levenshtein distance)是编辑距离的一种。指两个字串之間,由一个转成另一个所需的最少编辑操作次数。
允许的编辑操作包括:
- 将一个字符替换成另一个字符
- 插入一个字符
- 刪除一个字符
俄羅斯科學家弗拉基米尔·莱文斯坦在1965年提出這個概念[1][2]。
定义
如果分别用 和 表示 两个字符串的长度,那么它们的列文斯坦距离为 ,它符合:
是一个指示函数(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]
參見
参考文献