brute force for best edit distance

edit_distance.py

import editdist

def distance(a, b):
    """
    Find best edit distance between two strings of potentially uneven length.

    >>> import editdist
    >>> distance("abc", "abc")
    0
    >>> distance("abc", "abcdef")
    0
    >>> distance("abbb", "abcdef")
    2
    """
    # first position longer
    ab = sorted([a, b], key=len, reverse=True)
    assert all(isinstance(s, basestring) for s in ab)

    length_longer, length_shorter = len(ab[0]), len(ab[1])

    if length_longer == length_shorter:
        d = editdist.distance(ab[0], ab[1])

    else:
        dists = set()
        difference = length_longer - length_shorter

        for i in xrange(0, difference + 1):
            d = editdist.distance(ab[0][i:i + length_shorter], ab[1])
            # perfectly matching substring
            if d == 0:
                break
            dists.add(d)

        if d != 0:
            d = min(dists)

    return d