previousnext
ASTL homeSTL home
DFA_tr


Implements

DFA

Class Specifications

name DFA_tr
template parameters class _Sigma = Type_alphabet<char>,
class _Tag = empty_tag,
class Allocator = default_allocator
constructor DFA_tr(unsigned long = 0, Allocator a = Allocator())

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.