编辑距离

编辑距离是什么？下面是摘自维基百科的说明：

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

例如将kitten一字转成sitting：

1. sitten (k→s)
2. sittin (e→i)
3. sitting (→g)

俄罗斯科学家弗拉基米尔·莱文斯坦在1965年提出这个概念。

算法分析

从一个字符串变到另一个字符串可以：

1. 删除一个字符
2. 插入一个字符
3. 替换一个字符

从 hello 变到 aeliloo：

1. h （substitute）替换为 a ：编辑距离+1
2. 插入（insert） i ：编辑距离+1
3. 删除 （delete）o ：编辑距离+1

所以编辑距离为：3

如何计算最小编辑距离

首先定义两个变量 i（目标字符串中字符的位置）和 j（原始字符串中字符的位置）

则编辑距离 s = D(i,j)

1. i = 0, j = 0 --> D(0, 0) = 0
2. i > 0, j = 0 --> D(i, 0) = i (插入i次)
3. j = 0, j > 0 --> D(0, j) = j (删除j次)
4. i > 0, j > 0 --> D(i, j) = Min { edit(i-1, j) + 1, edit(i, j-1) + 1, edit(i-1, j-1) + f(i,j) }，其中如果 i == j，则 f(i,j) = 0, 否则 f(i, j) = 1

最小编辑距离算法伪代码：

function MinEditDistance(targetStr, sourceStr) {
    n = length(targetStr)
    m = length(sourceStr)
    matrix D[n,m]
    D[0,0] = 0;
    D[0,1] = 1......D[0,m] = m;
    D[1,0] = 1......D[n,0] = n;
    for i of range: 1 to n
        for j of range: 1 to m
            D[i, j] = min(D[i-1, j] + 1, D[i, j-1] + 1, D[i-1, j-1] + f(i, j))
    return D[n,m]
}

从 hello 变到 aeliloo：目标字符串 aeliloo，源字符串 hello

由：

D[0,0] = 0;
D[0,1] = 1......D[0,m] = m;
D[1,0] = 1......D[n,0] = n;

可得 dMatrix:

由： dMatrix[i,j] = min(dMatrix[i-1, j] + 1, dMatrix[i, j-1] + 1, dMatrix[i-1, j-1] + f(i, j))

当： i = 1, j = 1

所以：dMatrix[1,1] = min(dMatrix[0, 1] + 1, dMatrix[1, 0] + 1, dMatrix[0, 0] + f(1, 1)) 由于 字符 a 不等于 h 所以 f(1,1) = 1

得：dMatrix[1,1] = 1;

由此可以得到最终 dMatrix：

最小编辑距离 s = dMatrix[7, 5] = 3

JavaScript实现

'use strict';

function minEditDistance(target, source) {
    var tLen, sLen, dMatrix, i, j, temp;
    tLen = target.length;
    sLen = source.length;
    dMatrix = [];
    for(i = 0; i <= tLen; i++) {
        dMatrix.push([i]);
    }
    for(i = 0; i <= sLen; i++) {
        dMatrix[0][i] = i;
    }
    for(i = 1; i <= tLen; i++) {
        for(j = 1; j <= sLen; j++) {
            temp = [];
            temp.push(dMatrix[i][j-1] + 1);
            temp.push(dMatrix[i-1][j] + 1);
            temp.push(dMatrix[i-1][j-1] + (target[i - 1] === source[j - 1] ? 0 : 1));
            dMatrix[i][j] = Math.min.apply(null, temp);
        }
    }

    return dMatrix[tLen][sLen];
}

参考

1. 维基百科：Edit_distance