Optimizing the damerau version of the levenshtein algorithm to better than O(n*m)

Question

Here is the algorithm (in ruby)

#http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance
  def self.dameraulevenshtein(seq1, seq2)
      oneago = nil
      thisrow = (1..seq2.size).to_a + [0]
      seq1.size.times do |x|
          twoago, oneago, thisrow = oneago, thisrow, [0] * seq2.size + [x + 1]
          seq2.size.times do |y|
              delcost = oneago[y] + 1
              addcost = thisrow[y - 1] + 1
              subcost = oneago[y - 1] + ((seq1[x] != seq2[y]) ? 1 : 0)
              thisrow[y] = [delcost, addcost, subcost].min
              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] = [thisrow[y], twoago[y-2] + 1].min
              end
          end
      end
      return thisrow[seq2.size - 1]
  end

My problem is that with a seq1 of length 780, and seq2 of length 7238, this takes about 25 seconds to run on an i7 laptop. Ideally, I'd like to get this reduced to about a second, since it's running as part of a webapp.

I found that there is a way to optimize the vanilla levenshtein distance such that the runtime drops from O(n*m) to O(n + d^2) where n is the length of the longer string, and d is the edit distance. So, my question becomes, can the same optimization be applied to the damerau version I have (above)?

Have you looked at [Levenshtein Automata](http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata)? — dbenhur, Mar 29 '12 at 00:17
Do you need to know the exact distance, or just if the distance is under some threshold? The former is much harder than the latter. — Nick Johnson, Mar 29 '12 at 09:27

score 0 · Answer 1 · answered May 05 '12 at 15:50

Yes the optimization can be applied to the damereau version. Here is a haskell code to do this (I don't know Ruby):

distd :: Eq a => [a] -> [a] -> Int
distd a b
    = last (if lab == 0 then mainDiag
            else if lab > 0 then lowers !! (lab - 1)
                 else{- < 0 -}   uppers !! (-1 - lab))
    where mainDiag = oneDiag a b (head uppers) (-1 : head lowers)
          uppers = eachDiag a b (mainDiag : uppers) -- upper diagonals
          lowers = eachDiag b a (mainDiag : lowers) -- lower diagonals
          eachDiag a [] diags = []
          eachDiag a (bch:bs) (lastDiag:diags) = oneDiag a bs nextDiag lastDiag : eachDiag a bs diags
              where nextDiag = head (tail diags)
          oneDiag a b diagAbove diagBelow = thisdiag
              where doDiag [_] b nw n w = []
                    doDiag a [_] nw n w = []
                    doDiag (apr:ach:as) (bpr:bch:bs) nw n w = me : (doDiag (ach:as) (bch:bs) me (tail n) (tail w))
                        where me = if ach == bch then nw else if ach == bpr && bch == apr then nw else 1 + min3 (head w) nw (head n)
                    firstelt = 1 + head diagBelow
                    thisdiag = firstelt : doDiag a b firstelt diagAbove (tail diagBelow)
          lab = length a - length b
          min3 x y z = if x < y then x else min y z

distance :: [Char] -> [Char] -> Int
distance a b = distd ('0':a) ('0':b)

The code above is an adaptation of this code.

Optimizing the damerau version of the levenshtein algorithm to better than O(n*m)

1 Answers1