Löschabstand zwischen Wörtern

Question

Ich versuche zu finden, wie viele Zeichen ich löschen müsste, um die beiden Wörter gleich zu machen. Zum Beispiel "at", "cat" wäre 1, weil ich das c löschen könnte, "boat" und "got" wäre 3, weil ich die b, a und g löschen könnte, um es zu ot zu machen. Ich lege die Wörter in ein Wörterbuch mit ihrer Zählung als Wert. Dann iteriere ich über das Wörterbuch und sehe, ob dieser Schlüssel in dem anderen Wörterbuch existiert, ansonsten füge ich 1 zu der Differenz hinzu. Ist das ein sehr ineffizienter Algorithmus?

Aber es überschätzt die Anzahl der Löschungen, die ich brauche.

def deletiondistance(firstword, secondword): 
dfw = {} 
dsw = {} 
diff = 0 
for i in range(len(firstword)): 
    print firstword[i] 
    if firstword[i] in dfw: 
     dfw[firstword[i]]+=1 
    else: 
     dfw[firstword[i]]=1 
for j in range(len(secondword)): 
    if secondword[j] in dsw: 
     dsw[secondword[j]] +=1 
    else: 
     dsw[secondword[j]]=1 

for key, value in dfw.iteritems(): 

    if key in dsw: 
     #print "key exists" 
     pass 

    else: 
     diff +=1 

print "diff",diff 

Answer 1

Wie @Hulk erwähnt dies ähnlich ist Abstand levenshtein. Der einzige Unterschied besteht darin, dass Ersetzungen nicht erlaubt sind, aber das kann korrigiert werden, indem Substitutionskosten von 2 verwendet werden, was dem Entfernen von Zeichen aus beiden Strings entspricht. Beispiel:

def dist(s1, s2): 
    cur = list(range(len(s2) + 1)) 
    prev = [0] * (len(s2) + 1) 
    for i in range(len(s1)): 
     cur, prev = prev, cur 
     cur[0] = i + 1 
     for j in range(len(s2)): 
      # Substitution is same as two deletions 
      sub = 0 if s1[i] == s2[j] else 2 
      cur[j+1] = min(prev[j] + sub, cur[j] + 1, prev[j+1] + 1) 

    return cur[-1] 

cases=[('cat','bat'), 
     ('bat','cat'), 
     ('broom', 'ballroom'), 
     ('boat','got'), 
     ('foo', 'bar'), 
     ('foobar', '')] 

for s1, s2 in cases: 
    print('{} & {} = {}'.format(s1, s2, dist(s1, s2))) 

Ausgang:

cat & bat = 2 
bat & cat = 2 
broom & ballroom = 3 
boat & got = 3 
foo & bar = 6 
foobar & = 6 

Answer 2

Ich denke, Ihr Ziel ist vergleichbar mit Levenshtein Abstand.

Levenshtein Abstand ist eine Metrik für die Messung der Entfernung zwischen 2 Strings.

Hier ist ein Wiki-Link. https://en.wikipedia.org/wiki/Levenshtein_distance

Und hier ist Pypi-Paket für Levenshtein Abstand. https://pypi.python.org/pypi/python-Levenshtein

Answer 3

Sie können dafür difflib verwenden.

Beispiel:

import difflib 

cases=[('cat','bat'), 
     ('bat','cat'), 
     ('broom', 'ballroom'), 
     ('boat','got')] 

for a,b in cases:  
    print('{} => {}'.format(a,b)) 
    cnt=0 
    for i,s in enumerate(difflib.ndiff(a, b)): 
     if s[0]==' ': continue 
     elif s[0]=='-': 
      print(u'Delete "{}" from position {}'.format(s[-1],i)) 
     elif s[0]=='+': 
      print(u'Add "{}" to position {}'.format(s[-1],i))  
     cnt+=1 
    print("total=",cnt,"\n") 

Drucke:

cat => bat 
Delete "c" from position 0 
Add "b" to position 1 
total= 2 

bat => cat 
Delete "b" from position 0 
Add "c" to position 1 
total= 2 

broom => ballroom 
Add "a" to position 1 
Add "l" to position 2 
Add "l" to position 3 
total= 3 

boat => got 
Delete "b" from position 0 
Add "g" to position 1 
Delete "a" from position 3 
total= 3