document.write('
def dameraulevenshtein(seq1, seq2):\n    """Calculate the Damerau-Levenshtein distance between sequences.\n\n    This distance is the number of additions, deletions, substitutions,\n    and transpositions needed to transform the first sequence into the\n    second. Although generally used with strings, any sequences of\n    comparable objects will work.\n\n    Transpositions are exchanges of *consecutive* characters; all other\n    operations are self-explanatory.\n\n    This implementation is O(N*M) time and O(M) space, for N and M the\n    lengths of the two sequences.\n\n    >>> dameraulevenshtein('ba', 'abc')\n    2\n    >>> dameraulevenshtein('fee', 'deed')\n    2\n\n    It works with arbitrary sequences too:\n    >>> dameraulevenshtein('abcd', ['b', 'a', 'c', 'd', 'e'])\n    2\n    """\n    # codesnippet:D0DE4716-B6E6-4161-9219-2903BF8F547F\n    # Conceptually, this is based on a len(seq1) + 1 * len(seq2) + 1 matrix.\n    # However, only the current and two previous rows are needed at once,\n    # so we only store those.\n    oneago = None\n    thisrow = range(1, len(seq2) + 1) + [0]\n    for x in xrange(len(seq1)):\n        # Python lists wrap around for negative indices, so put the\n        # leftmost column at the *end* of the list. This matches with\n        # the zero-indexed strings and saves extra calculation.\n        twoago, oneago, thisrow = oneago, thisrow, [0] * len(seq2) + [x + 1]\n        for y in xrange(len(seq2)):\n            delcost = oneago[y] + 1\n            addcost = thisrow[y - 1] + 1\n            subcost = oneago[y - 1] + (seq1[x] != seq2[y])\n            thisrow[y] = min(delcost, addcost, subcost)\n            # This block deals with transpositions\n            if (x > 0 and y > 0 and seq1[x] == seq2[y - 1]\n                and seq1[x-1] == seq2[y] and seq1[x] != seq2[y]):\n                thisrow[y] = min(thisrow[y], twoago[y - 2] + 1)\n    return thisrow[len(seq2) - 1]\n
\n

paste from gytha.org. Raw text.

');