Implements |
DFA | ||||||
Class Specifications |
this class makes a read-only (non-editable) 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 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. |