文本相似度Levenshtein算法原理(转载)

Levenshtein算法原理

1) str1或str2的长度为0返回另一个字符串的长度。 if(str1.length==0) return str2.length; if(str2.length==0) return str1.length;

2)初始化(n+1)*(m+1)的矩阵d，并让第一行和列的值从0开始增长。

3)扫描两字符串（n*m级的），如果：str1 == str2[j]，用temp记录它，为0。否则temp记为1。然后在矩阵d[i,j]赋于d[i-1,j]+1 、d[i,j-1]+1、d[i-1,j-1]+temp三者的最小值。

4)扫描完后，返回矩阵的最后一个值d[n][m]即是它们的距离。

Levenshtein计算相似度公式：1-它们的距离/两个字符串长度的最大值。

Levenshtein应用　　DNA分析/拼字检查/语音辨识/抄袭侦测

推导过程

为了直观表现，我将两个字符串分别写到行和列中，实际计算中不需要。我们用字符串“ivan1”和“ivan2”举例来看看矩阵中值的状况：

1、第一行和第一列的值从0开始增长

 

 最后得到它们的距离=1

相似度：1-1/Math.Max(“ivan1”.length,“ivan2”.length) =0.8

 

本文转自百度和网页 http://www.cnblogs.com/shihuajie/p/5772173.html 的作者无关，不对其内容负责。百度快照谨为网络故障时之索引，不代表被搜索网站的即时页面。