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 module the automaton implemented here:

- newtype DAWG a b c = DAWG {}
- lookup :: (Unbox c, Enum a) => [a] -> DAWG a b c -> Maybe b
- numStates :: DAWG a b c -> Int
- index :: Enum a => [a] -> DAWG a b Weight -> Maybe Int
- byIndex :: Enum a => Int -> DAWG a b Weight -> Maybe [a]
- hash :: Enum a => [a] -> DAWG a b Weight -> Maybe Int
- unHash :: Enum a => Int -> DAWG a b Weight -> Maybe [a]
- empty :: Unbox c => 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 :: Unbox c => DAWG a b c -> DAWG a b Weight
- assocs :: (Enum a, Unbox c) => DAWG a b c -> [([a], b)]
- keys :: (Unbox c, Enum a) => DAWG a b c -> [[a]]
- elems :: Unbox c => DAWG a b c -> [b]

# DAWG type

`DAWG a b c`

constitutes an automaton with alphabet symbols of type *a*,
node values of type *Maybe b* and additional transition labels of type *c*.
Root is stored on the first position of the array.

# Query

lookup :: (Unbox c, Enum a) => [a] -> DAWG a b c -> Maybe bSource

Find value associated with the key.

# Index

index :: Enum a => [a] -> DAWG a b Weight -> Maybe IntSource

Position in a set of all dictionary entries with respect to the lexicographic order.

byIndex :: Enum a => Int -> DAWG a b Weight -> Maybe [a]Source

Find dictionary entry given its index with respect to the lexicographic order.

# Hash

hash :: Enum a => [a] -> DAWG a b Weight -> 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 b ()Source

# 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 :: Unbox c => DAWG a b c -> DAWG a b WeightSource

Compute node weights and store corresponding values in transition labels.

# Conversion

assocs :: (Enum a, Unbox c) => DAWG a b c -> [([a], b)]Source

Return all key/value pairs in the DAWG in ascending key order.