仅通过插入和删除查找编辑距离的变化？

Question

我需要找到一个词与其排序词之间的编辑距离（例如：apple 和 aelpp），仅递归地使用插入和删除。

我找到了一些使用插入、删除和替换的资源，但我不确定如何只使用插入和删除。

这是我找到的代码：

def ld(s, t):
    if not s: return len(t)
    if not t: return len(s)
    if s[0] == t[0]: return ld(s[1:], t[1:])
    l1 = ld(s, t[1:])
    l2 = ld(s[1:], t)
    l3 = ld(s[1:], t[1:])
    return 1 + min(l1, l2, l3)

需要做哪些编辑才能只找到插入和删除的数量？

Answer 1

删除 l3，它会像这样计算替换

def ld2(s, t):
    if not s: return len(t)
    if not t: return len(s)
    if s[0] == t[0]: return ld2(s[1:], t[1:])
    l1 = ld2(s, t[1:])
    l2 = ld2(s[1:], t)
    return 1 + min(l1, l2)

您可以看到 ld('apple', 'applx') 等于 1，而具有相同参数的 ld2 的计算结果为 2。

仅通过插入和删除查找编辑距离的变化？

Variation of finding edit distance with only insertions and deletions?

python

edit-distance

levenshtein-distance