使用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

然而，记忆化似乎没有任何效果，尽管我希望任何记忆化都会对运行时间有显着的改进，因为它至少是多项式的。我的实施有什么问题吗？如何获得良好的运行时间，同时尽可能保留编辑距离的高级定义？

Answer 1

如果您发布的代码实际上就是您正在做的事情，那么您就做错了！:-)。如果要记忆递归函数，则需要将对递归版本的调用回调到记忆版本中。例如：

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

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

这里还有另一个问题。 elm 的备忘录表不应依赖于它的参数（理想情况下，您甚至不应该提及这些参数，因此您不依赖于足够智能的编译器来找出依赖项）。如果备忘录表取决于参数，那么您必须为每个不同的参数构建一个新表，并且我们需要为所有参数共享一个表。您可以尝试一些愚蠢的事情，例如记住参数的整个结构：

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

看看这是否会加快速度（结合前一个技巧）。然后，您可以继续尝试仅使用长度而不是整个列表结构来获得额外的提升。

希望有帮助。