Seeing how lately the levenschtein distance is so popular, I thought I'd add a haskell version to the mix.
The code below is pretty self-explanatory, using the typical memoization pattern. I do wonder, however, what would happen if somehow GHC supported lazily-resizable arrays. Perhaps then you could do this on infinite lists and only ask the levenschtein distance up to a certain index.module Lev where
import Data.Array
levenshtein :: (Eq a) => [a] -> [a] -> Integer
levenshtein xs ys = arr ! (lenx, leny)
where arr :: (Array (Int, Int) Integer)
arr = array ((0,0), (lenx, leny))
[((ix, iy), worker ix iy) |
ix <- [0..lenx], iy <- [0..leny] ]
lenx = length xs
leny = length ys
arrx = listArray (1, lenx) xs
arry = listArray (1, leny) ys
worker 0 iy = fromIntegral iy
worker ix 0 = fromIntegral ix
worker ix iy = minimum [1 + arr ! (ix-1, iy),
1 + arr ! (ix, iy-1),
cost ix iy + arr ! (ix-1, iy-1)]
cost ix iy = if (arrx ! ix) == (arry ! iy) then 0 else 1
Thursday, April 24, 2008
Levenshtein Distance in Haskell
Subscribe to:
Post Comments (Atom)
4 comments:
this is a little bit shorter and faster:
levenshtein sa sb = last $ foldl (transform sa) [0..length sa] sb
where
transform str xs@(x:xs') c = res
where
res = x+1 : zipWith4 compute str xs xs' res
compute c' x y z = minimum [y+1, z+1, x + if c' == c then 0 else 1]
Interesting code :) Rather cryptic, I must admit.
if c' == c then 0 else 1
can also be written
fromEnum (c /= c')
if you don't like inline ifs :-)
Small improvements on jorpic's version:
levenshtein sa sb = last $ foldl transform [0..length sa] sb where
transform xs@(x:xs') c = scanl compute (x+1) (zip3 sa xs xs') where
compute z (c', x, y) = minimum [y+1, z+1, x + fromEnum (c' /= c)]
Post a Comment