khoảng cách xóa giữa các từ

Question

Tôi đang cố gắng tìm số ký tự cần xóa để làm cho hai từ giống nhau. Ví dụ "at", "cat" sẽ là 1 vì tôi có thể xóa c, "boat" và "got" sẽ là 3 vì tôi có thể xóa b, a và g để làm cho nó ot. Tôi đặt các từ vào một từ điển với số lượng của chúng như là giá trị. Sau đó, tôi lặp lại từ điển và xem liệu khóa đó có tồn tại trong từ điển khác hay không, nếu không tôi thêm 1 vào sự khác biệt. Đây có phải là một thuật toán rất kém hiệu quả không?

Nhưng nó đang đánh giá quá cao số lần xóa mà tôi cần.

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

Như @Hulk đề cập này cũng tương tự như khoảng cách levenshtein. Sự khác biệt duy nhất là các thay thế không được phép nhưng có thể được sửa chữa bằng cách sử dụng chi phí thay thế là 2 giống như việc loại bỏ ký tự khỏi cả hai chuỗi. Ví dụ:

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

Output:

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

Answer 2

Tôi nghĩ mục tiêu của bạn tương tự như khoảng cách levenshtein.

Khoảng cách Levenshtein là thước đo để đo khoảng cách giữa 2 chuỗi.

Đây là liên kết wiki. https://en.wikipedia.org/wiki/Levenshtein_distance

Và đây là gói pypi cho khoảng cách levenshtein. https://pypi.python.org/pypi/python-Levenshtein

Answer 3

Bạn có thể sử dụng difflib cho việc này.

Ví dụ:

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

Prints:

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