精华内容
下载资源
问答
  • 编辑距离算法应用总结
    2020-04-06 16:10:50

      项目中应用了编辑距离算法解决问题,做个总结。作为业务团队的同学,平时应用算法解决问题的机会并不多,但是还是要有这个能力 / 思维,对技术架构 / 技术选型都有帮助,遇到算法资源不足的情况,也能顶上。编辑距离算法可以用于衡量文本相似度,进而解决文本的模糊搜索 / 匹配问题。编辑距离又叫 Levenshtein 距离(莱文斯坦距离),区别于汉明距离(等长字符串对应位置的不同字符的个数),不仅可以替换字符,还可以增删字符。算法时间复杂度是 O(m*n),如果文本数量(t)较大,遍历文本集合,计算关键字和文本 Pair 的编辑距离,再做 TOP_K 遴选,时间复杂度为 O(m*n*t + logt*t),当 t 较大时将会存在性能问题。这个性能问题的一种解法是将莱文斯坦距离降级为汉明距离,不考虑增减字符的情况,用利用 LSH 算法的思想进行分桶匹配,快速锁定一些桶,只匹配这些桶内的文本,也就是快速排除一些桶,减少匹配次数,从而提升速度。(LSH 算法的应用下次展开)。在我的项目中,文本数量在 1w 左右,并且我们通过边缘计算的方式化解服务器的负载压力,最终还是应用编辑距离算法解决我们业务的文本模糊匹配问题。

      编辑距离算法是个经典 DP (动态规划)问题。完美契合 DP 问题的两大特征,一是问题可分解为规模更小的子问题,二是子问题解之间存在推导关系。对于编辑距离求解问题,我们把 S1(长度 m ) 和 S2 (长度 n) 的编辑距离定义为 d(m, n),用 d(m-1, n) 表示 S1 的子串(移除最后一个字符)和 S2 之间的编辑距离,同理定义 d(m, n-1) 、d(m-1, n-1),那么问题解之间的推导关系为,d(m, n) = d(m-1, n-1) if S1[m-1] == S2[n-1],d(m, n) = min(d(m-1, n), d(m, n-1)) + 1 if S1[m-1] != S2[n-1]。基本原理就是这样。

      在实际应用的时候,我们一是对空间复杂度进行了优化(常规优化操作),二是微调算法满足业务需要的特定匹配规则。一,我们的直接反应会使用一个 m*n 的二维数据存储解空间,空间复杂度是 O(m*n),但仔细观察一下,在推导过程中,新一行的解只依赖上一行的解,意味着我们可以只存储上一行的解,空间复杂度可以降为 O(n)。二,在我们的项目中,S1 是一个段落,S2 是关键字,我们的编辑距离并不是严格意义上的编辑距离,严格来说,我们业务需要的是 S1 的连续子串和 S2 的编辑距离,(听起来问题复杂了好多),(业务含义是这个段落里是不是包含了疑似 S2 的子串)。理解起来,S1 的连续子串和 S2 的编辑距离,可以转化为 S1 向 S2 转化(编辑 / 匹配)的过程,S1 的前缀、后缀可以不参与匹配,或者说可以自由删除 S1 的前缀、后缀,而不增加编辑距离,这样的话,我们对算法的微调方法就出来了,1,初始化时,d(i, 0) = 0, 0 <= i < m,表示可以删除 S1 的前缀而不增加编辑距离,2,求解最终解时,取 min(d(i, n)), 0 <= i < m,表示可以删除 S1 的后缀而不增加编辑距离。

    更多相关内容
  • 该文介绍编辑距离算法的原理;通过该文,可学习编辑距离算法的相关知识,可进一步理解Elasticsearch中建议提示搜索中的计算模型!
  • 编辑距离算法,比较字符串相似度 pb11.5版本
  • 字符串的编辑距离,又称为levenshtein距离,是指利用字符操作,把字符串A转换成字符串B所需要的最少操作数,这里的操作包括删除、插入、修改。
  • 详解编辑距离算法-Levenshtein Distance

    万次阅读 多人点赞 2020-02-06 18:19:03
    编辑距离算法被数据科学家广泛应用,是用作机器翻译和语音识别评价标准的基本算法。最简单的方法是检查所有可能的编辑序列,从中找出最短的一条。但这个序列总数可能达到指数级,但完全不需要这么多,因为我们只要...

    目录

    •写在前面

    •什么是编辑距离?

    •思路

    •思路可视化

    •代码实现


    •写在前面

    编辑距离算法被数据科学家广泛应用,是用作机器翻译和语音识别评价标准的基本算法。最简单的方法是检查所有可能的编辑序列,从中找出最短的一条。但这个序列总数可能达到指数级,但完全不需要这么多,因为我们只要找到距离最短的那条而不是所有可能的序列。这个概念是由俄罗斯科学家Vladimir Levenshtein在1965年提出来的,所以也叫 Levenshtein 距离。总是比较相似的,或多或少我们可以考虑编辑距离。我们在解决这个问题中,使用动态规划的思想进行求解。

    •什么是编辑距离?

    这里给一个题目的描述:给定两个单词 word1 和 word2,计算出将 word1 转换成 word2 所使用的最少操作数 。你可以对一个单词进行如下三种操作。

    • 插入一个字符
    • 删除一个字符
    • 替换一个字符

    为了更好的理解,我这里给出两个示例,帮助理解这个概念

    示例一:

    输入: word1 = "horse", word2 = "ros"
    输出: 3
    解释: 
    horse -> rorse (将 'h' 替换为 'r')
    rorse -> rose (删除 'r')
    rose -> ros (删除 'e')

    示例二:

    输入: word1 = "intention", word2 = "execution"
    输出: 5
    解释: 
    intention -> inention (删除 't')
    inention -> enention (将 'i' 替换为 'e')
    enention -> exention (将 'n' 替换为 'x')
    exention -> exection (将 'n' 替换为 'c')
    exection -> execution (插入 'u')

    •思路

    我们的目的是让问题简单化,比如说两个单词 horse ros 计算他们之间的编辑距离 D,容易发现,如果把单词变短会让这个问题变得简单,很自然的想到用 D[n][m] 表示输入单词长度为 nm 的编辑距离。具体来说,D[ i ][ j ] 表示 word1 的前 i 个字母和 word2 的前 j 个字母之间的编辑距离。

    更通俗的理解,假设我们可以使用d[ i , j ]个步骤(可以使用一个二维数组保存这个值,使用动态规划的思想),表示将串s[ 1…i ] 转换为串t [ 1…j ]所需要的最少步骤个数,那么,在最基本的情况下,即在 i 等于 0 时,也就是说串 s 为空,那么对应的d[ 0 , j ] 就是 增加 j 个字符,使得 s 转化为 t,在 j 等于 0 时,也就是说串 t 为空,那么对应的 d[ i, 0] 就是 减少 i 个字符,使得 s 转化为 t

    更一般的情况,加一点动态规划的想法,我们要想得到将 s[1..i] 经过最少次数的增加,删除,或者替换操作就转变为 t[1..j],那么我们就必须在之前可以以最少次数的增加,删除,或者替换操作,使得现在串 s 和串 t 只需要再做一次操作或者不做就可以完成 s[1..i] == t[1..j] 的转换。所谓的“之前”分为下面三种情况:

    • 要得到 s[1…i] == t[1…j-1],需要 k 个操作
    • 要得到 s[1..i-1] == t[1..j],需要 k 个操作
    • 要得到 s[1…i-1] == t [1…j-1],需要 k 个操作

    在上面的这三种情况的基础下,我们需要得到 s[1..i] == t[1..j] ,我们分别给出解决思路,如下

    • 第1种情况,只需要在最后将 t[1…j-1] 加上 s[i] 就完成了匹配,这样总共就需要 k+1 个操作。
    • 第2种情况,只需要在最后将 s[1..i-1] 加上 t[j] 就完成了匹配,所以总共需要 k+1 个操作。
    • 第3种情况,只需要在最后将 s[ i ] 替换为 t[ j ],使得满足 s[1..i] == t[1..j],这样总共也需要 k+1 个操作。

    特别注意:而如果在第3种情况下,s[i]刚好等于t[j],那我们就可以仅仅使用k个操作就完成这个过程。

    最后,为了保证得到的操作次数总是最少的,我们可以从上面三种情况中选择消耗最少的一种最为将s[1..i]转换为t[1..j]所需要的最小操作次数。我们把储存k的二维数组命名为 D[ ][ ] ,显而易见,当我们获得 D[i-1][j]D[i][j-1] 和 D[i-1][j-1] 的值之后就可以计算出 D[i][j]

    如果两个子串的最后一个字母相同,即word1[i] = word2[i] 的情况下:

    D[i][j]=1+\min (D[i-1][j], D[i][j-1], D[i-1][j-1]-1)

    如果两个子串的最后一个字母不相同,即word1[i] != word2[i] 我们将考虑替换最后一个字符使得他们相同:

    D[i][j]=1+\min (D[i-1][j], D[i][j-1], D[i-1][j-1])

    •思路可视化

    在上面的思路描述下,我们大致能够理解了,当然,如果还是有点迷糊的,这里我将思路用表格一步一步的表示出来,帮助理解。首先我们先初始化一个二维数组,如下。“.” 代表空串。第一行和第一列按照个数进行初始化,这一步要想明白,想明白了之后就好理解了。

    如果两个子串的最后一个字母相同,即word1[i] = word2[i] 的情况下:

    D[i][j]=1+\min (D[i-1][j], D[i][j-1], D[i-1][j-1]-1),图形如下。

    如果两个子串的最后一个字母不相同,即word1[i] != word2[i] 我们将考虑替换最后一个字符使得他们相同:

    D[i][j]=1+\min (D[i-1][j], D[i][j-1], D[i-1][j-1]),图形如下。

    最后我们会得到如下的结果,二维数组最后的 3 就是我们的答案。

    •代码实现

    public int minDistance(String word1, String word2){
        int n = word1.length();
        int m = word2.length();
    
        if(n * m == 0)
            return n + m;
    
        int[][] d = new int[n + 1][m + 1];
        for (int i = 0; i < n + 1; i++){
            d[i][0] = i;
        }
    
        for (int j = 0; j < m + 1; j++){
                d[0][j] = j;
        }
    
        for (int i = 1; i < n + 1; i++){
            for (int j = 1; j < m + 1; j++){
                int left = d[i - 1][j] + 1;
                int down = d[i][j - 1] + 1;
                int left_down = d[i - 1][j - 1];
                if (word1.charAt(i - 1) != word2.charAt(j - 1))
                    left_down += 1;
                d[i][j] = Math.min(left, Math.min(down, left_down));
            }
        }
        return d[n][m];
    }

     

    展开全文
  • 易语言编辑距离算法

    2020-07-21 04:23:05
    易语言编辑距离算法源码,编辑距离算法
  • 编辑距离是一个标准的动态规划问题。 给定两个字符串 s1 和 s2,s1 和 s2 之间的编辑距离是将字符串 s1 转换为 s2 所需的最小操作次数。 通常使用以下操作: 用另一个字符替换字符串的一个字符。 从字符串中删除一个...
  • 易语言源码易语言编辑距离算法源码.rar 易语言源码易语言编辑距离算法源码.rar 易语言源码易语言编辑距离算法源码.rar 易语言源码易语言编辑距离算法源码.rar 易语言源码易语言编辑距离算法源码.rar 易语言源码...
  • NULL 博文链接:https://biansutao.iteye.com/blog/326008
  • 编辑距离算法详解和python代码

    千次阅读 2018-12-10 16:33:07
    最近做NLP用到了编辑距离,网上学习了很多,看到很多博客写的有问题,这里做一个编辑距离算法介绍,步骤和多种python代码实现,编辑距离有很多个定义,比如Levenshtein距离,LCS距离,汉明距离等,我们这里将...

    编辑距离(Levenshtein Distance)算法详解和python代码

    最近做NLP用到了编辑距离,网上学习了很多,看到很多博客写的有问题,这里做一个编辑距离的算法介绍,步骤和多种python代码实现,编辑距离有很多个定义,比如Levenshtein距离,LCS距离,汉明距离等,我们这里将Levenshtein距离默认为编辑距离。

    基本概念:

    编辑距离是指两个字符串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作仅包括删除、加入、取代字符串中的任何一个字符。
    它是由俄罗斯科学家Vladimir Levenshtein在1965年提出,中文名叫做莱文斯坦距离。
    例如将 jary 转为 jerry;

    1. jery (a→e)
    2. jerry(add r)

    主要思想

    假设我们可以使用d[i, j]个步骤(可以使用一个二维数组保存这个值),表示将字符串 s[ : i ] 转换为字符串 t[ : j ] 所需要的最少编辑操作次数,那么,考虑一个特殊情况,即在 i = 0,即s为空时,那么对应的d[0, j] 就是增加 j 个字符,使得 s 转化为 t;反之,在 j = 0,即t为空时,对应的d[i, 0] 就是减少 i 个字符,使得s转化为t。
    然后我们考虑一般情况,利用动态规划的思想,我们要想得到将 s[ : i ]经过最少次数的增加,删除,或者替换操作就转变为 t[ : j ],那么我们就必须在最后一步操作之前可以以最少次数的增加,删除,或者替换操作,使得现在 s 和 t 只需要再做一次操作或者不做就可以完全相等。
    根据动态规划和贝尔曼最优性原理,这里的"最后一步操作之前"指的是:

    1. 在k个操作内将 s[ : i ] 转换为 t[ : j-1 ]
    2. 在k个操作里面将 s[ : i-1 ] 转换为 t[ : j ]
    3. 在k个步骤里面将 s[ : i-1 ] 转换为 t[ : j -1]

    于是,与之对应的最后一步操作即为:

    1. 最后将 t[j] 加上s[ : i ]就完成了匹配,这样总共就需要 k+1 个操作
    2. 最后将 s[i] 移除,也完成了匹配,所以总共需要 k+1 个操作
    3. 最后将 s[i] 替换为 t[j],完成匹配,这样总共也需要 k+1个操作。而如果在第3种情况下,s[i ]刚好等于 t[j],那我 们就仅仅使用了k个操作就完成这个过程。

    所以现在问题变为:为了保证得到的操作总次数最少,我们需要从上面三种情况中选择消耗最少的一种。

    基本步骤

    1. 初始化行数为m+1 列数为 n+1 的矩阵 matrix, 用来保存完成某个转换需要执行的操作的次数,那么将 s[ 1 : n ] 变为t[ 1 : m ] 所需要执行的操作次数为matrix[n][m]的值;

    2. 初始化matrix第一行为0到n,第一列为0到m。Matrix[0][j]表示第1行第j+1列的值,这个值表示将串s[1 : 0]=[]转换为 t[1 : j] 所需要执行的操作的次数,很显然将一个空串转换为一个长度为 j 的串,只需要 j 次的add操作,所以matrix[0][j]的值应该是 j,其他值以此类推。

    3. 检查每个从1到n的 s[i] 字符;

    4. 检查每个从1到m的 t[j] 字符;

    5. 将串 s 和串 t 的每一个字符进行两两比较,如果相等,则让cost为0,如果不等,则让cost为1(这个cost后面会用到);

    6. a、如果我们可以在k个操作里面将s[1:i-1]转换为t[1:j],也就是说matrix[i-1,j]=k, 那么我们就可以将s[i]移除,然后再做这k个操作,所以总共需要k+1个操作。
      b、如果我们可以在k个操作内将 s[1:i] 转换为 t[1:j-1] ,也就是说matrix[i,j-1]=k,那么我们就可以将 t[j] 加上s[1:i],这样总共就需要k+1个操作。
      c、如果我们可以在k个步骤里面将 s[1:i-1] 转换为 t [1:j-1],那么我们就可以将s[i]转换为 t[j],使得满足s[1:i] == t[1:j],这样总共也需要k+1个操作。(这里需要加上cost,是因为如果s[i]刚好等于t[j],那么就不需要再做替换操作,即可满足,如果不等,则需要再做一次替换操作,那么就需要k+1次操作)
      因为我们要取得最小操作的个数,所以我们最后还需要将这三种情况的操作个数进行比较,取最小值作为matrix[ i , j ]的值;

    7. 然后重复执行3,4,5,6,最后的结果就在matrix[m,n]中;

    文字看的不清不楚没有关系,我们下面以图解解释下每一个步骤,还是以"jary" → "jerry"为例。

    图解如下

    步骤1:初始化矩阵如下:
    在这里插入图片描述
    步骤2:从源串"jary"的第一个字符"j"开始,自上而下与目标串"jerry"比较
    在这里插入图片描述
    如果两个字符相等,则cost = 0, 如果两个字符不相等,则cost = 1。
    当前值从此位置的 左+1,上+1和 左上+cost 三个值中取最小值。
    第一次,源串第一个字符“j” 与目标串的“j”对比,左+1,上+1,左上+cost三个值中取出最小的值0,因为两字符相等,所以加上0;接着,依次对比“j”→“e”,“j”→“r”,“j”→“r”,,“j”→“y” 到扫描完目标串。
    在这里插入图片描述
    步骤三:遍历整个源串与目标串每一个字符比较
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    步骤四:遍历完成,则matrix[m][n]即为所求编辑距离
    求出编辑距离后,可以计算两个字符串的相似度Similarity = 1 − L e v e n s h t e i n max ⁡ ( s , t ) 1-\frac{Levenshtein}{\max(s,t)} 1max(s,t)Levenshtein,其中s,t分别是源串和目标串的长度。

    代码实现

    1. 利用python的三方库Levenshtein,调用Levenshtein.distance(str1,str2)方法即可,这是内部调用c库,优化了算法结构的,比我们按照上面那个步骤写的代码快。
    2. 利用Numpy,DP,wiki上的代码 python_code.
    2.一个简单的代码,用python的list实现

    #!/usr/bin/env python
    # -*- coding: cp936 -*-
    def edit_distance(str1, str2):
    '''
            :type str1: str
            :type str2: str
            :rtype: int
    '''
        matrix = [[i+j for j in xrange(len(str2) + 1)] for i in xrange(len(str1) + 1)]
        for i in xrange(1,len(str1)+1):
            for j in xrange(1,len(str2)+1):
                if str1[i-1] == str2[j-1]:
                    d = 0
                else:
                    d = 1
                matrix[i][j] = min(matrix[i-1][j]+1,matrix[i][j-1]+1,matrix[i-1][j-1]+d)
        return matrix[len(str1)][len(str2)]
    

    参考文献

    展开全文
  • mt2.0基于编辑距离算法增量更新介绍 2014-06 about me 卢勇福 waynelu 提纲 l Mt1.0 chunk算法的问题 l 什么是编辑距离计算 l 编辑距离计算算法具体实现 l 在mt里面编辑距离计算算法 Mt1.0 chunk算法的问题 mt1.0...
  • 编辑距离的定义 编辑距离(Edit Distance)最常用的定义就是Levenstein距离,是由俄国科学家Vladimir Levenshtein于1965年提出的,所以编辑距离一般又称Levenshtein距离。它主要作用是测量两个字符串的差异化程度,...

    编辑距离的定义

    编辑距离(Edit Distance)最常用的定义就是Levenstein距离,是由俄国科学家Vladimir Levenshtein于1965年提出的,所以编辑距离一般又称Levenshtein距离。它主要作用是测量两个字符串的差异化程度,表示字符串a至少要经过多少个操作才能转换为字符串b,这里的操作包括三种:增加、删除、替换。

    举个例子:
    (1)增加:对于字符串a:abc 和 字符串b:abcde,显然,只需要在字符串a的末尾增加字符’d’和’e’就能变成字符串b了,所以a和b的最短编辑距离为2。
    (2)删除:对于字符串a:abcd 和字符串b:abc,显然,只需要在字符串a的末尾删除字符’d’就能变成字符串b了,所以a和b的最短编辑距离为1。
    (3)替换:对于字符串a:abcd 和 字符串b:abce,显然,只需要把字符串a的’d’替换成’e’就可以了,此时二者的最短编辑距离是1。

    一般字符串都是需要增加、删除、替换三者结合起来一起使用,因为字符串a到b可能存在多种变化的方法,而我们往往最关心的是最短的编辑距离,这样才能得出a和b的相似程度,最短编辑距离越小,表示a到b所需要的操作越少,a和b的相似度也就越高。因此,Levenstein距离的一个应用场景就是判断两个字符串的相似度,可以用在字符串的模糊搜索上面。

    Levenshtein 算法原理

    先从一个问题谈起:对于字符串"xyz"和"xcz",它们的最短距离是多少?我们从两个字符串的最后一个字符开始比较,它们都是’z’,是相同的,我们可以不用做任何操作,此时二者的距离实际上等于"xy"和"xc"的距离,即d(xyz,xcz) = d(xy,xc)。也即是说,如果在比较的过程中,遇到了相同的字符,那么二者的距离是除了这个相同字符之外剩下字符的距离。即d(i,j) = d(i - 1,j-1)。

    接着,我们把问题拓展一下,最后一个字符不相同的情况:字符串A(“xyzab”)和字符串B(“axyzc”),问至少经过多少步操作可以把A变成B。

    我们还是从两个字符串的最后一个字符来考察即’b’和’c’。显然二者不相同,那么我们有以下三种处理办法:
    (1)增加:在A末尾增加一个’c’,那么A变成了"xyzabc",B仍然是"axyzc",由于此时末尾字符相同了,那么就变成了比较"xyzab"和"axyz"的距离,即d(xyzab,axyzc) = d(xyzab,axyz) + 1。可以写成d(i,j) = d(i,j - 1) + 1。表示下次比较的字符串B的长度减少了1,而加1表示当前进行了一次字符的操作。

    (2)删除:删除A末尾的字符’b’,考察A剩下的部分与B的距离。即d(xyzab,axyzc) = d(xyza,axyzc) + 1。可以写成d(i,j) = d(i - 1,j) + 1。表示下次比较的字符串A的长度减少了1。

    (3)替换:把A末尾的字符替换成’c’,这样就与B的末尾字符一样了,那么接下来就要考察出了末尾’c’部分的字符,即d(xyzab,axyzc) = d(xyza,axyz) + 1。写成d(i,j) = d(i -1,j-1) + 1表示字符串A和B的长度均减少了1。

    由于我们要求的是最短的编辑距离,所以我们取以上三个步骤得出的距离的最小值为最短编辑距离。由上面的步骤可得,这是一个递归的过程,因为除掉最后一个字符之后,剩下的字符串的最后一位仍然是最后一个字符,我们仍然可以按照上面的三种操作来进行,经过这样的不断递归,直到比较到第一个字符为止,递归结束。

    按照以上思路,我们很容易写出下面的方程:
    最短编辑距离方程
    注释:该方程的第一个条件min(i,j) = 0,表示若某一字符串为空,转换成另一个字符串所需的操作次数,显然,就是另一个字符串的长度(添加length个字符就能转换)。这个条件可以看成是递归的出口条件,此时i或j减到了0。

    根据以上方程,我们能快速写出递归代码,但由于递归包含了大量的重复计算,并且如果初始字符串过长,会造成递归层次过深,容易造成栈溢出的问题,所以我们这里可以用***动态规划***来实现。**如果说递归是自顶向下的运算过程,那么动态规划就是自底向上的过程。**它从i和j的最小值开始,不断地增大i和j,同时对于一个i和j都会算出当前地最短距离,因为下一个i和j的距离会与当前的有关,所以通过一个数组来保存每一步的运算结果来避免重复的计算过程,当i和j增加到最大值length时,结果也就出来了,即d[length][length]为A、B的最短编辑距离。

    动态规划中,i和j的增加需要两层循环来完成,外层循环遍历i,内层循环遍历j,也即是,对于每一行,会扫描行内的每一列的元素进行运算。因此,时间复杂度为o(n²),空间复杂度为o(n²)。

    图解动态规划求最短编辑距离过程

    在写代码之前,为了让读者对动态规划有一个直观的感受,笔者以表格的形式,列出动态规划是如何一步步地工作的。
    下面以字符串"xyzab"和"axyzc"为例来讲解。
    在这里插入图片描述
    在这里插入图片描述

    由上面可以看出,动态规划就是逐行逐列地运算,逐渐填满整个数组,最后得到结果恰好保存在数组的最后一行和最后一列的元素上。

    代码实现

    一、基本实现

    public class LevenshteinDistance {
    
        private static int minimum(int a,int b,int c){
            return Math.min(Math.min(a,b),c);
        }
    
        public static int computeLevenshteinDistance(CharSequence src,CharSequence dst){
            int[][] distance = new int[src.length() + 1][dst.length() + 1];
    
            for (int i = 0;i <= src.length();i++)
                distance[i][0] = i;
            for (int j = 0;j <= dst.length();j++)
                distance[0][j] = j;
    
            for (int i = 1;i <= src.length();i++){
                for (int j = 1;j <= dst.length();j++){
                    int flag = (src.charAt(i - 1) == dst.charAt(j - 1)) ? 0 : 1;
                    distance[i][j] = minimum(
                            distance[i - 1][j] + 1,
                            distance[i][j - 1] + 1,
                            distance[i - 1][j - 1] + flag);
                }
            }
            return distance[src.length()][dst.length()];
        }
    
        //测试方法
        public static void main(String args[]){
            String s1 = "xyzab";
            String s2 = "axyzc";
    
            String s3 = "等啊高原";
            String s4 = "阿登高原";
    
            String s5 = "xyz阿登高原";
            String s6 = "1y3等啊高原x";
    
            System.out.println("字符串(\"" + s1 + "\")和字符串(\"" + s2 + "\")的最小编辑距离为:"+ computeLevenshteinDistance(s1,s2));
            System.out.println("字符串(\"" + s3 + "\")和字符串(\"" + s4 + "\")的最小编辑距离为:"+ computeLevenshteinDistance(s3,s4));
            System.out.println("字符串(\"" + s5 + "\")和字符串(\"" + s6 + "\")的最小编辑距离为:"+ computeLevenshteinDistance(s5,s6));
    
        }
    }
    

    上面的代码是利用了动态规划的思想来实现的最短编辑距离算法,它的实现与原理方程基本上是一致的,都是先对第一行和第一列的数据进行初始化,然后开始逐行逐列进行计算,填充满整个数组,即自底向上的思想,通过这样减少了大量的递归重复计算,实现了运算速度的提升。上面提到,这种实现的时间复杂度和空间复杂度都是n²级别的(实际上是m×n,两个字符串长度的乘积)。实际上,我们可以对代码进行优化,降低空间复杂度。

    二、利用滚动数组进行空间复杂度的优化
    滚动数组是动态规划中一种常见的优化思想。为了理解滚动数组的思想,我们先来看看如何进行空间复杂度的优化。回到原理方程,我们可以观察到d(i,j)只与上一行的元素d(i-1,j)、d(i,j-1)和d(i-1,j-1)有关,而上一行之前的元素没有关系,也就是说,对于某一行的d(i,j),我们只需要知道上一行的数据就行,别的数据都是无效数据。实际上,我们只需要两行的数组就可以了。

    举个例子:还是上面的"xyzab"和"axyzc",当我们计算完第一行和第二行的数据后,到达第三行时,我们以第二行为上一行结果来计算,并把计算结果放到第一行内;到达第四行时,由于第三行的数据实际上保存在第一行,所以我们根据第一行来计算,把结果保存在第二行……以此类推,直到计算到最后一行,即不断交替使用两行数组的空间,“滚动数组”也因此得名。通过使用滚动数组的形式,我们不需要n×m的空间,只需要2×min(n,m)的空间,这样便能把空间复杂度降到线性范围内,节省了大量的空间。

    利用滚动数组后的空间复杂度为o(2×n)或者o(2×m),这取决于代码的实现,即取字符串A还是B的长度为数组的列数。(因为无论把哪一个字符串作为src或dst,都是等价的,结果都是一样的。)其实我们可以通过判断A、B的长度,来选取一个最小值作为列数,此时空间复杂度变为o(2×min(n,m))。下面给出基于滚动数组的最小编辑距离的优化版本,由Java实现。

    /**
         *  利用滚动数组优化过的最小编辑距离算法。空间复杂度为O(2×min(lenSrc,lenDst))
         * @param src 动态规划数组的行元素
         * @param dst 动态规划数组的列元素
         * @return
         */
        public static int computeLevenshteinDistance_Optimized(CharSequence src,CharSequence dst){
            int lenSrc = src.length() + 1;
            int lenDst = dst.length() + 1;
    
            CharSequence newSrc = src;
            CharSequence newDst = dst;
            //如果src长度比dst的短,表示数组的列数更多,此时我们
            //交换二者的位置,使得数组的列数变为较小的值。
            if (lenSrc < lenDst){
                newSrc = dst;
                newDst = src;
                int temp = lenDst;
                lenDst = lenSrc;
                lenSrc = temp;
            }
    
            //创建滚动数组,此时列数为lenDst,是最小的
            int[] cost = new int[lenDst];   //当前行依赖的上一行数据
            int[] newCost = new int[lenDst];//当前行正在修改的数据
    
            //对第一行进行初始化
            for(int i = 0;i < lenDst;i++)
                cost[i] = i;
    
            for(int i = 1;i < lenSrc;i++){
                //对第一列进行初始化
                newCost[0] = i;
    
                for(int j = 1;j < lenDst;j++){
                    int flag = (newDst.charAt(j - 1) == newSrc.charAt(i - 1)) ? 0 : 1;
    
                    int cost_insert = cost[j] + 1;        //表示“上面”的数据,即对应d(i - 1,j)
                    int cost_replace = cost[j - 1] + flag;//表示“左上方的数据”,即对应d(i - 1,j - 1)
                    int cost_delete = newCost[j - 1] + 1; //表示“左边的数据”,对应d(i,j - 1)
    
                    newCost[j] = minimum(cost_insert,cost_replace,cost_delete); //对应d(i,j)
                }
    
                //把当前行的数据交换到上一行内
                int[] temp = cost;
                cost = newCost;
                newCost = temp;
            }
    
            return cost[lenDst - 1];
        }
    

    把main()方法的方法调用改为上述方法,比较前后两个方法的输出结果,结果一致,符合预期。
    输出结果

    三、对空间复杂度的进一步优化
    实际上,我们还能对这个进行进一步的优化,把空间复杂度减少为o(min(n,m)),即我们只需要一行的数组d加一个额外的临时变量就可以实现。比如说我们要修改d[i]的值时,只需知道它的左边、上边和左上方的元素的值,而左边的值就是d[i-1],上边的值是修改之前的d[i],左上方的值是d[i-1]修改之前的值。每一次需要修改d[i-1]的时候,都用临时变量把他保存起来,这样i位置就能直接获取这三个值进行比较,得到结果之后,先用这个临时变量把d[i]保存起来,然后再写入d[i]内,……以此类推,直到遍历完一行。

    其核心思想是:把求得的数据,再次写回这一行数据对应下标元素的位置,而临时变量temp则保存当前位置左上方元素的值,以提供给下一个位置的计算。总的来说,数据的操作只集中在一行之内,所以空间复杂度就是o(n)。

    下面以图解的形式表达这一过程,方便读者理解。
    单行数组
    代码实现也不复杂,有兴趣的同学可以根据上图或者思路来实现,这里就不再实现了。

    好了,这篇文章写到这里就结束了,希望能对各位同学有所裨益,谢谢你们的耐心阅读~

    展开全文
  • 编辑距离算法-易语言.zip
  • 文本相似度算法之编辑距离算法

    千次阅读 2019-03-13 08:42:59
    编辑距离又称Leveinshtein距离,是由俄罗斯科学家Vladimir Levenshtein在1965年提出。 以字符串为例,字符串a和字符串b的编辑距离是将a转换成b的最小操作次数,这里的操作包括三种: 插入一个字符 删除一个字符 替换...
  • 编辑距离(Edit Distance),又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。 例如将kitten一字转...
  • 易语言验证码编辑距离算法源码
  • 编辑距离算法: 图解过程: C++代码如下: 总结: 背景: 我们在使用词典app时,有没有发现即使输错几个字母,app依然能给我们推荐出想要的单词,非常智能。它是怎么找出我们想要的单词的呢?这里就需要BK...
  • 易语言编辑距离算法源码
  • 最小编辑距离算法及python实现

    千次阅读 2018-10-22 15:01:29
    对于最小编辑距离算法的理解: 1,一个字符串转化到另一个字符串的最少操作次数 2,操作有三种:增加,删除,替换。 3,它是一个不断最小取值的过程(每一步都是最小取值,至最后理所当然最少操作次数)PS:算法...
  • 编辑距离算法的优化与实现.doc
  • 最小编辑距离算法

    千次阅读 2019-06-23 11:37:45
    最小编辑距离算法 简介: 通俗地来讲,编辑距离指的是在两个单词<w_1,w_2>之间,由其中一个单词w_1转换为另一个单词w_2所需要的最少单字符编辑操作次数。 定义的单字符编辑操作有三种, 每种操作的权重为1...
  • 最小编辑距离算法 Edit Distance(经典DP)

    万次阅读 多人点赞 2018-05-23 11:36:32
    编辑距离(Edit Distance),又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。一般来说,编辑距离越...
  • pyxDamerauLevenshtein在Cython中为Python实现了Damerau-Levenshtein(DL)编辑距离算法,以实现高性能。 礼貌: 在信息论和计算机科学中,Damerau-Levenshtein距离(以Frederick J. Damerau和Vladimir I. ...
  • 这个想法类似于字符串之间的编辑距离,实际上,字符串之间的编辑距离是该算法的特例。 在计算字符串之间的编辑距离时,需要计算字符插入,删除和重新标记的最小数量,以将一个字符串转换为另一个字符串。 转到此处...
  • fasta算法,Smith-waterman算法,编辑距离算法,最长公共子串算法
  • Levenshtein Distance算法,又叫Edit Distance算法...一般来说,编辑距离越小,两个串的相似度越大。    算法基本原理:假设我们可以使用d[i,j]个步骤(可以用一个二维数组保存这个值),表示将串 s[1...i]转换...
  • 字符串相似度算法(编辑距离算法)

    千次阅读 2019-04-24 20:56:13
    编辑距离算法前言原理实现 前言 有时候 原理 实现
  • python实现编辑距离算法

    千次阅读 2017-12-27 20:24:36
    原文章链接:python实现计算最小编辑距离 最小编辑距离或莱文斯坦距离(Levenshtein),指由字符串A转化为字符串B的最小编辑次数。允许的编辑操作有:删除,插入,替换。具体内容可参见:Wikipedia - Levenshtein_...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 41,903
精华内容 16,761
关键字:

编辑距离算法

友情链接: 捕捉点快捷键.rar