响应realazy的号召努力学习算法中。 这个莱文斯坦算法(Levenshtein Distance)还是比较好理解而且很实用的，放在这里做个备份吧。

原文请见 http://www.merriampark.com/ld.htm 。

什么是莱文斯坦距离？

莱文斯坦距离(LD)用于衡量两个字符串之间的相似度。 以下我们称这两个字符串分别为 s (原字符串) 和 t (目标字符串)。莱文斯坦距离被定义为’‘将字符串 s 变换为字符串 t 所需的删除、插入、替换操作的次数’‘。

例如：

• s=”test”, t=”test”, 那么 LD(s,t)=0，因为不需要做任何变换两者已相等；
• s=”test”, t=”tent”, 那么 LD(s,t)=1，因为s变换为t只需做一次替换(将”s”替换为”n”)。

莱文斯坦距离越大，字符串的相似程度越低。

莱文斯坦距离以俄国科学家Vladimir Levenshtein命名，他于1965年发明了这个算法。 如果你对Levenshtein这个词的发音有问题，也可以称这个距离为编辑距离。

莱文斯坦距离被应用于以下领域：

• 拼写检查
• 语音识别
• DNA分析
• 剽窃检测

算法

1. 设 s 的长度为 n，t 的长度为 m。如果 n = 0，则返回 m 并退出；如果 m=0，则返回 n 并退出。否则构建一个数组 d[0..m, 0..n]。
2. 将第0行初始化为 0..n，第0列初始化为0..m。
3. 依次检查 s 的每个字母(i=1..n)。
4. 依次检查 t 的每个字母(j=1..m)。
5. 如果 s[i]=t[j]，则 cost=0；如果 s[i]!=t[j]，则 cost=1。
6. 将 d[i,j] 设置为以下三个值中的最小值：
7. 紧邻当前格上方的格的值加一，即 d[i-1,j]+1
8. 紧邻当前格左方的格的值加一，即 d[i,j-1]+1
9. 当前格左上方的格的值加cost，即 d[i-1,j-1]+cost
10. 重复3-6步直到循环结束。d[n,m]即为莱茵斯坦距离。

代码

代码请参考原文网站。 该网站给出了 Java、C++、Visual Basic三种语言的实现， 又在页面最下方的链接中给出了Perl、PL/SQL、TSQL、C#、Delphi、PHP 等数十种语言的实现方式。

所以我在这里就不献丑啦～。