仅通过插入和删除查找编辑距离的变化?
Variation of finding edit distance with only insertions and deletions?
我需要找到一个词与其排序词之间的编辑距离(例如: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)
需要做哪些编辑才能只找到插入和删除的数量?
删除 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。
我需要找到一个词与其排序词之间的编辑距离(例如: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)
需要做哪些编辑才能只找到插入和删除的数量?
删除 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。