Re: State transition table compression, and search in compression structure
On Oct 24, 10:31 pm, Alexander Zezulinsky <palgol...@gmail.com> wrote:
I code state transition table with such structure:
0 1 2 3 4 5 6 7.... //states
'a' 1 8 8 8 9 8 1 76 ....//next states
'b' 1
'c'
//'a','b','c',.. transition term
- It has 128 symbols (rows) and less then 65536 states(cols);
- 8 is initial transition ("error state" for this table);
- table can have various richness;
(50% table richness = if 65536/2 * 128 = 32768 * 128 transitions is
unerror transitions, we added it's to table after it's
initialization).
I implemented table as a array (128*65536) unsigned short.
There are two ideas to compress such structure:
1. RLE compress method (Run-length encoding);
(State, Length)
2. Edge list;
(CurState, NextState)
or
('symbol', NextState)
Adding states for edge structure without initial error (excess)
states.
For fast search we can segmentate 'a','b',... symbol segments or
0,1,... segments.
Task:
We must provide low memory costs with various table richness % and
fast search in compress table structure.
Questions:
How can i compress transition table structure effectively with low
memory costs and fast performance search time?
You can store the transitions in a sorted vector and use binary search
to find the transition from the current state upon a particular event.
This way undefined transitions do not use any memory.
Something like this:
#include <vector>
#include <algorithm>
struct transition
{
unsigned short state_current, state_next;
unsigned char event;
// order by { state_current, event }
bool operator<(transition const& b) const
{
return state_current == b.state_current
? event < b.event
: state_current < b.state_current
;
}
};
struct transition_table
{
typedef std::vector<transition> transitions;
mutable transitions transitions_;
mutable bool sorted_ : 1;
transition_table()
: sorted_(false)
{}
void transition_add(unsigned short from, unsigned char event,
unsigned short to)
{
transition t = { from, to, event };
transitions_.push_back(t);
sorted_ = false;
}
// return NULL if not found
transition const* transition_find(unsigned short
state_current, unsigned char event) const
{
if(!sorted_) { // sort on first search
std::sort(transitions_.begin(), transitions_.end());
sorted_ = true;
}
transition needle = { state_current, 0, event };
// use binary search
transitions::const_iterator i =
std::lower_bound(transitions_.begin(), transitions_.end(), needle);
return i != transitions_.end() && i->state_current ==
state_current && i->event == event
? &*i
: NULL
;
}
};
--
Max
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]