相关疑难解决方法(0)

我正在尝试在Haskell中实现levenshtein距离(或编辑距离),但是当字符串长度增加时,它的性能会迅速下降.

我仍然是Haskell的新手,所以如果你能就我如何改进算法给我一些建议会很好.我已经尝试"预先计算"值(inits),但由于它没有改变任何东西,我还原了那个改变.

我知道Hackage上已有一个editDistance实现,但是我需要它来处理任意标记的列表,而不一定是字符串.另外,我发现它有点复杂,至少与我的版本相比.

那么,这是代码:

-- 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' _ …