在 Python 中使用操作权重编辑距离

Question

我是第一次学习编辑距离，并且只编写了几个月的代码。我正在尝试修改算法，使不同的编辑操作具有不同的权重，如下所示：插入权重 20，删除权重 20，替换权重 5。

如果所有操作的权重（levenshtein 距离）相等，我已经能够实现计算最小编辑距离的基本代码。但是，如果它们与上述不同，将如何实施呢？这是我目前拥有的：

str1="algorithms"
str2="alligator"
m=len(str1)
n=len(str2)

def editdistance(str1, str2, m, n):
  table=[[0 for x in range(n+1)] for x in range(m+1)]
  
  for i in range(m+1):
    for j in range(n+1):

      if i==0:
        table[i][j]=j

      elif j==0:
        table[i][j]=i

      elif str1[i-1]==str2[j-1]:
        table[i][j]=table[i-1][j-1]

      else:
         table[i][j] = min(20+table[i][j-1], 20+table[i-1][j], 5+table[i-1][j-1])
        

  return table[m][n]

print(editdistance(str1, str2, m, n))

输出是 46，这显然是错误的，因为答案应该是 5 的倍数。我在这里错过了什么？任何帮助将不胜感激。

Answer 1

当 i = 0 和 j = 0 时的基本成本分别为 j 和 i，它们不是 5 的倍数。那么你应该乘以他们 20 因为不使用字母本质上与为了编辑距离而删除或插入它们相同。所以你应该尝试这样的事情：

str1="algorithms"
str2="alligator"
m=len(str1)
n=len(str2)

def editdistance(str1, str2, m, n):
  table=[[0 for x in range(n+1)] for x in range(m+1)]
  
  for i in range(m+1):
    for j in range(n+1):

      if i==0:
        table[i][j]=j*20

      elif j==0:
        table[i][j]=i*20

      elif str1[i-1]==str2[j-1]:
        table[i][j]=table[i-1][j-1]

      else:
         table[i][j] = min(20+table[i][j-1], 20+table[i-1][j], 5+table[i-1][j-1])
        

  return table[m][n]

print(editdistance(str1, str2, m, n))

在 Python 中使用操作权重编辑距离

Edit Distance w/ operational weights in Python

python

distance

edit

levenshtein-distance

weighted