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

81 阅读 0 评论 54 点赞

我是靠谱客的博主酷酷鞋子，最近开发中收集的这篇文章主要介绍文本相似度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 的作者无关，不对其内容负责。百度快照谨为网络故障时之索引，不代表被搜索网站的即时页面。

以上就是酷酷鞋子为你收集整理的文本相似度Levenshtein算法原理(转载)的全部内容，希望文章能够帮你解决文本相似度Levenshtein算法原理(转载)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。