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

Question

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

我对 Haskell 还是很陌生，所以如果你能给我一些关于如何改进算法的建议，那就太好了。我已经尝试过“预先计算”值(初始化)，但由于它没有改变任何东西，所以我恢复了那个改变。

我知道已经有 editDistance在 Hackage 上实现，但我需要它来处理任意 token 列表，不一定是字符串。另外，我觉得它有点复杂，至少与我的版本相比。

所以，这里是代码:

-- 两个列表之间的标准 levenshtein 距离
editDistance::Eq a => [a] -> [a] -> Int
编辑距离 s1 s2 = 编辑距离' 1 1 1 s1 s2

-- 加权 levenshtein 距离
-- ins、sub 和 del 是各种操作的成本
editDistance'::Eq a => Int -> Int -> Int -> [a] -> [a] -> Int
editDistance' _ _ ins s1 [] = ins * 长度 s1
编辑距离'_ _ ins [] s2 = ins * 长度s2
editDistance' del sub ins s1 s2
| last s1 == last s2 = editDistance' del sub ins (init s1) (init s2)
|否则 = 最小值 [editDistance' del sub ins s1 (init s2) + del -- 删除
, editDistance' del sub ins (init s1) (init s2) + sub -- 替换
, editDistance' del sub ins (init s1) s2 + ins -- 插入
]

这似乎是一个正确的实现，至少它给出了与 online tool 完全相同的结果.

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

问候，
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 至少可以是惰性的)。所有这些操作都是使用 Vector 的 O(1)。

虽然真正的基准测试应该使用 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 )，您基本上可以毫不费力地获得内存。编码:

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
                                   ]

您看到记忆化如何需要一个“键”(请参阅​​ MonadMemo 类)？我将所有参数打包成一个又大又丑的元组。它还需要一个“值”，即您生成的 Int 。然后它只是使用“备忘录”功能即插即用您想要内存的值。

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

$ time ./so  # the memoized vector version
12

real    0m0.003s

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

real    1m33.122s

甚至不要考虑运行非内存字符串版本，我认为它至少需要大约 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 的调用会导致对 editDistance' 的 3 次调用......每个调用 editDistance' 又调用了 3 次......又调用了 3 次......和 ​​AHHH!指数爆炸!幸运的是，大多数电话都是相同的!例如(使用 --> 表示“通话”，使用 eD 表示 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) 执行了 3 次。另一个 child 也与 parent 分享电话，所有 child 彼此分享许多电话(和他们的 child ，提示 Monty Python 短剧)。

制作一个类似 runMemo 的函数来返回所使用的缓存结果的数量将是一个有趣的，也许是有启发性的练习。