packages feed

adict 0.1.0 → 0.2.0

raw patch · 7 files changed

+144/−45 lines, 7 filesdep +PSQueuedep −pqueue

Dependencies added: PSQueue

Dependencies removed: pqueue

Files

+ NLP/Adict.hs view
@@ -0,0 +1,61 @@+-- | This module exports main data types and functions of the adict library.++module NLP.Adict+(+-- * Dictionary representation+-- $data-structures++-- ** Trie+  Trie (..)+, TrieD+, fromList+, implicitDAWG++-- ** Directed acyclic word graph+, DAWG (..)+, Row (..)+, DAWGD+, fromTrie+, fromDAWG+) where++import NLP.Adict.Trie (Trie (..), TrieD, fromList, implicitDAWG)+import NLP.Adict.DAWG (DAWG (..), Row (..), DAWGD, fromTrie, fromDAWG)++{- $data-structures++  The library provides two basic data structures used for dictionary+  representation. The first one is a 'Trie', which can be constructed +  from a list of dictionary entries by using the 'fromList' function.++  The trie can be translated into a directed acyclic word graph ('DAWG')+  using the 'fromTrie' function (for the moment it is done in an+  inefficient manner, though). ++  There is also a possibility of constructing an implicit DAWG, i.e. a DAWG+  which is algebraically represented by a trie with sharing of common subtries,+  by using the 'implicitDAWG' function (which is also inefficient right now;+  in fact, the 'fromTrie' function uses this one underneath).++  Finally, the DAWG can be transformed back to a trie (implicit DAWG) using+  the 'fromDAWG' function.++-}++--   2. Approximate search and cost representation+--    * Plain cost function+--    * Cost components divided with respect to weight+-- +--   There are to ways of representing the cost function, depending on+--   the searching algorithm you are planning to use.  If you want to+--   find all matches within the given distance of the query word,+--   use the 'findAll' function with cost function represented by the+--   'Cost' structure.+-- +--   If, however, only the nearest match is needed you can use the+--   'findNearest' function. The shortest-path-search algorithm in the+--   background is optimized to use the more find-grained, 'CostDiv'+--   structure for cost representation. See the '...' module for the+--   details about how such a cost function can be constructed.+-- +-- -}
NLP/Adict/Core.hs view
@@ -16,13 +16,13 @@ x#i = x V.! (i-1) {-# INLINE (#) #-} --- | Word with 'a' character type.+-- | A word parametrized with character type 'a'. type Word a = V.Vector a --- | Position.+-- | Position in a sentence. type Pos = Int --- | Cost of edit operation.  It has to be non-negative!+-- | Cost of edit operation.  It has to be a non-negative value! type Weight = Double  -- | Cost represents a cost (or weight) of a symbol insertion, deletion or
NLP/Adict/DAWG.hs view
@@ -3,6 +3,9 @@ module NLP.Adict.DAWG ( DAWGD , DAWG (..)+, fromTrie+, fromDAWG+ , size , row , Row (..)@@ -22,13 +25,28 @@ import qualified Data.Vector as V  import NLP.Adict.DAWG.Node+import qualified NLP.Adict.Trie as Trie +-- | A DAWGD dictionary is a 'DAWG' which may have the 'Nothing' value+-- along the path from the root to a leave. type DAWGD a b = DAWG a (Maybe b) +-- | A directed acyclic word graph with character type @a@ and dictionary+-- entry type @b@. data DAWG a b = DAWG-    { root  :: Int-    , array :: V.Vector (Row a b) }+    { root  :: Int                  -- ^ Root (index) of the DAWG+    , array :: V.Vector (Row a b)   -- ^ Vector of DAWG nodes+    } +-- | Find and eliminate all common subtries in the input trie+-- and return the trie represented as a DAWG.+fromTrie :: (Ord a, Ord b) => Trie.Trie a b -> DAWG a b+fromTrie = deserialize . Trie.serialize++-- | Transform the DAWG to implicit DAWG in a form of a trie.+fromDAWG :: Ord a => DAWG a b -> Trie.Trie a b+fromDAWG = Trie.deserialize . serialize+ size :: DAWG a b -> Int size = V.length . array {-# INLINE size #-}@@ -37,9 +55,14 @@ row dag k = array dag V.! k {-# INLINE row #-} -data Row a b = Row-    { rowValue :: b-    , rowEdges :: V.Vector (a, Int) }+-- | A Row represents one node of the DAWG.+data Row a b = Row {+    -- | Value in the node.+    rowValue :: b, +    -- | Edges to subnodes (represented by array indices)+    -- annotated with characters.+    rowEdges :: V.Vector (a, Int)+    }  valueIn :: DAWG a b -> Int -> b valueIn dag k = rowValue (array dag V.! k)
NLP/Adict/Graph.hs view
@@ -7,8 +7,7 @@ , IsEnd ) where -import Data.Function (on)-import qualified Data.PQueue.Min as P+import qualified Data.PSQueue as P import qualified Data.Map as M  -- | Adjacent list for a given node @n. We assume, that the list@@ -19,53 +18,55 @@ -- | Is @n node an ending node? type IsEnd n = n -> Bool --- | Non-empty list of adjacent nodes given in ascending order.--- We use new data type to implement custom Eq and Ord instances.+-- | Non-empty list of adjacent nodes given in an ascending order. data Adj n w = Adj     { from :: n     , to   :: [(w, n)] }-    deriving Show+    deriving (Show, Eq, Ord) +-- | First element from the the adjacent list, which is also+-- a priority in the priority queue. proxy :: Adj n w -> (w, n) proxy = head . to {-# INLINE proxy #-} +-- | Tail elements from the adjacent list. folls :: Adj n w -> [(w, n)] folls = tail . to {-# INLINE folls #-} -instance (Eq n, Eq w) => Eq (Adj n w) where-    (==) = (==) `on` proxy--instance (Ord n, Ord w) => Ord (Adj n w) where-    compare = compare `on` proxy+-- | Priority queue.+type PQ n w = P.PSQ (Adj n w) (w, n)  -- | Remove minimal edge (from, weight, to) from the queue.-minView :: (Ord n, Ord w) => P.MinQueue (Adj n w)-        -> Maybe (Edge n w, P.MinQueue (Adj n w))+minView :: (Ord n, Ord w) => PQ n w -> Maybe (Edge n w, PQ n w) minView queue = do-    (adj, queue') <- P.minView queue+    (adj P.:-> (w, q), queue') <- P.minView queue     let p       = from adj-        (w, q)  = proxy adj         e       = (p, w, q)     return (e, push queue' p (folls adj)) -push :: (Ord n, Ord w) => P.MinQueue (Adj n w) -> n-     -> [(w, n)] -> P.MinQueue (Adj n w)+push :: (Ord n, Ord w) => PQ n w -> n -> [(w, n)] -> PQ n w push queue _ [] = queue-push queue p xs = P.insert (Adj p xs) queue+push queue p xs = insert (Adj p xs) queue+{-# INLINE push #-} --- | Find shortes path from a beginning node to any ending node.-minPath :: (Show n, Show w, Ord n, Ord w, Num w, Fractional w)+insert :: (Ord n, Ord w) => Adj n w -> PQ n w -> PQ n w+insert x = P.insert x (proxy x)+{-# INLINE insert #-}++-- | Find the shortest path from the beginning node to one+-- of the ending nodes.+minPath :: (Ord n, Ord w, Num w, Fractional w)         => w -> Edges n w -> IsEnd n -> n -> Maybe ([n], w) minPath threshold edgesFrom isEnd beg = -    shortest M.empty $ P.singleton (Adj beg [(0, beg)])+    shortest M.empty $ insert (Adj beg [(0, beg)]) P.empty    where -    -- | @visited -- set of visited nodes.-    --   @queue -- priority queue,+    -- @visited: set of visited nodes+    -- @queue: priority queue     shortest visited queue = do         (edge, queue') <- minView queue         shortest' visited queue' edge
NLP/Adict/Nearest.hs view
@@ -45,7 +45,7 @@  -- | We can check, if CostDiv satisfies basic properties.  On the other -- hand, we do not do this for plain Cost function.-search :: Show a => CostDiv a -> Double -> Word a -> DAWGD a b -> Maybe ([a], b, Double)+search :: CostDiv a -> Double -> Word a -> DAWGD a b -> Maybe ([a], b, Double) search cost z x dag = do     (xs, w) <- minPath z edgesFrom isEnd (Node (root dag) 0 Nothing)     let form = catMaybes . map nodeChar $ xs
NLP/Adict/Trie.hs view
@@ -21,7 +21,7 @@  , serialize , deserialize-, toDAWG+, implicitDAWG ) where  import Prelude hiding (lookup)@@ -33,12 +33,17 @@  import NLP.Adict.DAWG.Node +-- | A 'Trie' with 'Maybe' values in nodes. type TrieD a b = Trie a (Maybe b) -data Trie a b = Trie-    { valueIn :: b-    , edgeMap :: M.Map a (Trie a b) }-    deriving (Show, Eq, Ord)+-- | A trie of words with character type @a@ and entry type @b@.  It can be+-- thought of as a map of type @[a] -> b@.+data Trie a b = Trie {+    -- | Value in the node.+    valueIn :: b,                  +    -- | Edges to subtries annotated with characters.+    edgeMap :: M.Map a (Trie a b)+    } deriving (Show, Eq, Ord)  instance Functor (Trie a) where     fmap f Trie{..} = Trie (f valueIn) (fmap (fmap f) edgeMap)@@ -106,6 +111,7 @@ lookup :: Ord a => [a] -> TrieD a b -> Maybe b lookup xs t = follow xs t >>= valueIn +-- | Construct the 'Trie' from the list of (word, value) pairs. fromList :: Ord a => [([a], b)] -> TrieD a b fromList xs =     let update t (x, v) = insert x v t@@ -123,9 +129,14 @@ fromLang :: Ord a => [[a]] -> TrieD a () fromLang xs = fromList [(x, ()) | x <- xs] -toDAWG :: (Ord a, Ord b) => Trie a b -> Trie a b-toDAWG = deserialize . serialize+-- | Elminate common subtries.  The result is algebraically a trie+-- but is represented as a DAWG in memory.+implicitDAWG :: (Ord a, Ord b) => Trie a b -> Trie a b+implicitDAWG = deserialize . serialize +-- | Serialize the trie and eliminate all common subtries+-- along the way.  TODO: perhaps the function name should+-- be different? serialize :: (Ord a, Ord b) => Trie a b -> [Node a b] serialize r =     [ mkNode (valueIn t)@@ -137,7 +148,7 @@     m' = M.fromList [(y, x) | (x, y) <- M.toList m]  -- | FIXME: Null node list case.-deserialize :: (Ord a, Ord b) => [Node a b] -> Trie a b+deserialize :: Ord a => [Node a b] -> Trie a b deserialize =     snd . M.findMax . foldl' update M.empty   where
adict.cabal view
@@ -1,5 +1,5 @@ name:               adict-version:            0.1.0+version:            0.2.0 synopsis:           Approximate dictionary searching description:     Approximate dictionary searching library.@@ -16,23 +16,26 @@  library     build-depends:-        base >= 4 && < 5+        base >= 4 && <= 5       , containers       , vector       , array-      , pqueue+      , PSQueue >= 1.1 && < 1.2       , binary      exposed-modules:-        NLP.Adict.Core+        NLP.Adict+      , NLP.Adict.Core       , NLP.Adict.CostDiv       , NLP.Adict.Dist       , NLP.Adict.Brute       , NLP.Adict.Trie-      , NLP.Adict.DAWG.Node       , NLP.Adict.DAWG-      , NLP.Adict.Graph       , NLP.Adict.Basic++    other-modules:+        NLP.Adict.Graph+      , NLP.Adict.DAWG.Node       , NLP.Adict.Nearest      ghc-options: -Wall -O2