next up previous
Next: Hashing table Up: Automaton Representations Previous: Adjacency list by maps

Single vector (compact representation)

This representation ranks number one in low space consuming and fast retrieval of transitions: we merge in a single vector all lines of a matrix, taking advantage of the remaining empty cells of the previous transitions. Generally the context size of state is much lower than the alphabet size (occupation ratio is low), making this representation very efficient in most cases. The drawback is major : a compact representation does not support side effect operations on the automaton and thus can only be constructed by copy.

Vincent Lemaout