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
- type ID = Int
- rootID :: DAWG a b c -> ID
- byID :: ID -> DAWG a b c -> Maybe (DAWG a b c)
- lookup :: (Enum a, Unbox b) => [a] -> DAWG a b c -> Maybe c
- edges :: Enum a => DAWG a b c -> [(a, DAWG a b 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 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
The actual DAWG root has the 0 ID. Thanks to the
attribute, we can represent a submap of a DAWG.
Retrieve sub-DAWG with a given ID (or
Nothing, if there's
no such DAWG). This function can be used, together with the
root function, to store IDs rather than entire DAWGs in a
Find value associated with the key.
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.
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.
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
submap function) only a part of the DAWG is currently selected.
Position in a set of all dictionary entries with respect to the lexicographic order.
Find dictionary entry given its index with respect to the lexicographic order.
Return all (key, value) pairs in the DAWG in ascending key order.
Return all keys of the DAWG in ascending order.
Return all elements of the DAWG in the ascending order of their keys.