module NLP.Adict.Dist
( editDist
) where
import qualified Data.Array as A
import qualified Data.Vector as V
import Data.Ix (range)
import NLP.Adict.Core
editDist :: Cost a -> Word a -> Word a -> Weight
editDist cost x y =
dist' m n
where
dist' i j = distA A.! (i, j)
distA = A.array bounds [(k, uncurry dist k) | k <- range bounds]
bounds = ((0, 0), (m, n))
m = V.length x
n = V.length y
dist 0 0 = 0
dist i 0 = dist' (i1) 0 + (delete cost) i (x#i)
dist 0 j = dist' 0 (j1) + (insert cost) 0 (y#j)
dist i j = minimum
[ dist' (i1) (j1) + (subst cost) i (x#i) (y#j)
, dist' (i1) j + (delete cost) i (x#i)
, dist' i (j1) + (insert cost) i (y#j) ]