mwh.geek.nz

def dameraulevenshtein(seq1, seq2):
    """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
    """
    # codesnippet:D0DE4716-B6E6-4161-9219-2903BF8F547F
    # Conceptually, this is based on a len(seq1) + 1 * len(seq2) + 1 matrix.
    # However, only the current and two previous rows are needed at once,
    # so we only store those.
    oneago = None
    thisrow = range(1, len(seq2) + 1) + [0]
    for x in xrange(len(seq1)):
        # Python lists wrap around for negative indices, so put the
        # leftmost column at the *end* of the list. This matches with
        # the zero-indexed strings and saves extra calculation.
        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]

11 Responses to “Python Damerau-Levenshtein distance implementation”

1. Joseph Reagle says:

   October 10, 2009 at 03:47

   Thanks for this. It is faster than: http://www.guyrutenberg.com/2008/12/15/damerau-levenshtein-distance-in-python/comment-page-1/
2. Joseph Reagle says:

   October 10, 2009 at 04:48

   btw: Any idea how to get a ratio function (normalization) akin to that in difflib? I tried: return float((max_length – DL_distance(seq1, seq2)) / max_length)

   but it’s not as nice as the one in difflib.
3. numerix says:

   May 25, 2010 at 00:56

   J. Reagle is right according to the speed of the algorithm, but the algorithms doesn’t work correctly.
   You find more information about that in my comment to this code: http://www.guyrutenberg.com/2008/12/15/damerau-levenshtein-distance-in-python/comment-page-1/
4. Michael says:

   May 25, 2010 at 15:49

   numerix, it works perfectly well. You need to note the difference between the Levenshtein distance (described in the SPOJ problem and the calculator you link to) and the Damerau-Levenshtein distance, which allows transpositions.

   Both algorithms give the correct answer for that pair: delete H, U, R, replace B with K, transpose O and H, replace P with Z. Six steps.
5. numerix says:

   May 28, 2010 at 02:12

   Thanks Michael, for pointing that out. I was not aware of that difference!
6. flow says:

   August 8, 2010 at 10:00

   i am trying to convert your code to Cython and have already obtained 20x speed gains. sadly, my translation still has some problems; so i opened a question on http://stackoverflow.com/questions/3431933/how-to-correct-algorithm-malloc-related-bugs-in-this-damerau-levenshtein-edit-di
7. OneEyedMan says:

   January 21, 2011 at 07:36

   I wanted to port this to be compatible with Python 3. I’m new to 3 myself, but I think I’ve pulled it off by checking a few strings across both the versions.
   Here are the changes:
   1) thisrow = range(1, len(seq2) + 1) + [0]
   becomes
   thisrow = list(range(1, len(seq2) + 1)) + [0]
   2) for x in xrange(len(seq1)):
   becomes
   for x in range(len(seq1)):
   3) for y in xrange(len(seq2)):
   becomes
   for y in range(len(seq2)):

   I checked ‘spam’ vs. ham (2)
   ‘hasddddddddddddddddam’ vs ‘ham’ (18)
   Here is the full updated code:
   ____________________________________________
   def dameraulevenshtein(seq1, seq2):
   “”"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
   “”"
   # codesnippet:D0DE4716-B6E6-4161-9219-2903BF8F547F
   # Conceptually, this is based on a len(seq1) + 1 * len(seq2) + 1 matrix.
   # However, only the current and two previous rows are needed at once,
   # so we only store those.
   oneago = None
   thisrow = list(range(1, len(seq2) + 1)) + [0]
   for x in range(len(seq1)):
   # Python lists wrap around for negative indices, so put the
   # leftmost column at the *end* of the list. This matches with
   # the zero-indexed strings and saves extra calculation.
   twoago, oneago, thisrow = oneago, thisrow, [0] * len(seq2) + [x + 1]
   for y in range(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]
8. Michael says:

   January 21, 2011 at 10:47

   Thanks, OneEyedMan. Those changes should be all that’s required, and they’re what 2to3 will give you if you’re converting automatically. The Python 3 version should run fine on Python 2 as well, with just a little waste around the range() calls.
9. emmaespina says:

   February 1, 2011 at 04:59

   [...] the previus listing I have to make some remarks. In line 2 and 3 we use third party libraries for levenshtain distance and metaphone algorithms. In line 8 we are collecting a list of 70 candidates. This particular [...]
10. Lucid Imagination » Creating a spellchecker with Solr says:

    April 16, 2011 at 11:27

    [...] the previous listing I have to make some remarks. In line 2 and 3 we use third party libraries for Levenshtein distance and metaphone algorithms. In line 8 we are collecting a list of 70 candidates. This particular [...]
11. denny says:

    June 5, 2012 at 08:58

    added to beginning:
    seq1 = seq1.translate(string.maketrans(“”,”"), string.punctuation).upper()
    seq2 = seq2.translate(string.maketrans(“”,”"), string.punctuation).upper()

    to remove punctuation marks and case from the equation.