Safe Haskell | None |
---|
The module implements directed acyclic word graphs (DAWGs) internaly represented as minimal acyclic deterministic finite-state automata.
In comparison to Data.DAWG.Dynamic module the automaton implemented here:
- data DAWG a b c
- lookup :: (Enum a, Unbox b) => [a] -> DAWG a b c -> Maybe c
- numStates :: DAWG a b c -> Int
- numEdges :: DAWG a b c -> Int
- index :: Enum a => [a] -> DAWG a Weight c -> Maybe Int
- byIndex :: Enum a => Int -> DAWG a Weight c -> Maybe [a]
- hash :: Enum a => [a] -> DAWG a Weight c -> Maybe Int
- unHash :: Enum a => Int -> DAWG a Weight c -> Maybe [a]
- empty :: Unbox b => DAWG a b c
- fromList :: (Enum a, Ord b) => [([a], b)] -> DAWG a () b
- fromListWith :: (Enum a, Ord b) => (b -> b -> b) -> [([a], b)] -> DAWG a () b
- fromLang :: Enum a => [[a]] -> DAWG a () ()
- freeze :: DAWG a b -> DAWG a () b
- type Weight = Int
- weigh :: DAWG a b c -> DAWG a Weight c
- assocs :: (Enum a, Unbox b) => DAWG a b c -> [([a], c)]
- keys :: (Enum a, Unbox b) => DAWG a b c -> [[a]]
- elems :: Unbox b => DAWG a b c -> [c]
DAWG type
DAWG a b c
constitutes an automaton with alphabet symbols of type a,
transition labels of type b and node values of type Maybe c.
All nodes are stored in a Vector
with positions of nodes corresponding
to their ID
s.
Query
lookup :: (Enum a, Unbox b) => [a] -> DAWG a b c -> Maybe cSource
Find value associated with the key.
Index
index :: Enum a => [a] -> DAWG a Weight c -> Maybe IntSource
Position in a set of all dictionary entries with respect to the lexicographic order.
byIndex :: Enum a => Int -> DAWG a Weight c -> Maybe [a]Source
Find dictionary entry given its index with respect to the lexicographic order.
Hash
hash :: Enum a => [a] -> DAWG a Weight c -> Maybe IntSource
Perfect hashing function for dictionary entries.
A synonym for the index
function.
Construction
fromListWith :: (Enum a, Ord b) => (b -> b -> b) -> [([a], b)] -> DAWG a () bSource
Weight
Weight of a node corresponds to the number of final states reachable from the node. Weight of an edge is a sum of weights of preceding nodes outgoing from the same parent node.
weigh :: DAWG a b c -> DAWG a Weight cSource
Compute node weights and store corresponding values in transition labels.
Conversion
assocs :: (Enum a, Unbox b) => DAWG a b c -> [([a], c)]Source
Return all key/value pairs in the DAWG in ascending key order.