Usunięcie odległości między słowami

Question

Próbuję znaleźć liczbę znaków, które muszę usunąć, aby te same słowa były takie same. Na przykład "przy", "kot" będzie 1, ponieważ mogę usunąć c, "łódź" i "dostał" będzie 3, ponieważ mogę usunąć b, a ig, aby go ot. Umieściłem słowa w słowniku z ich liczbą jako wartością. Następnie przechodzę do słownika i sprawdzam, czy ten klucz istnieje w innym słowniku, inaczej dodaję 1 do różnicy. Czy jest to bardzo nieefektywny algorytm?

Ale przecenia liczbę potrzebnych skreśleń.

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

Jak wspomniano @Hulk jest podobny do Levenshteina odległość. Jedyna różnica polega na tym, że podstawienia są niedozwolone, ale można je naprawić, stosując koszt zastąpienia równy 2, który jest taki sam jak usunięcie znaku z obu łańcuchów. Przykład:

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

wyjściowa:

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

Answer 2

Myślę, że Twój cel jest podobny do dystansu dystansowego.

Odległość odstępu jest miarą odległości między dwoma ciągami.

Oto link do strony wiki. https://en.wikipedia.org/wiki/Levenshtein_distance

I tutaj jest pakiet pypi dla odległości levenshtein. https://pypi.python.org/pypi/python-Levenshtein

Answer 3

Możesz użyć do tego celu difflib.

przykład:

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

reprodukcje:

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