动态规划之字符串编辑距离

Question

编辑距离

我们都用过在线字典，应该会有这样一个体验：在输入我们想要单词的前几个字母时，输入框下的提示框会给我们推荐若干个字母相近的单词。或者另一种用户体验：拼写检查。那么这些单词推荐是怎么实现的呢？程序是怎么知道我们想要的单词的呢？这里就需要引入编辑距离（Edit distance）的概念了。

简单来讲，两个单词的编辑距离就是单词 a 通过增加字母、删减字母和替换字母等操作变成单词 b ，在这个过程中总共进行了多少次操作便是这两个单词的编辑距离。

比如 snowy 和 sunny 两个单词，我们可以这样来进行编辑：

• 方法1：

S - N O W Y
S U N N - Y
cost: 3

上下表格字符一一对齐来看：增加U、将O改为N、删除W，共3步，所以编辑距离是3。

• 方法2：

- S N O W - Y
S U N - - N Y
cost: 5

上下表格字符一一对齐来看：增加S、将S改为U、删除O、删除W、增加N，共5步，所以编辑距离是5。

最小编辑距离（Levenshtein Distance）

题目描述：https://leetcode.com/problems/edit-distance/description/

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

1. 推导状态转移方程

E[i][j] = min{ E[i-1][j] + 1, E[i][j-1]+1, E[i-1][j-1] + diff(i, j) }，其中 diff(i, j) 表示当 a[i] = b[j] ，返回1；a[i] <> b[j]，返回0。

即针对三种编辑操作，那么最优子结构应该是对这三种操作所得到的编辑距离进行求最小值。

• 当编辑操作为字符串 a[1…i-1] 增加字符 a[i] 才能得到字符串 b[1…j] ，那么 E[i][j] 需要 E[i-1][j] 加 1；
• 当编辑操作为字符串 a[1…i] 删减字符 a[i] 才能得到字符串 b[1…j-1] ，那么 E[i][j] 需要 E[i][j-1]加1；
• 当编辑操作为替换，即当 a[i] = b[j] 时，那么 E[i][j] 需要 E[i-1][j-1] + 1；如果不等时，E[i][j] 等于 E[i-1][j-1] 。

最后对这三个操作的结果进行求最小值即可。

例如：

两个单词分别为 EXPONENTIAL 和 POLYNOMIAL。

并让第一行和列的值从0开始增长。矩阵的最后一个值d[n][m]即是它们的距离。

a = [' ', 'E', 'X', 'P', 'O', 'N', 'E', 'N', 'T', 'I', 'A', 'L'];
b = [' ', 'P', 'O', 'L', 'Y', 'N', 'O', 'M', 'I', 'A', 'L'];

其中，子结构 E[4][3] 表示 EXPO 与 POL 的最小编辑距离。

• E[i-1][j] + 1，即 EXP 与 POL 的最小编辑距离
• E[i][j-1] + 1，即 EXPO 与 PO 的最小编辑距离
• E[i-1][j-1] + 1(因为O不等于L)，即 EXP 与 PO 的最小编辑距离。

function editDistance(str1, str2) {
    let m = str1.length;
    let n = str2.length;
    let dp = [new Array(n + 1)];
    let insertion;
    let deletion;
    let replace;
    for(let i = 0; i <= m; i++) {
        // dp[i][0] = i;
        dp[i] = [i]; //可以先创建好二维数组
    }
    for(let j = 0; j <= n; j++) {
        dp[0][j] = j;
    }
    for(let i = 1; i <= m; i++) {
        for(let j = 1; j <= n; j++) {
            let cost = 0; // cost = 0
            if(str1[i - 1] !=str2[j - 1]) {
                cost = 1;
            }
            insertion = dp[i- 1][j] + 1; // 上边 + 1
            deletion = dp[i][j - 1] + 1; // 左边 + 1
            replace = dp[i - 1][j - 1] + cost; // 左上角
            dp[i][j] = Math.min(insertion, deletion, replace);
        }
    }
    // console.log(dp)
    return dp[m][n];
}

editDistance('jary', 'jerry'); // 2
editDistance('EXPONENTIAL', 'POLYNOMIAL'); // 6

一道题目：英文单词拼写纠错推荐

题目描述：

英文单词拼写的时候可能会出现拼写错误的情况(typo)。下面的题目，我们尝试实现拼写纠错推荐的功能。

字串编辑距离是衡量字串间相似度的常见手段。

①字串编辑距离：是指利用字符操作，把字符串A转换成字符串B所需要的最少操作数。

②字串操作包括：删除字符(removal)、插入字符(insertion)、修改字符(substitution)。

③使用以下规则对推荐纠错选项进行相似度排序。得分越高，认为相似度越低

只涉及到26个英文字符、不区分大小写。

