React-虚拟dom-diff算法，Levenshtein Distance最小编辑距离

太过爱你忘了你带给我的痛 2021-06-10 20:40 453阅读 0赞

Levenshtein Distance是最小编辑距离的一种实现，网上搜到的一些python的实现，现在用前端的JavaScript来实现一下。什么是最小编辑距离？请看[斯坦福的课件][Link 1]。简单地说就是将string1变成string2需要的最少步骤。

例如string1是abc，sting2是123abc。把string1变成string2的最小编辑距离是3，即新增1，新增2，新增3。

例如string1是abc，string2是abd。把string1变成string2的最小编辑距离是1，即c替换成d。（也有的将其计算成2，先删除c，再新增d，因此是要编辑2次）。

用Levenshtein Distance来实现最小编辑距离的算法逻辑见图：

![98fae789c9d72522d44f722b3ee6966a.png][]

核心思想是用二维数组记录每次计算的值，核心技巧当然还是递归。D(i-1, j) + 1代表将算法思想转化成：将string1去掉末尾一个字符后，变成string2的最小编辑距离是多少。最终不管值是多少，还需要加1，因为之前去掉了一个字符。

同理D(i, j-1) + 1代表将算法思想转化成：将string2去掉末尾一个字符后，变成string1的最小编辑距离是多少。最终不管值是多少，还需要加1，因为之前去掉了一个字符。

D(i-1, j-1)代表将算法思想转化成：将string1和string2都去掉末尾一个字符后，变成相同字符串的最小编辑距离是多少。因为两个字符串都去掉了一个字符，因此存在两种情况：如果被去掉的字符相同，就抵消。如果不同，就+1，表示替换字符。

最终的最小编辑距离是上面3种方法求出来的值的最小值。二维数组执行计算的效果图如下，最终的结果就是矩阵右上角的值：

![c1d1c63e59d62c27e0175e8b2822dd4c.png][]

JavaScript版的代码已经上传[仓库][Link 2]：

static Minimum = (a, b, c) => {
        return a < b ? (a < c ? a : c) : (b < c ? b : c); 
    }; 
    
    static LevenshteinDistance = (v1, v2) => {
        const len1 = v1.length;
        const len2 = v2.length;
        const matrix = [];  // matrix
        let i;              // iterates through v1
        let j;              // iterates through v2
        let sIndex;         // ith character of v1
        let tIndex;         // jth character of v2
        let cost;           // cost
    
        // Step 1
        if (len1 === 0) return len2;
        if (len2 === 0) return len1;
    
        // Step 2
        for (i = 0; i <= len1; i++) {
            matrix[i] = [];
            matrix[i][0] = i;
        }
    
        for (j = 0; j <= len2; j++) {
            matrix[0][j] = j;
        }
    
        // Step 3
        for (i = 1; i <= len1; i++) {
            sIndex = v1.charAt(i - 1);
            for (j = 1; j <= len2; j++) {
                tIndex = v2.charAt(j - 1);
                if (sIndex === tIndex) {
                    cost = 0;
                } else {
                    cost = 1;
                }
    
                matrix[i][j] = Demo.Minimum(
                    matrix[i - 1][j] + 1,
                    matrix[i][j - 1] + 1,
                    matrix[i - 1][j - 1] + cost,
                );
            }
        }
    
        // Step 4
        return matrix[len1][len2];
    };

[Link 1]: https://web.stanford.edu/class/cs124/lec/med.pdf
[98fae789c9d72522d44f722b3ee6966a.png]: /images/20210527/ac0b2e2f9274482fb6dabd1285dcdac1.png
[c1d1c63e59d62c27e0175e8b2822dd4c.png]: /images/20210527/09d7de69de26412e8225c5e5b1a69413.png
[Link 2]: https://github.com/JackZhangXL/Levenshtein-Distance

发表评论取消回复

表情：

评论列表（有 0 条评论，453人围观）

还没有评论，来说两句吧...

相关阅读

相关字符串相似度算法（编辑距离算法 Levenshtein Distance）

[字符串相似度算法（编辑距离算法 Levenshtein Distance）][Levenshtein Distance] 在搞验证码识别的时候需要比较字符代码的相似度用

小咪咪/ 2023年06月07日 08:08/ 0 赞/ 25 阅读

相关最小编辑距离

/ 求两个字符串的最小编辑距离 dp[i][j]表示s1[0...i-1]和s[0...j-1]的最小编辑距离 / public class Solutio

蔚落/ 2022年10月29日 11:20/ 0 赞/ 17 阅读

相关 Edit Distance（C++编辑距离）

（1）动态规划 class Solution { public: int minDistance(string w1, string w

我就是我/ 2022年10月11日 10:56/ 0 赞/ 46 阅读

相关 Levenshtein 相似度算法——Levenshtein(编辑距离)

[https://www.iteye.com/blog/wdhdmx-1343856][https_www.iteye.com_blog_wdhdmx-1343856] 原文

谁借莪１个温暖的怀抱￠/ 2022年08月28日 07:43/ 0 赞/ 204 阅读

相关编辑距离Edit distance

http://[blog.csdn.net/pipisorry/article/details/46383947][blog.csdn.net_pipisorry_articl

谁借莪１个温暖的怀抱￠/ 2022年08月05日 04:29/ 0 赞/ 364 阅读

相关 LeetCode 72.Edit Distance (编辑距离)

题目：给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行如下三种操作： 1. 插入一个字

墨蓝/ 2022年04月15日 04:30/ 0 赞/ 246 阅读

相关 Levenshtein Distance （LD算法）编辑距离算法原理

莱文斯坦距离，又称Levenshtein距离，是编辑距离的一种。指两个字串之间，由一个转成另一个所需的最少编辑操作次数。允许的编辑操作包括：将一个字符替换成另一个字符，插入一个

向右看齐/ 2022年02月22日 15:08/ 0 赞/ 352 阅读

相关 Levenshtein编辑距离C++实现

简介 Levenshtein Distance是1965年由苏联数学家Vladimir Levenshtein发明的。Levenshtein Distance也被称为编辑

末蓝、/ 2022年02月09日 11:15/ 0 赞/ 270 阅读

相关数据对齐-编辑距离算法详解（Levenshtein distance）

总结一句话：编辑距离就是从一个字符串变到另外一个字符串所需要最小的步骤一：简介在信息论、语言学和计算机科学中，Levenshtein distance是用于测量两个

我会带着你远行/ 2022年01月19日 03:21/ 0 赞/ 326 阅读

相关 React-虚拟dom-diff算法，Levenshtein Distance最小编辑距离

Levenshtein Distance是最小编辑距离的一种实现，网上搜到的一些python的实现，现在用前端的JavaScript来实现一下。什么是最小编辑距离？请看[斯坦福

太过爱你忘了你带给我的痛/ 2021年06月10日 20:40/ 0 赞/ 454 阅读