编辑距离及编辑距离算法

leejan97 发布于2019-07-30 14:43 / 270人阅读

摘要：无意间看到了有人问编辑距离算法，当时对这个概念很陌生，也就去学习了下，做下总结，记录下，好记性不如烂笔头。编辑距离又称距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。

无意间看到了有人问编辑距离算法，当时对这个概念很陌生，也就去学习了下，做下总结，记录下，好记性不如烂笔头。

编辑距离（Edit Distance）：又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符，用数据库的说法就是改、增、删；一般来说就是字符串编辑距离离越小，两个串的相似度越大。

举个例子：S1=“eeba” S2="abac" 我们可以按照这样的步骤转变：

(1) 将S1中的第一个e变成a;

(2) 删除S1中的第二个e;

(3)在S1中最后添加一个c; 那么S1到S2的编辑路径就等于3。

当然，这种变换并不是唯一的，但如果3是所有变换中最小值的话。那么我们就可以说S1和S2的编辑距离等于3了。

听说这个概念是由俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念

概念的东西，说多了也只是理论，还是上代码吧！

先来份java的吧，这是我工作时用的第一个编程语言：

publicclassStringSimilar{

//编辑距离求串相似度

publicdoublegetStringSimilar(Strings1,Strings2){

double d[][];//matrix

int n;//lengthofs

int m;//lengthoft

int i;//iteratesthroughs

int j;//iteratesthrought

char s_i;//ithcharacterofs

char t_j;//jthcharacteroft

double cost;//cost

//第1步

n=s1.length();

m=s2.length();

if(n==0){

return m;

}

if(m==0){

return n;

}

d=new double[n+1][m+1];

//第2步

for(i=0;i<=n;i++){

d[i][0]=i;

}

for(j=0;j<=m;j++){

d[0][j]=j;

}

//第3步

for(i=1;i<=n;i++){

s_i=s1.charAt(i-1);

//第4步

for(j=1;j<=m;j++){

t_j=s2.charAt(j-1);

//第5步

if(s_i==t_j){cost=0;}else{cost=1;}

//第6步

d[i][j]=Minimum(d[i-1][j]+1,d[i][j-1]+1,d[i-1][j-1]+cost);

}

}

//第7步

return d[n][m];

}

//求最小值

privatedoubleMinimum(doublea,doubleb,doublec){

        double mi;

         mi=a;

        if(b
在来一份我最近学习的Python的
#!/user/bin/env python

# -*- coding: utf-8 -*-

class arithmetic():

    def __init__(self):

        pass

        def levenshtein(self,first,second):

        if len(first) > len(second):

                first,second = second,first

        if len(first) == 0:

                return len(second)

        if len(second) == 0:

                return len(first)

        first_length = len(first) + 1

        second_length = len(second) + 1

        distance_matrix = [range(second_length) for x in range(first_length)]

        for i in range(1,first_length):

            for j in range(1,second_length):

                 deletion = distance_matrix[i-1][j] + 1

                 insertion = distance_matrix[i][j-1] + 1

                 substitution = distance_matrix[i-1][j-1]

                 if first[i-1] != second[j-1]:

                     substitution += 1

                  distance_matrix[i][j] = min(insertion,deletion,substitution)

         print distance_matrix

         return distance_matrix[first_length-1][second_length-1]

if __name__ == "__main__":

    arith = arithmetic()

    print arith.levenshtein( "latino","larou"  )
吐槽下：Python语法缩进真是蛋疼，用4个空格缩进来确定。累的很啊
我的本行iOS的我就不上代码了，代码风格太菜同行到笑话就不好了。可以看出是动态规划解决编辑距离，明白算法原理写出算法函数方法还是不难的；大概的公式也就是：例S1=“eeba”  S2="abac"
如果i=0且j=0        edit(0, 0)=1

如果i=0且j>0        edit(0, j )=edit(0, j-1)+1

如果i>0且j=0        edit( i, 0 )=edit(i-1, 0)+1

如果i>0且j>0        edit(i, j)=min(edit(i-1, j)+1, edit(i,j-1)+1, edit(i-1,j-1)+f(i , j) )
这就是将长字符串间的编辑距离问题一步一步转换成短字符串间的编辑距离问题，直至只有1个字符的串间编辑距离为1

超融合服务器混合云编辑距离最大距离算法最小距离分类算法 java欧氏距离算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/40875.html

编辑距离及编辑距离算法

摘要：无意间看到了有人问编辑距离算法，当时对这个概念很陌生，也就去学习了下，做下总结，记录下，好记性不如烂笔头。编辑距离又称距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。无意间看到了有人问编辑距离算法，当时对这个概念很陌生，也就去学习了下，做下总结，记录下，好记性不如烂笔头。编辑距离（Edit Distance）：又称Levenshtein距离，是指两个字串之间，由一个...

zollero 2019-08-16 10:48 评论0 收藏0
文本相似度余弦值相似度算法 VS L氏编辑距离（动态规划）

摘要：本文对两种文本相似度算法进行比较。余弦值相似度算法最小编辑距离法氏编辑距离基于词条空间编辑距离，又称距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。但是同时也可以看出余弦相似度得到的结果相对比较高一些。本文由作者祝娜授权网易云社区发布。本文对两种文本相似度算法进行比较。余弦值相似度算法 VS 最小编辑距离法1、L氏编辑距离（基于词条空间）编辑距离（Edit Dist...

fxp 2019-06-28 11:05 评论0 收藏0
lucene的查询与排序

摘要：序本文主要记录一下的另外两个要点的使用查询与排序。在指定距离可以找到第一个单词的查询。查询的几个语句之间保持者一定的距离。同时查询几个词句查询。从一个词距查询结果中，去除一个词距查询。序本文主要记录一下lucene的另外两个要点的api使用：查询与排序。查询完全匹配查询 /** * 查找指定field中包含某个关键字 * @throws IOExcep...

baoxl 2019-08-14 15:14 评论0 收藏0
[转载] Python的字符串相似度检测

摘要：要求和必须长度一致。是描述由一个字串转化成另一个字串最少的操作次数，在其中的操作包括插入删除替换。计算距离，其中的为的匹配长度，当某位置的认为匹配当该位置字符相同，或者在不超过是调换次数的一半计算距离原文相似度计算转载自蔡尐的博客安装python-Levenshtein模块 pip install python-Levenshtein 使用python-Levens...

biaoxiaoduan 2019-07-31 11:38 评论0 收藏0
[Leetcode] Edit Distance 最小编辑距离

摘要：动态规划复杂度时间空间思路这是算法导论中经典的一道动态规划的题。 Edit Distance Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.) You h...

zhangke3016 2019-08-14 12:29 评论0 收藏0