编辑距离算法（Levenshtein距离）与字符有不同的长度？

Question

我正在研究一个算法问题，这是Levenshtein Distance（最小编辑距离）的修改版本。在

现在为字符串提供一个字符长度数组，并返回计算的距离。在

• 删除长度为n的字符将花费n个距离，以便插入字符。在
• 替换可以被视为插入代价为2n距离的删除。在
• 可以部分删除字符或插入任意长度的字符。在

示例：

ex1.
string1 = "egg" with length [1, 1, 1]
string2 = "eg" with length [1, 1.5]

They have a distance of 0.5 (insert a 'g' with 0.5 length at the end of string2)

ex2.
string1 = "elicit" with length [1, 1, 1, 1, 1, 1]
string2 = "illicit" with length [0.9, 1.2, 1, 0.9, 0.9, 1.1]

They have a distance of 1.9 + 0.2 + 1 + 0 + 0.1 + 0.1 + 0.1 = 3.4

一个近似的解决方案是尝试将字符上采样到相等的长度，然后使用Wagner–Fischer算法在O（n^2）中对问题进行动态规划求解。然而，由于我们对它进行采样，它将变成一个有量化误差的近似解。在

我曾尝试过像下面这样的递归版本，但它非常慢。我尝试使用散列来保存计算的值，以剪切递归分支，但似乎仍然很糟糕。在

Python中的递归版本：

def lev(a, a_lens, b, b_lens):
    if not a:
        return sum(b_lens)
    elif not b:
        return sum(a_lens)
    else:
        if a_lens[0] < b_lens[0]:
            _b_lens = b_lens[:]
            _b_lens[0] -= a_lens[0]
            if a[0] == b[0]:
                change = lev(a[1:], a_lens[1:], b, _b_lens)
            else:
                change = MAX
        else:
            _a_lens = a_lens[:]
            _a_lens[0] -= b_lens[0]
            if a[0] == b[0]:
                change = lev(a, _a_lens, b[1:], b_lens[1:])
            else:
                change = MAX
        insert = b_lens[0] + lev(a, a_lens, b[1:], b_lens[1:])
        delete = a_lens[0] + lev(a[1:], a_lens[1:], b, b_lens)
        minimum = min(change, insert, delete)
        return minimum

如何改进？有可能实现O（n^2）吗？任何语言都是受欢迎的。谢谢。在