Est-il possible que le SequenceMatcher de la difflib de Python puisse fournir un moyen plus efficace de calculer la distance de Levenshtein ?

Question

Voici l'exemple de manuel de l'algorithme général pour calculer la distance de Levenshtein (j'ai tiré de Site web de Magnus Hetland ) :

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]

Je me demandais cependant s'il n'existait pas une implémentation plus efficace (et potentiellement plus élégante) en Python pur qui utilise le SequenceManager de difflib. Après avoir joué avec, voici ce que j'ai trouvé :

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

Je n'arrive pas à trouver un cas d'essai où il échoue, et les performances semblent être nettement supérieures à celles de l'algorithme standard.

Voici les résultats avec l'algorithme levenshtein qui s'appuie sur 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

Et voici l'implémentation standard en pur 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

Les performances de l'algorithme utilisant le SequenceMatcher de difflib sont-elles vraiment meilleures ? Ou est-ce qu'il s'appuie sur une bibliothèque C qui invalide complètement la comparaison ? S'il s'appuie sur des extensions C, comment puis-je le savoir en regardant l'implémentation de difflib.py ?

Utilisation de Python 2.7.3 [GCC 4.2.1 (Apple Inc. build 5666)].

Merci d'avance pour votre aide !

Answer 1

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