数学篇 - 动态规划,编辑距离的计算(笔记)

2020-09-09

Daily 数学

动态规划（Dynamic Programming）

很多人也简称DP,动态规划需要通过子问题的最优解，推导出最终问题的最优解，因此这种方法特别注重子问题之间的转移关系。我们通常把这些子问题之间的转移称为状态转移，并把用于刻画这些状态转移的表达式称为状态转移方程。

编辑距离 (莱文斯坦距离,又称Levenshtein距离)

俄罗斯科学家弗拉基米尔·莱文斯坦（毕业于莫斯科国立大学数学和力学系）在1965年提出，他因对纠错码理论和信息理论的贡献，于2006年获得IEEE Richard W. Hamming奖章。

定义：莱文斯坦距离也称编辑距离，指的是将文本 A 编辑成文本 B 需要的最少变动次数（每次只能增加、删除或修改一个字）。
用途：可以用来计算字符串的相似度，文本相似度, 拼写纠错和抄袭侦测等等
优点：准确率很高，编辑距离算出来很小，文本相似度肯定很高。
缺点：召回率不高，由于编辑距离与文本的顺序有关。在文字相同，文字顺序变化很大的情况下，相似度会变得很低。比如“正大光明”和“光明正大”其实是一个意思。但编辑距离是4，完全不匹配

计算解析：

首先定义的单字符编辑操作有且仅有三种：

插入（Insertion）

删除（Deletion）

替换（Substitution）

图 1

搜索推荐关键词的应用

计算 mouuse 与 mouse的编辑距离

图 2

表格推导

图 3

这里面求最小值的 min 函数里有三个参数，分别对应三种情况的编辑距离，分别是：替换、插入和删除字符。

代码实现


/**
  * @Description:  使用状态转移方程，计算两个字符串之间的编辑距离
  * @param a-第一个字符串，b-第二个字符串
  * @return let-两者之间的编辑距离
  */
function getStrDistance( a,  b) {
    
    if (a == null || b == null) return -1;


  // 初始用于记录化状态转移的二维表
    let d = []
  for (let index = 0; index <= a.length; index++) {
     d.push(new Array(b.length))
  }


    // 如果i为0，且j大于等于0，那么d[i, j]为j
    for (let j = 0; j <= b.length; j++) {
      d[0][j] = j;
    }
    
    // 如果i大于等于0，且j为0，那么d[i, j]为i
    for (let i = 0; i <= a.length; i++) {
      d[i][0] = i;
    }

    // 当前二维数组的状态
    //   [
    //   [0, 1, 2, 3,4, 5, 6  ],
    //   [ 1, <5 empty items> ],
    //   [ 2, <5 empty items> ],
    //   [ 3, <5 empty items> ],
    //   [ 4, <5 empty items> ],
    //   [ 5, <5 empty items> ],
    //   [ 6, <5 empty items> ]
    // ]

    // 实现状态转移方程
    for (let i = 0; i < a.length; i++) {
      for (let j = 0; j < b.length; j++) {
        
        let r = 0;
        if (a.charAt(i) != b.charAt(j)) {
          r = 1;
        } 

        // 给所有的格志做应有的标记
        // 坐标加1是为了从第二个格子开始记录数据
        let first_append = d[i][j + 1] + 1;
        let second_append = d[i + 1][j] + 1;


        // 当前格志记录之前对比的差异
        let replace = d[i][j] + r;

        console.log(a.charAt(i) , b.charAt(j))
        console.log(first_append, second_append)

        // 求得first_append, second_append,replace三个最小的一个
        // 分别对应三种情况的编辑距离，分别是：替换、插入和删除字符
        let min = Math.min(first_append, second_append);
        min = Math.min(min, replace);

        // 所有的差异累积
        d[i + 1][j + 1] = min;
        
      }
    }

    // 当前二维数组的状态
    // [
    //   [0, 1, 2, 3, 4, 5, 6],
    //   [1, 0, 1, 2, 3, 4, 5],
    //   [2, 1, 1, 2, 3, 4, 5],
    //   [3, 2, 2, 2, 3, 4, 5],
    //   [4, 3, 3, 2, 2, 3, 4],
    //   [5, 4, 4, 3, 3, 2, 3],
    //   [6, 5, 5, 4, 4, 3, 2]
    // ]
    // 输出最终的累积值,就是他们的编辑距离
    return d[a.length][b.length];
  }

尾巴

这一节有点懵,记录一下后续再查更多资料深入理解了. 例子理解的还行,一到应用就嗝屁.还是要多做题…

参考资料

莱文斯坦距离 : https://www.jianshu.com/p/4678d3f7b6f1
程序员的数学基础课 : https://time.geekbang.org/column/article/76183

微信公众号

本文链接：

https://alili.tech/archive/nfo3tlig7y/

动态规划 （Dynamic Programming）