module NLP.Adict.Basic
( search
) where
import Data.Ix (range)
import qualified Data.Array as A
import qualified Data.Vector as V
import NLP.Adict.Core
import NLP.Adict.Trie hiding (insert)
search :: Cost a -> Double -> Word a -> TrieD a b -> [([a], b, Double)]
search cost k x trie =
foundHere ++ foundLower
where
foundHere
| dist' m <= k = case valueIn trie of
Just y -> [([], y, dist' m)]
Nothing -> []
| otherwise = []
foundLower
| minimum (A.elems distV) > k = []
| otherwise = concatMap searchLower $ anyChild trie
searchLower = search' cost k dist' x
dist' = (A.!) distV
distV = A.array bounds [(i, dist i) | i <- range bounds]
bounds = (0, m)
m = V.length x
dist 0 = 0
dist i = dist' (i1) + (delete cost) i (x#i)
search' :: Cost a -> Double -> (Int -> Double)
-> Word a -> (a, TrieD a b) -> [([a], b, Double)]
search' cost k distP x (c, trie) =
foundHere ++ map appendChar foundLower
where
foundHere
| dist' m <= k = case valueIn trie of
Just y -> [([c], y, dist' m)]
Nothing -> []
| otherwise = []
foundLower
| minimum (A.elems distV) > k = []
| otherwise = concatMap searchLower $ anyChild trie
searchLower = search' cost k dist' x
appendChar (cs, y, w) = ((c:cs), y, w)
dist' = (A.!) distV
distV = A.array bounds [(i, dist i) | i <- range bounds]
bounds = (0, m)
m = V.length x
dist 0 = distP 0 + (insert cost) 0 c
dist i = minimum
[ distP (i1) + (subst cost) i (x#i) c
, dist' (i1) + (delete cost) i (x#i)
, distP i + (insert cost) i c ]