Estoy tratando de implementar la distancia levenshtein (o la distancia de edición) en Haskell, pero su rendimiento disminuye rápidamente cuando aumenta la longitud de la cuerda.

Todavía soy bastante nuevo en Haskell, por lo que sería bueno que me dieras algunos consejos sobre cómo podría mejorar el algoritmo. Ya intenté "precalcular" los valores (los inits), pero como no cambió nada, revertí ese cambio.

Sé que ya hay una editDistance implementación en Hackage, pero necesito que funcione en listas de tokens arbitrarios, no necesariamente cadenas. Además, me resulta un poco complicado, al menos en comparación con mi versión.

Entonces, aquí está el código:

-- standard levenshtein distance between two lists
editDistance      :: Eq a => [a] -> [a] -> Int
editDistance s1 s2 = editDistance' 1 1 1 s1 s2 

-- weighted levenshtein distance
-- ins, sub and del are the costs for the various operations
editDistance'      :: Eq a => Int -> Int -> Int -> [a] -> [a] -> Int
editDistance' _ _ ins s1 [] = ins * length s1 
editDistance' _ _ ins [] s2 = ins * length s2 
editDistance' del sub ins s1 s2  
    | last s1 == last s2 = editDistance' del sub ins (init s1) (init s2)
    | otherwise          = minimum [ editDistance' del sub ins s1 (init s2)        + del -- deletion 
                                   , editDistance' del sub ins (init s1) (init s2) + sub -- substitution
                                   , editDistance' del sub ins (init s1) s2        + ins -- insertion
                                   ]

Parece ser una implementación correcta, al menos da exactamente los mismos resultados que esta herramienta en línea.

¡Gracias de antemano por tu ayuda! Si necesita información adicional, hágamelo saber.

Greetings, bzn