Implements 
DFA  
Class Specifications 
this class makes a readonly (noneditable) but really fast and compact DFA from an other one.


File 
dfa_compact.h  
Structure 
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 readonly automaton because of its particular structure.


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

Space 

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. 