È possibile che SequenceMatcher in difflib di Python possa fornire un modo più efficiente per calcolare la distanza di Levenshtein?

Question

Ecco l'esempio da manuale del algoritmo generale per calcolare Levenshtein Distanza (ho tirato da 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] 

Mi chiedevo, però, se ci potrebbe essere un più efficiente (e potenzialmente più elegante) puro Implementazione Python che utilizza SequenceManager di difflib. Dopo aver giocato intorno con esso, questo è quello che mi si avvicinò con:

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 

Non posso venire con un banco di prova in cui non riesce, e la performance sembra essere significativamente migliore rispetto l'algoritmo standard.

Ecco i risultati con l'algoritmo levenshtein che si basa su 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 

Ed ecco l'implementazione di Python puro di serie:

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

è la performance dell'algoritmo utilizzato SequenceMatcher di difflib davvero meglio? O si basa su una libreria C che invalida completamente il confronto? Se si basa su estensioni C, come posso dire osservando l'implementazione difflib.py?

Usare Python 2.7.3 [GCC 4.2.1 (Apple Inc. costruire 5666)]

Grazie in anticipo per il vostro aiuto!

Answer 1

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