如何修改levenshtein编辑距离函数，使之更加灵活。

Question

我正在寻找一个levenshtein编辑距离函数的版本，它有3个主要区别。

1. 它适用于标记化的输入，因此，它不使用 'hello world' 其 ['hello', 'world']. 所以每一个char都会被视为一个词，与其他词作为一个整体进行比较。因此，距离的 ['hello', 'world'] 和 ['world', 'hello'] 是2个更新。默认情况下，如果我把它们作为标记化的输入，普通的实现似乎已经像这样工作了。
2. 我想为插入、更新和删除定义一个自定义的数字成本。我想为插入、更新和删除定义一个自定义的数字成本。npm natural.js 似乎支持这个功能。
3. 我想定义一个自定义函数来检查平等性。现在所有的实现都使用 === 或者没有办法改变这个问题。

下面是我目前能做的最好的，通过稍微修改下面链接中的代码。它似乎与上面的#1和#3一起工作，但我不知道如何修改下面的代码来做#2。

// https://rosettacode.org/wiki/Levenshtein_distance
function levenshtein(a, b, customCheck) {
    var t = [], u, i, j, m = a.length, n = b.length;
    if (!m) { return n; }
    if (!n) { return m; }
    for (j = 0; j <= n; j++) { t[j] = j; }
    for (i = 1; i <= m; i++) {
        for (u = [i], j = 1; j <= n; j++) {
            u[j] = customCheck(a[i - 1], b[j - 1]) ? t[j - 1] : Math.min(t[j - 1], t[j], u[j - 1]) + 1;
        } t = u;
    } return u[n];
}

function customCheck(a, b) {
    return a === b;
}

有人知道吗？

---

EDIT: 试了一下，但它给我的成本是1，我把删除成本定为100，更新成本定为1，插入成本定为10。我以为删除成本是100，更新成本是1，插入成本是10。b.

function levenshtein(a, b, customCheck) {
    var t = [], u, i, j, m = a.length, n = b.length;
    if (!m) { return n; }
    if (!n) { return m; }
    for (j = 0; j <= n; j++) { t[j] = j; }
    for (i = 1; i <= m; i++) {
        for (u = [i], j = 1; j <= n; j++) {
            u[j] = customCheck(a[i - 1], b[j - 1]) ? t[j - 1] : Math.min(t[j - 1] + 100, t[j] + 1, u[j - 1] + 10); // removal, update, insert
        } t = u;
    }
}

function customCheck(a, b) {
    return a === b;
}

console.log(levenshtein('ab', 'a', customCheck));

Answer 1

就在这部分。

 Math.min(t[j - 1], t[j], u[j - 1]) + 1

t[j - 1] 是去除之前的成本 a, t[j] 是更换的费用，和 u[j - 1] 是清除费用 b (或插在 a). 1是当前步骤的成本，所以所有操作。我们可以放心地将1移入 Math.min:

 Math.min(t[j - 1] + 1, t[j] + 1, u[j - 1] + 1)

然后你可以很容易地改变每种类型的成本。