时间戳

首页 > 解决方案 > 在 Python 中使用操作权重编辑距离

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

问题描述

我是第一次了解编辑距离，并且只编码了几个月。我正在尝试修改算法，使不同的编辑操作具有不同的权重，如下所示：插入权重为 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 的倍数。我在这里遗漏了什么？任何帮助将不胜感激。

标签： pythondistanceeditlevenshtein-distanceweighted

解决方案

i = 0您分别拥有 when和j = 0to bej的基本成本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))

推荐阅读