NLP.Adict.DAWG

Documentation

type DAWGD a b = DAWG a (Maybe b)

A DAWGD dictionary is a DAWG which may have the Nothing value along the path from the root to a leave.

data DAWG a b

A directed acyclic word graph with character type a and dictionary entry type b.

Constructors

DAWG

Fields

root :: Int

Root (index) of the DAWG

array :: Vector (Row a b)

Vector of DAWG nodes

Instances

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

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.

size :: DAWG a b -> Int

row :: DAWG a b -> Int -> Row a b

data Row a b

A Row represents one node of the DAWG.

Constructors

Row

Fields

rowValue :: b

Value in the node.

rowEdges :: Vector (a, Int)

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

entry :: DAWG a (Maybe b) -> [Int] -> Maybe ([a], b)

charOn :: DAWG a b -> (Int, Int) -> Maybe a

valueIn :: DAWG a b -> Int -> b

edges :: DAWG a b -> Int -> [(a, Int)]

edgeOn :: Eq a => DAWG a b -> Int -> a -> Maybe Int

serialize :: Ord a => DAWG a b -> [Node a b]

deserialize :: Ord a => [Node a b] -> DAWG a b

Assumptiom: root node is last in the serialization list.