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 speed-up only if the probability for each transition to be accessed are not uiform. |