Haskell程序Levenshtein距离

Question

我需要一个程序在Haskell计算Levenshtein distance。

Answer 1

你需要计算Levenshtein距离（也称为编辑距离），这被定义为跟随字符串a和b：（从Wikipedia拍摄）：

因为列夫（值我，j）只依赖于以前的值，我们可以利用Haskell的懒惰来初始化一个Array，其中位置（i，j）处的元素值是同一个数组的先前值的函数！请参阅Dynamic programming example以查看如何完成此操作的示例。

这里去一个基本实施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进行比较。