Levenshtein编辑距离C++实现

简介

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++代码

包含递归与动态规划

动态规划矩阵示意图:

结果:

可以看到DP时间很快


参考资料

https://en.wikipedia.org/wiki/Levenshtein_distance

https://blog.csdn.net/lhkaikai/article/details/25186255

 

留下评论

您的电子邮箱地址不会被公开。 必填项已用*标注