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
- submap :: (Enum a, Unbox b) => [a] -> DAWG a b c -> DAWG a b c
- numStates :: DAWG a b c -> Int
- numEdges :: DAWG a b c -> Int
- type Weight = Int
- weigh :: DAWG a b c -> DAWG a Weight c
- size :: DAWG a Weight c -> Int
- index :: Enum a => [a] -> DAWG a Weight c -> Maybe Int
- byIndex :: 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 () ()
- 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]
- freeze :: DAWG a b -> DAWG a () b
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.
submap :: (Enum a, Unbox b) => [a] -> DAWG a b c -> DAWG a b cSource
Return the sub-DAWG containing all keys beginning with a prefix. The in-memory representation of the resultant DAWG is the same as of the original one, only the pointer to the DAWG root will be different.
numStates :: DAWG a b c -> IntSource
Number of states in the automaton.
TODO: The function ignores the root
value, it won't work properly
after using the submap
function.
numEdges :: DAWG a b c -> IntSource
Number of edges in the automaton.
TODO: The function ignores the root
value, it won't work properly
after using the submap
function.
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.
Be aware, that the entire DAWG will be weighted, even when (because of the use of
the submap
function) only a part of the DAWG is currently selected.
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.
Construction
fromListWith :: (Enum a, Ord b) => (b -> b -> b) -> [([a], b)] -> DAWG a () bSource
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.
keys :: (Enum a, Unbox b) => DAWG a b c -> [[a]]Source
Return all keys of the DAWG in ascending order.