Data.DAWG.Frozen

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:

• Keeps all nodes in one array and therefore uses much less memory,
• Constitutes a perfect hash automaton with hash and unHash functions,
• Doesn't provide insert/delete family of operations.

DAWG type

type DAWG a b = Vector (Node (Maybe b))

Root is stored on the first position of the array.

Query

lookup :: Enum a => [a] -> DAWG a b -> Maybe b

Find value associated with the key.

numStates :: DAWG a b -> Int

Number of states in the automaton.

Index

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

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

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

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

Hashing

hash :: Enum a => [a] -> DAWG a b -> Maybe Int

Perfect hashing function for dictionary entries. A synonym for the index function.

unHash :: Enum a => Int -> DAWG a b -> Maybe [a]

Inverse of the hash function and a synonym for the byIndex function.

Construction

empty :: DAWG a b

Empty DAWG.

fromList :: (Enum a, Ord b) => [([a], b)] -> DAWG a b

Construct DAWG from the list of (word, value) pairs. First a DAWG is created and then it is frozen using the freeze function.

fromListWith :: (Enum a, Ord b) => (b -> b -> b) -> [([a], b)] -> DAWG a b

Construct DAWG from the list of (word, value) pairs with a combining function. The combining function is applied strictly. First a DAWG is created and then it is frozen using the freeze function.

fromLang :: Enum a => [[a]] -> DAWG a ()

Make DAWG from the list of words. Annotate each word with the () value. First a DAWG is created and then it is frozen using the freeze function.

Conversion

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

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

keys :: Enum a => DAWG a b -> [[a]]

Return all keys of the DAWG in ascending order.

elems :: DAWG a b -> [b]

Return all elements of the DAWG in the ascending order of their keys.

freeze :: DAWG a b -> DAWG a b

Yield immutable version of the automaton.