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

问题描述 投票:0回答:1

我正在寻找一个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));
javascript levenshtein-distance
1个回答
0
投票

就在这部分。

 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)

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

热门问题
推荐问题
最新问题