Có thể là SequenceMatcher trong difflib của Python có thể cung cấp một cách hiệu quả hơn để tính khoảng cách Levenshtein?

Question

Dưới đây là ví dụ điển hình về các thuật toán tổng quát để tính toán khoảng cách levenshtein (Tôi đã kéo từ Magnus Hetland's webite):

def levenshtein(a,b): 
    "Calculates the Levenshtein distance between a and b." 
    n, m = len(a), len(b) 
    if n > m: 
     # Make sure n <= m, to use O(min(n,m)) space 
     a,b = b,a 
     n,m = m,n 

    current = range(n+1) 
    for i in range(1,m+1): 
     previous, current = current, [i]+[0]*n 
     for j in range(1,n+1): 
      add, delete = previous[j]+1, current[j-1]+1 
      change = previous[j-1] 
      if a[j-1] != b[i-1]: 
       change = change + 1 
      current[j] = min(add, delete, change) 

    return current[n] 

tôi đã tự hỏi, tuy nhiên, nếu có thể có một hiệu quả hơn (và có khả năng thanh lịch hơn) tinh khiết Triển khai Python sử dụng SequenceManager của difflib. Sau khi chơi với nó, đây là những gì tôi đã đưa ra với:

from difflib import SequenceMatcher as sm 

def lev_using_difflib(s1, s2): 
    a = b = size = distance = 0 
    for m in sm(a=s1, b=s2).get_matching_blocks(): 
     distance += max(m.a-a, m.b-b) - size 
     a, b, size = m 
    return distance 

Tôi không thể đưa ra một trường hợp thử nghiệm không thành công, và hiệu suất có vẻ tốt hơn đáng kể so với thuật toán chuẩn.

Sau đây là các kết quả với thuật toán Levenshtein dựa trên difflib:

>>> from timeit import Timer 
>>> setup = """ 
... from difflib import SequenceMatcher as sm 
... 
... def lev_using_difflib(s1, s2): 
...  a = b = size = distance = 0 
...  for m in sm(a=s1, b=s2).get_matching_blocks(): 
...   distance += max(m.a-a, m.b-b) - size 
...   a, b, size = m 
...  return distance 
... 
... strings = [('sunday','saturday'), 
...   ('fitting','babysitting'), 
...   ('rosettacode','raisethysword')] 
... """ 
>>> stmt = """ 
... for s in strings: 
...  lev_using_difflib(*s) 
... """ 
>>> Timer(stmt, setup).timeit(100000) 
36.989389181137085 

Và đây là tiêu chuẩn tinh khiết thực hiện python:

>>> from timeit import Timer 
>>> setup2 = """ 
... def levenshtein(a,b): 
...  n, m = len(a), len(b) 
...  if n > m: 
...   a,b = b,a 
...   n,m = m,n 
... 
...  current = range(n+1) 
...  for i in range(1,m+1): 
...   previous, current = current, [i]+[0]*n 
...   for j in range(1,n+1): 
...    add, delete = previous[j]+1, current[j-1]+1 
...    change = previous[j-1] 
...    if a[j-1] != b[i-1]: 
...     change = change + 1 
...    current[j] = min(add, delete, change) 
... 
...  return current[n] 
... 
... strings = [('sunday','saturday'), 
...   ('fitting','babysitting'), 
...   ('rosettacode','raisethysword')] 
... """ 
>>> stmt2 = """ 
... for s in strings: 
...  levenshtein(*s) 
... """ 
>>> Timer(stmt2, setup2).timeit(100000) 
55.594768047332764 

là việc thực hiện các thuật toán sử dụng SequenceMatcher difflib thực sự tốt hơn? Hoặc là nó dựa vào một thư viện C làm mất hiệu lực so sánh hoàn toàn? Nếu nó dựa vào các phần mở rộng của C, làm thế nào tôi có thể biết bằng cách nhìn vào việc thực hiện difflib.py?

Sử dụng Python 2.7.3 [GCC 4.2.1 (Apple Inc. xây dựng 5666)]

Cảm ơn bạn đã giúp đỡ!

Answer 1

>>> levenshtein('hello', 'world') 
4 
>>> lev_using_difflib('hello', 'world') 
5