Levenshtein bearbeiten Abstand Python

Question

Dieser Codeabschnitt gibt den Levenshtein-Bearbeitungsabstand von 2 Begriffen zurück. Wie kann ich das so machen, dass Einfügen und Löschen kostet nur 0,5 statt 1? Substitution sollte noch Kosten 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

Es gibt zwei Stellen, die Sie für die reduzierten Kosten des Hinzufügens oder Entfernens eines Vokal berücksichtigen müssen. Sie sind die return j und return i Zeilen in den Basisfällen Ihrer Funktion, und die +1 s in der min Aufruf nach den ersten zwei rekursiven Aufrufe.

Wir müssen jeden von denen ändern, um einen "ternären" Ausdruck zu verwenden: 0.5 if ch in 'aeiou' else 1 anstelle von angenommenen Kosten von 1 pro hinzugefügtem oder entferntem Zeichen.

Für die Basis Fällen können wir die Rückgabewerte mit sum fordert einen Generator Ausdruck ersetzen, der den ternären Ausdruck beinhaltet:

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) 

Für spätere Fälle können wir die +1 mit dem ternären Ausdruck ersetzen selbst (mit einem Index anstelle der ch Iterationsvariable):

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])) 

Wenn Sie dies verallgemeinern wollten, könnten Sie den ternären Ausdruck aus in seine eigene Funktion, genannt somet bewegen Hing wie addCost, und rufen Sie es aus dem Code in der levenshtein Funktion.