Implements 
DFA  
Class Specifications 


File 
dfa_tr.h  
Structure 
This is one of the three arrays DFA. In thes representation, we store the outgoing transitions of a state in an array of couples in Sigma*Q. they are to be used when space memory constraints are strong since they are the least consumming structures. Structure is the same as DFA_mtf but here the heuristic is slightly different: once found, the transition is swapped with the immediatly preceding one, thus organizing the transitions in decreasing order of use, this is supposed to be the best heuristic for naturaly decreasing probabilities. F is a bit vector. 

time 
Add Remove state: O(1)
Addtransition:amortized O(1) Access transition: +/ O(c) Iteration on edges: O(c) 

Space 

Use Cases 
Similar to DFA_mtf. of course, the two techniques provide a sensitive speedup only if the probability for each transition to be accessed are not uiform. 