Data.DAWG

The module provides implementation of directed acyclic word graphs (DAWGs) also known as minimal acyclic finite-state automata. The implementation provides fast insert and delete operations which can be used to build the DAWG structure incrementaly.

Documentation

data DAWG a

A Graph with one root from which all other graph nodes should be accesible.

Constructors

DAWG

Fields

graph :: !(Graph (Maybe a))

root :: !Id

Instances

Eq a => Eq (DAWG a)

(Eq (DAWG a), Ord a) => Ord (DAWG a)

Show a => Show (DAWG a)

(Binary a, Ord a) => Binary (DAWG a)

empty :: Ord a => DAWG a

Empty DAWG.

numStates :: DAWG a -> Int

Number of states in the underlying graph.

insert :: Ord a => String -> a -> DAWG a -> DAWG a

Insert the (key, value) pair into the DAWG.

delete :: Ord a => String -> DAWG a -> DAWG a

Delete the key from the DAWG.

lookup :: String -> DAWG a -> Maybe a

Find value associated with the key.

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

Construct DAWG from the list of (word, value) pairs.

fromLang :: [String] -> DAWG ()

Make DAWG from the list of words. Annotate each word with the () value.