Levenshtein距离成本

Question

我是haskell的新手,我遇到了一个非常严重的性能问题,它必须是我的代码,而不是haskell平台.

我有一个Levenshtein距离(自己的代码)的python实现,我通过(或试图这样做)这个到haskell.结果如下:

bool2int :: Bool -> Int
bool2int True = 1
bool2int False = 0

levenshtein :: Eq a => [a] -> [a] -> Int -> Int -> Int
levenshtein u v 0 0 = 0
levenshtein u v i 0 = i
levenshtein u v 0 j = j
levenshtein u v i j = minimum [1 + levenshtein u v i (j - 1),
    1 + levenshtein u v (i - 1) j,
    bool2int (u !! (i - 1) /= v !! (j - 1) ) + levenshtein u v (i - 1) (j - 1) ]

distance :: Eq a => [a] -> [a] -> Int
distance u v = levenshtein u v (length u) (length v)

现在,长度为10或更长的字符串的执行时间差异在python和haskell之间具有10的各种幂.还有一些粗略的时间测量(挂钟,因为到目前为止我还没有在haskell中找到clock()命令),似乎我的haskell实现没有花费O(mn),但是其他一些其他快速增长的成本.

Nota bene:我不希望我的haskell实现与python脚本快速竞争.我只是希望它在一个"合理的"时间内运行,而不是整个宇宙存在的倍数.

问题:

• 我做错了什么,我的实施是如此缓慢？
• 怎么解决？
• 谈论"懒惰的评价":我认为如果levenshtein "cat" "kit" 2 2被称为三次,它只计算一次.这是正确的吗？
• 我的bool2int必须内置一些东西,对吧？
• 任何其他输入都非常受欢迎,如果它推动我在掌握haskell的艰难道路上前进.

编辑:这里是python代码进行比较:

#! /usr/bin/python3.2
# -*- coding, utf-8 -*-

class Levenshtein:
        def __init__ (self, u, v):
                self.__u = ' ' + u
                self.__v = ' ' + v
                self.__D = [ [None for x in self.__u] for x in self.__v]
                for x, _ in enumerate (self.__u): self.__D [0] [x] = x
                for x, _ in enumerate (self.__v): self.__D [x] [0] = x

        @property
        def distance (self):
                return self.__getD (len (self.__v) - 1, len (self.__u) - 1)

        def __getD (self, i, j):
                if self.__D [i] [j] != None: return self.__D [i] [j]
                self.__D [i] [j] = min ( [self.__getD (i - 1, j - 1) + (0 if self.__v [i] == self.__u [j] else 1),
                                  self.__getD (i, j - 1) + 1,
                                  self.__getD (i - 1, j) + 1] )
                return self.__D [i] [j]

print (Levenshtein ('first string', 'second string').distance)

Answer 1

我做错了什么,我的实施是如此缓慢？

您的算法具有指数复杂性.你好像假设这些电话都是为你记忆的,但事实并非如此.

怎么解决？

您需要添加显式memoization,可能使用数组或其他方法.

谈论"懒惰的评价":我认为如果levenshtein "cat" "kit" 2 2被称为三次,它只计算一次.这是正确的吗？

不,Haskell不进行自动记忆.懒惰意味着如果你这样做let y = f x in y + y,那么f x只有在要求总和的结果时才会评估遗嘱(一次).它并不意味着f x + f x将只有一个调用来评价f x.当您想要从子表达式共享结果时,您必须明确.

我必须有内置的东西bool2int,对吗？

是的,有一个instance Enum Bool,所以你可以使用fromEnum.

*Main> fromEnum True
1
*Main> fromEnum False
0

任何其他输入都非常受欢迎,如果它推动我在掌握haskell的艰难道路上前进.

虽然从头开始编写内容可能既有趣又有教育意义,但在做类似常见的事情时,学习利用Hackage上的许多优秀库是很重要的.

例如,在编辑距离包中存在Levenshtein距离的实现.

我将您的Haskell代码翻译回Python进行比较:

def levenshtein(u, v, i, j):
    if i == 0: return j
    if j == 0: return i

    return min(1 + levenshtein(u, v, i, (j-1)),
               1 + levenshtein(u, v, (i-1), j),
               (u[i-1] != v[j-1]) + levenshtein(u, v, (i-1), (j-1)))

def distance(u, v):
    return levenshtein(u, v, len(u), len(v))

if __name__ == "__main__":
    print distance("abbacabaab", "abaddafaca")

即使没有修复chrisdb在他的回答中指出的O(n)索引问题,这在编译时比Haskell版本执行速度慢:

$ time python levenshtein.py
6

real    0m4.793s
user    0m4.690s
sys 0m0.020s

$ time ./Levenshtein 
6

real    0m0.524s
user    0m0.520s
sys 0m0.000s

当然,他们都输入了编辑距离包中正确记忆的版本:

$ time ./LevenshteinEditDistance 
6

real    0m0.015s
user    0m0.010s
sys 0m0.000s

这是一个简单的memoized实现,使用Data.Array:

import Data.Array

distance u v = table ! (m, n)
   where table = listArray ((0, 0), (m, n)) [levenshtein i j | i <- [0..m], j <- [0..n]]

         levenshtein 0 j = j
         levenshtein i 0 = i
         levenshtein i j = minimum [ 1 + table!(i, j-1)
                                   , 1 + table!(i-1, j)
                                   , fromEnum (u'!(i-1) /= v'!(j-1)) + table!(i-1, j-1) ]

         u' = listArray (0, m-1) u
         v' = listArray (0, n-1) v

         m = length u
         n = length v

main = print $ distance "abbacabaab" "abaddafaca"

它的执行方式与原始Python代码类似:

$ time python levenshtein-original.py 
6

real    0m0.037s
user    0m0.030s
sys 0m0.000s
$ time ./LevenshteinArray 
6

real    0m0.017s
user    0m0.010s
sys 0m0.000s