NLP.Adict.DAWG

A directed acyclic word graph.

Documentation

data DAWG a b

A directed acyclic word graph with character type a and dictionary entry type b. Each node is represented by a unique integer number which is also an index of the node in the vector of DAWG nodes.

Constructors

DAWG

Fields

root :: Int

Root (index) of the DAWG

nodes :: Vector (Node a b)

Vector of DAWG nodes

Instances

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

data Node a b

A node in the DAWG.

Constructors

Node

Fields

valueIn :: b

Value in the node.

subNodes :: Vector (a, Int)

Edges to subnodes (represented by DAWG node indices) annotated with characters.

type DAWGM a b = DAWG a (Maybe b)

A DAWGM is a DAWG with Maybe values in nodes.

fromTrie :: (Ord a, Ord b) => Trie a b -> DAWG a b

Find and eliminate all common subtries in the input trie and return the trie represented as a DAWG.

fromDAWG :: Ord a => DAWG a b -> Trie a b

Transform the DAWG to implicit DAWG in a form of a trie.