Levenshtein距离的Haskell程序

Question

我需要在Haskell中使用一个程序来计算Levenshtein距离.

Answer 1

您需要计算Levenshtein距离(也称为编辑距离),该距离定义为以下字符串a和b:(取自维基百科):

因为lev(i,j)的值仅取决于先前的值,所以我们可以利用Haskell的惰性来初始化一个数组,其中位置(i,j)处的元素值是同一数组的先前值的函数!请参阅动态编程示例以查看如何执行此操作的示例.

这是一个基本的实现lev:

import Data.Array

lev :: String -> String -> Int
lev x y = c ! (m, n)
  where
    c = listArray ((0, 0), (m, n)) [compute i j | i <- [0 .. m], j <- [0 .. n]]
    compute 0 j = j
    compute i 0 = i
    compute i j
      | x !! (i - 1) == y !! (j - 1) = c ! (i - 1, j - 1)
      | otherwise = 1 + (minimum $ map (c !) [(i , j - 1),
                                              (i - 1, j),
                                              (i - 1, j - 1)])
    m = length x
    n = length y

这段代码可以进一步优化,但应该为您提供一个好主意.

在计算Levenshtein之后,您只需将其与编辑成本约束k进行比较.