编辑Haskell中的距离算法 - 性能调优

Question

我正在尝试在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' _ _ 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
                                   ]

它似乎是一个正确的实现,至少它提供与此在线工具完全相同的结果.

在此先感谢您的帮助!如果您需要任何其他信息,请告诉我们.

问候,bzn

Answer 1

忽略这是一个糟糕的算法(应该记住,我到达那一秒)......

使用O(1)基元而不是O(n)

一个问题是你对列表使用O(n)的整串调用(haskell列表是单链表).一个更好的数据结构将给你O(1)操作,我使用Vector:

import qualified Data.Vector as V

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

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

列表的O(n)操作包括init,length和last(尽管init至少可以是惰性的).所有这些操作都是O(1)使用Vector.

虽然真正的基准测试应该使用Criterion,一个快速而肮脏的基准:

str2 = replicate 15 'a' ++ replicate 25 'b'
str1 = replicate 20 'a' ++ replicate 20 'b'
main = print $ editDistance str1 str2

显示矢量版本需要0.09秒而字符串需要1.6秒,因此我们甚至没有查看您的editDistance算法就节省了大约一个数量级.

那么记忆结果怎么样？

更大的问题显然是需要进行记忆.我把这作为学习monad-memo包的机会- 我的上帝真棒!对于一个额外的约束(你需要Ord a),你基本上没有努力得到一个memoization.代码:

import qualified Data.Vector as V
import Control.Monad.Memo

-- standard levenshtein distance between two lists
editDistance      :: (Eq a, Ord a) => [a] -> [a] -> Int
editDistance s1 s2 = startEvalMemo $ editDistance' (1, 1, 1, (V.fromList s1), (V.fromList s2))

-- weighted levenshtein distance
-- ins, sub and del are the costs for the various operations
editDistance' :: (MonadMemo (Int, Int, Int, V.Vector a, V.Vector a) Int m, Eq a) => (Int, Int, Int, V.Vector a, V.Vector a) -> m Int
editDistance' (del, sub, ins, s1, s2)
  | V.null s2 = return $ ins * V.length s1
  | V.null s1 = return $ ins * V.length s2
  | V.last s1 == V.last s2 = memo editDistance' (del, sub, ins, (V.init s1), (V.init s2))
  | otherwise = do
        r1 <- memo editDistance' (del, sub, ins, s1, (V.init s2))
        r2 <- memo editDistance' (del, sub, ins, (V.init s1), (V.init s2))
        r3 <- memo editDistance' (del, sub, ins, (V.init s1), s2)
        return $ minimum [ r1 + del -- deletion 
                         , r2 + sub -- substitution
                         , r3 + ins -- insertion
                                   ]

你看到memoization如何需要一个"key"(参见MonadMemo类)？我将所有参数打包成一个丑陋的大元组.它还需要一个"值",这是你的结果Int.然后它只是使用"备忘录"功能即插即用,以便您想要记忆的值.

对于基准测试,我使用了更短但更大距离的字符串:

$ time ./so  # the memoized vector version
12

real    0m0.003s

$ time ./so3  # the non-memoized vector version
12

real    1m33.122s

甚至不考虑运行非memoized字符串版本,我认为它至少需要大约15分钟.至于我,我现在喜欢monad-memo - 感谢Eduard这个包!

编辑:String和Vector记忆版本之间的区别并没有那么多,但是当距离达到200左右时仍然会增长到2倍,所以仍值得.

编辑:也许我应该解释为什么更大的问题"显然"记忆结果.好吧,如果你看看原始算法的核心:

 [ editDistance' ... s1          (V.init s2)  + del 
 , editDistance' ... (V.init s1) (V.init s2) + sub
 , editDistance' ... (V.init s1) s2          + ins]

很明显,editDistance' s1 s2在3次调用中调用结果editDistance'......每次调用editDistance'三次......还有三次调用......和AHHH!指数爆炸!幸运的是,大多数电话都是相同的!例如(-->用于"调用"和eDfor editDistance'):

eD s1 s2  --> eD s1 (init s2)             -- The parent
            , eD (init s1) s2
            , eD (init s1) (init s2)
eD (init s1) s2 --> eD (init s1) (init s2)         -- The first "child"
                  , eD (init (init s1)) s2
                  , eD (init (init s1)) (init s2) 
eD s1 (init s2) --> eD s1 (init (init s2))
                  , eD (init s1) (init s2)
                  , eD (init s1) (init (init s2))

只要考虑父母和两个直接的孩子,我们就可以看到电话ed (init s1) (init s2)完成了三次.另一个孩子也与父母分享了呼叫,并且所有孩子彼此共享许多呼叫(以及他们的孩子,提示Monty Python短剧).

使用runMemo类似的函数返回所使用的缓存结果的数量将是一个有趣的,也许是有益的练习.

Answer 2

你需要记住editDistance'.有许多方法可以做到这一点,例如,递归定义的数组.