Optimierung der Damerau Version des levenshtein Algorithmus besser als O (n * m)

Question

Hier ist der Algorithmus (in Rubin) ist

#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 

Mein Problem ist, dass mit einer seq1 der Länge 780 und seq2 der Länge 7238 dauert dies etwa 25 Sekunden, um auf einem i7-Laptop zu laufen. Im Idealfall möchte ich das auf eine Sekunde reduzieren, da es als Teil einer Webapp läuft.

Ich fand, dass there is a way to optimize the vanilla levenshtein distance so, dass die Laufzeit von O (n * m) nach O (n + d^2) fällt, wobei n die Länge der längeren Zeichenfolge und d die Bearbeitungsdistanz ist. So, meine Frage wird, kann die gleiche Optimierung auf die Dameau-Version angewendet werden, die ich habe (oben)?

Answer 1

Ja, die Optimierung kann auf die Damereau-Version angewendet werden. Hier ist ein Haskell Code, dies zu tun (ich weiß nicht, Rubin):

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) 

Der obige Code ist eine Adaption von this code.