'Calculate the Damerau-Levenshtein distance between sequences.
This distance is the number of additions, deletions, substitutions,
and transpositions needed to transform the first sequence into the
second. Although generally used with strings, any sequences of
comparable objects will work.
Transpositions are exchanges of *consecutive* characters; all other
operations are self-explanatory.
This implementation is O(N*M) time and O(M) space, for N and M the
lengths of the two sequences.
>>> dameraulevenshtein(\'ba\', \'abc\')
2
>>> dameraulevenshtein(\'fee\', \'deed\')
2
It works with arbitrary sequences too:
>>> dameraulevenshtein(\'abcd\', [\'b\', \'a\', \'c\', \'d\', \'e\'])
2'

def dameraulevenshtein(self, seq1, seq2):

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