编辑编辑距离 Python

Question

这段代码returns 2项的Levenshtein编辑距离。我怎样才能使插入和删除只花费 0.5 而不是 1？替换应该仍然花费 1.

def substCost(x,y):
   if x == y: 
      return 0
   else: 
      return 1

def  levenshtein(target, source):
   i = len(target); j = len(source)
   if i == 0:  
      return j
   elif j == 0: 
      return i

   return(min(levenshtein(target[:i-1],source)+1,
          levenshtein(target, source[:j-1])+1,
          levenshtein(target[:i-1], source[:j-1])+substCost(source[j-1],target[i-1])))

Answer 1

您需要在两个地方考虑添加或删除元音的成本降低。它们是函数基本情况中的 return j 和 return i 行，以及前两次递归调用后 min 调用中的 +1s。

我们需要更改每一个以使用 "ternary" 表达式：0.5 if ch in 'aeiou' else 1 代替假设每个添加或删除字符的成本 1。

对于基本情况，我们可以将 return 值替换为对包含三元表达式的生成器表达式的 sum 调用：

if i == 0:  
    return sum(0.5 if ch in 'aeiou' else 1 for ch in source)
elif j == 0: 
    return sum(0.5 if ch in 'aeiou' else 1 for ch in target)

对于后面的情况，我们可以将 +1 替换为三元表达式本身（使用索引而不是 ch 迭代变量）：

return min(levenshtein(target[:i-1],source) + (0.5 if target[-1] in 'aeiou' else 1),
           levenshtein(target, source[:j-1]) + (0.5 if source[-1] in 'aeiou' else 1),
           levenshtein(target[:i-1], source[:j-1])+substCost(source[j-1],target[i-1]))

如果你想概括这一点，你可以将三元表达式移到它自己的函数中，命名为 addCost，然后从 levenshtein 函数中的代码调用它。

编辑编辑距离 Python

Levenshtein edit distance Python

python

levenshtein-distance