DFA_COMPACT

Implements	DFA
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)
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 read-only 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.