Safe Haskell | None |
---|---|
Language | Haskell2010 |
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,
- When
weigh
ed, it can be used to perform static hashing withhash
andunHash
functions, - Doesn't provide insert/delete family of operations.
Transition backend has to be specified by a type signature. You can import the desired transition type and define your own dictionary construction function.
import Data.DAWG.Static import Data.DAWG.Trans.Map (Trans) mkDict :: (Enum a, Ord b) => [([a], b)] -> DAWG Trans a Weight b mkDict = weigh . fromList
Synopsis
- data DAWG t a b c
- lookup :: (Enum a, Trans t, Unbox b) => [a] -> DAWG t a b c -> Maybe c
- numStates :: DAWG t a b c -> Int
- index :: (Enum a, Trans t) => [a] -> DAWG t a Weight c -> Maybe Int
- byIndex :: (Enum a, Trans t) => Int -> DAWG t a Weight c -> Maybe [a]
- hash :: (Enum a, Trans t) => [a] -> DAWG t a Weight c -> Maybe Int
- unHash :: (Enum a, Trans t) => Int -> DAWG t a Weight c -> Maybe [a]
- empty :: (Trans t, Unbox b) => DAWG t a b c
- fromList :: (Enum a, MkNode t b) => [([a], b)] -> DAWG t a () b
- fromListWith :: (Enum a, MkNode t b) => (b -> b -> b) -> [([a], b)] -> DAWG t a () b
- fromLang :: (Enum a, MkNode t ()) => [[a]] -> DAWG t a () ()
- freeze :: Trans t => DAWG t a b -> DAWG t a () b
- type Weight = Int
- weigh :: Trans t => DAWG t a b c -> DAWG t a Weight c
- assocs :: (Enum a, Trans t, Unbox b) => DAWG t a b c -> [([a], c)]
- keys :: (Enum a, Trans t, Unbox b) => DAWG t a b c -> [[a]]
- elems :: (Trans t, Unbox b) => DAWG t a b c -> [c]
DAWG type
DAWG t a b c
constitutes an automaton with alphabet symbols of type a,
transition labels of type b and node values of type Maybe c, implemented
on top of the Trans
t backend. All nodes are stored in a Vector
with positions of nodes corresponding to their ID
s.
Instances
(Eq b, Eq c, Unbox b) => Eq (DAWG Trans a b c) Source # | |
(Ord b, Ord c, Unbox b) => Ord (DAWG Trans a b c) Source # | |
Defined in Data.DAWG.Static compare :: DAWG Trans a b c -> DAWG Trans a b c -> Ordering # (<) :: DAWG Trans a b c -> DAWG Trans a b c -> Bool # (<=) :: DAWG Trans a b c -> DAWG Trans a b c -> Bool # (>) :: DAWG Trans a b c -> DAWG Trans a b c -> Bool # (>=) :: DAWG Trans a b c -> DAWG Trans a b c -> Bool # max :: DAWG Trans a b c -> DAWG Trans a b c -> DAWG Trans a b c # min :: DAWG Trans a b c -> DAWG Trans a b c -> DAWG Trans a b c # | |
(Unbox b, Show t, Show b, Show c) => Show (DAWG t a b c) Source # | |
(Binary t, Binary b, Binary c, Unbox b) => Binary (DAWG t a b c) Source # | |
Query
lookup :: (Enum a, Trans t, Unbox b) => [a] -> DAWG t a b c -> Maybe c Source #
Find value associated with the key.
Index
index :: (Enum a, Trans t) => [a] -> DAWG t a Weight c -> Maybe Int Source #
Position in a set of all dictionary entries with respect to the lexicographic order.
byIndex :: (Enum a, Trans t) => Int -> DAWG t a Weight c -> Maybe [a] Source #
Find dictionary entry given its index with respect to the lexicographic order.
Hash
hash :: (Enum a, Trans t) => [a] -> DAWG t a Weight c -> Maybe Int Source #
Perfect hashing function for dictionary entries.
A synonym for the index
function.
Construction
freeze :: Trans t => DAWG t a b -> DAWG t a () b Source #
Construct immutable version of the automaton.
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 :: Trans t => DAWG t a b c -> DAWG t a Weight c Source #
Compute node weights and store corresponding values in transition labels.
Conversion
assocs :: (Enum a, Trans t, Unbox b) => DAWG t a b c -> [([a], c)] Source #
Return all key/value pairs in the DAWG in ascending key order.