• 删除(removal) 3分
• 插入(insertion) 3分
• 修改(substitution) ：

  (q w e r t a s d f g z x c v ) （y u i o p h j k l b n m）

  以上两个分组内的字符修改 1 分，两个分组间字符修改 2 分。

输入：
每行一个输入。空格分割参数。 第一个参数是目标单词(可能存在 typo ) ，后面若干空格分割参数(个数不定)是字典单词，作为候选纠错项(也可能和第一个参数重复)。

输出：
按照上面的纠错规则字串相似度最小编辑距离进行排序，给出3个(如有)对应的纠错候选。 如得分相同，则按照输入顺序进行排序。

样例输入：
slep slap sleep step shoe shop snap slep

样例输出：
slep slap step

const arr1 = ["q", "w", "e", "r", "t", "a", "s", "d", "f", "g", "z", "x", "c", "v"];
const arr2 = ["y", "u", "i", "o", "p", "h", "j", "k", "l", "b", "n", "m"];

function levenshteinDistance(a, b) {
    const distanceMatrix = Array(b.length + 1).fill(null).map(() => Array(a.length + 1).fill(null));

    for (let i = 0; i <= a.length; i += 1) {
        distanceMatrix[0][i] = i * 3;
    }

    for (let j = 0; j <= b.length; j += 1) {
        distanceMatrix[j][0] = j * 3;
    }

    for (let j = 1; j <= b.length; j += 1) {
        for (let i = 1; i <= a.length; i += 1) {
            let indicator = a[i - 1] === b[j - 1] ? 0 : 1;

            if (indicator === 1) {
                const typeA1 = arr1.includes(a[i - 1]);
                const typeB1 = arr1.includes(b[i - 1]);
                const typeA2 = arr2.includes(a[i - 1]);
                const typeB2 = arr2.includes(b[i - 1]);

                if (typeA1 === typeB1 === true || typeA2 === typeB2 === true) {
                    indicator = 1;
                } else if ((typeA1 && !typeB1) || (!typeA1 && typeB1)) {
                    indicator = 2;
                } else {
                    indicator = 3;
                }
            }


            distanceMatrix[j][i] = Math.min(
                distanceMatrix[j][i - 1] + 3, // deletion
                distanceMatrix[j - 1][i] + 3, // insertion
                distanceMatrix[j - 1][i - 1] + indicator, // substitution
            );
        }
    }

    return distanceMatrix[b.length][a.length];
}



function findCandidate(base, arr) {
    let res = [];
    let result = [];
    let i = 1;
    arr.map(item => {
        const obj = {};
        obj.value = levenshteinDistance(base, item);
        obj.item = item;
        obj.index = i++;
        result.push(obj);
    });


    result.sort(function(a, b) {
        return a.value === b.value ?
            a.index - b.index :
            a.value - b.value;
    });

    result.slice(0, 3).map(item => {
        res.push(item.item);
    })
    return res.join(' ');
}

findCandidate('slep', ['slap', 'sleep', 'step', 'shoe', 'shop', 'snap', 'slep']); // "slep slap step"

应用

最小编辑距离通常作为一种相似度计算函数被用于多种实际应用中，详细如下：（特别的，对于中文自然语言处理，一般以词为基本处理单元）

1. 生物领域中DNA分析：比较 DNA 序列并尝试找出两个序列的公共部分。如果两个 DNA 序列有类似的公共子序列，那么这些两个序列很可能是同源的。在比对两个序列时，不仅要考虑完全匹配的字符，还要考虑一个序列中的空格或间隙（或者，相反地，要考虑另一个序列中的插入部分）和不匹配，这两个方面都可能意味着突变（mutation）。在序列比对中，需要找到最优的比对（最优比对大致是指要将匹配的数量最大化，将空格和不匹配的数量最小化）。
2. NLP中应用：即两个字符串的相似计算函数可用于下面的任务。

• 拼写纠错（Spell Correction）：又将每个词与词典中的词条比较，英文单词往往需要做词干提取等规范化处理，如果一个词在词典中不存在，就被认为是一个错误，然后试图提示N个最可能要输入的词——拼写建议。常用的提示单词的算法就是列出词典中与原词具有最小编辑距离的词条。
• 命名实体抽取（Named Entity Extraction）：由于实体的命名往往没有规律，如品牌名，且可能存在多种变形、拼写形式，这样导致基于词典完全匹配的命名实体识别方法召回率较低，为此，我们可以使用编辑距离由完全匹配泛化到模糊匹配，先抽取实体名候选词。
• 实体共指（Entity Coreference）：通过计算任意两个实体名之间的最小编辑距离判定是否存在共指关系。
• 字符串核函数（String Kernel）：最小编辑距离作为字符串之间的相似度计算函数，用作核函数，集成在SVM中使用。

Reference

斯坦福课件
Levenshtein Distance