ASTL homeSTL home




Class Specifications

this class makes a read-only (non-editable) but really fast and compact DFA from an other one.
name DFA_compact
template parameters class DFA,
class tag_mapping_object_function = identity<typename DFA::Tag>,
class Allocator = default_allocator
constructor DFA_compact(const DFA &dfa, long opt_value = 0)




This class uses a single vector to store all of its transitions. It stores pairs in (Sigma,Q) and is constructed by copying an already buit DFA. We merge in this vector all lines of the matrix representation, taking advantage of the unused cells of preceding lines. States are given a new name: an integer designating the first cell of the transitions which are retrieved by adding to this integer an offset corresponding to the transition letter. F is a bit vector. Watch out: a DFA_compact is a read-only automaton because of its particular structure.


Add/Remove state: not Supported
Add/Remove transitions: not supported
Access transition: O(1)
Iteration on edges: O(Sigma)


Use Cases

As we can see in DFA_matrix, the resulting matrix is often very sparse, hence the idea to reuse the empty cells to save memory space. Like matrix representation, it requires that a mapping from Sigma to integers exists and iteration on edge should be avoided on large alphabets.
Compacting prcess, to be efficient, needs an average context size lower than the alphabet size. Moreover, the more the transitions are unevenly spread, the better. The drawback is major: a compact representation do not support side effect operations and thus is often used in static dictionnary implementation.