аюсь реализовать расстояние Левенштейна (или редактировать расстояние) в Haskell, но его производительность быстро уменьшается при увеличении длины строки.

Я все еще новичок в Haskell, поэтому было бы неплохо, если бы вы могли дать мне несколько советов о том, как я могу улучшить алгоритм. Я уже пытался «предварительно вычислить» значения (inits), но так как это ничего не изменило, я отменил это изменение.

Я знаю, что уже естьeditDistance Реализация на Hackage, но мне нужно, чтобы он работал со списками произвольных токенов, не обязательно строк. Кроме того, я нахожу это немного сложным, по крайней мере, по сравнению с моей версией.

Итак, вот код:

-- 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
                                   ]

Кажется, это правильная реализация, по крайней мере, она дает точно такие же результаты, как этаонлайн инструмент.

Заранее спасибо за вашу помощь! Если вам нужна дополнительная информация, пожалуйста, дайте мне знать.

Привет, бзн