Возможно ли, что SequenceMatcher в difflib Python мог бы предоставить более эффективный способ для вычисления расстояния Левенштейна?

Question

Вот учебный пример общего алгоритма для вычисления расстояния Левенштейна (я взял из веб-сайта Магнуса Хетланда):

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]

Мне было интересно, однако, может ли быть более эффективная (и потенциально более изящная) реализация на чистом Python, которая использует difflib's SequenceManager. Поиграв с этим, вот что я придумал:

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

Я не могу придумать тестовый случай, когда он терпит неудачу, и производительность кажется значительно лучше, чем стандартный алгоритм.

Вот результаты с алгоритмом Левенштейна, который опирается на 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

А вот стандартная реализация чистого 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

Действительно ли производительность алгоритма с использованием difflib SequenceMatcher действительно лучше? Или это полагается на библиотеку C, которая делает недействительным сравнение? Если это зависит от расширений C, как я могу это определить, посмотрев на реализацию difflib.py?

Использование Python 2.7.3 [GCC 4.2.1 (Apple Inc., сборка 5666)]

Заранее спасибо за помощь!

Answer 1

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