Damerau-Levenshtein distance

Damerau-Levenshtein.py

def dlevenshtein(seq1, seq2):
    """
    This implementation is O(N*M) time and O(M) space, for N and M the
    lengths of the two sequences.
    # codesnippet:D0DE4716-B6E6-4161-9219-2903BF8F547F    
    """
    
    oneago = None
    thisrow = range(1, len(seq2) + 1) + [0]
    for x in xrange(len(seq1)):
        twoago, oneago, thisrow = oneago, thisrow, [0] * len(seq2) + [x + 1]
        for y in xrange(len(seq2)):
            delcost = oneago[y] + 1
            addcost = thisrow[y - 1] + 1
            subcost = oneago[y - 1] + (seq1[x] != seq2[y])
            thisrow[y] = min(delcost, addcost, subcost)
            # This block deals with transpositions
            if (x > 0 and y > 0 and seq1[x] == seq2[y - 1]
                and seq1[x-1] == seq2[y] and seq1[x] != seq2[y]):
                thisrow[y] = min(thisrow[y], twoago[y - 2] + 1)

    return thisrow[len(seq2) - 1]