使用Data.Memocombinators实现编辑距离算法

Question

假设我想要实现通常用于Levensthein距离（编辑距离）的动态规划算法。很容易想到递归：

editDistance [] ys = length ys
editDistance xs [] = length xs
editDistance (x:xs) (y:ys) 
  | x == y = editDistance xs ys
  | otherwise = minimum [
      1 + editDistance xs (y:ys),
      1 + editDistance (x:xs) ys,
      1 + editDistance xs ys]

这个函数的运行时间呈指数级增长，因此有必要进行记忆化处理。我想使用Data.Memocombinators来实现，已经尝试了几种方法。以下是我的当前尝试：

import qualified Data.MemoCombinators as M

memLength str = 
  M.wrap 
    (\i -> drop i str) 
    (\xs -> length str - length xs)
    (M.arrayRange (0,length str))

elm xs ys = (M.memo2 memListx memListy editDistance) xs ys
  where
    memListx = memLength xs
    memListy = memLength ys

然而，备忘录似乎没有任何作用，尽管我期望任何备忘录都会显着提高运行时间，因为它至少是多项式的。我的实现有什么问题？如何在尽可能保留编辑距离高级定义的同时获得良好的运行时间？

- HaskellElephant

Answer 1

如果您发布的代码确实是您正在执行的操作，那么您就做错了！:-)。如果您要备忘递归函数，则需要将递归版本的调用回调到备忘版本中。例如：

editDistance (x:xs) (y:ys)
  | x == y = elm xs ys
  | ...

否则，您需要做完整的递归计算并仅存储最终结果。 您需要存储中间结果。

这里还有另一个问题。 elm 的备忘录表不应该依赖于其参数（理想情况下，您甚至不应该提到参数，这样就不会依赖于编译器聪明到足以找出依赖项）。 如果备忘录表依赖于参数，则必须为每个不同的参数构建新表，并且我们需要为所有参数共享一个表。 您可以尝试像对整个参数结构进行记忆化的愚蠢操作：

elm = M.memo2 (M.list M.char) (M.list M.char)

看看是否加入前面的技巧可以加速它。然后，您可以尝试仅使用长度而不是整个列表结构来获得额外的提升。

希望这有所帮助。

- luqui

---

你知道吗，这实际上就是问题所在，现在看起来非常明显 =D。 - HaskellElephant