Octane v1.01.20 - The Open Compression Toolkit for C++

http://octane.sourceforge.net/

SubstringParser Class Reference
[Parsers]

#include <substringparser.hpp>

Inheritance diagram for SubstringParser:

List of all members.

---

Detailed Description

The SubstringParser class is a flexible parser, which uses arbitrarily long substrings of text as symbols.

It can be configured to build a symbol set using only whole words, or with substrings that are not affected by word boundary (max symbol length can be set). Various input parsing strategies can be used, from greedy (fastest) to longest first, to near optimal (slowest). Various heuristics for pruning the symbol set can be applied, which can be used to get the symbol set down to a desired size.

Definition at line 154 of file substringparser.hpp.

Public Member Functions
	SubstringParser ()
	Constructor.
	~SubstringParser ()
	Destructor.
virtual bool	CreateSymbolSetUsingStream (bitreader &from)
	Process (train on) an input stream to update/create a symbol set from it.
virtual bool	IsReadyToParse ()
	are we ready to parse? i.e. has symbol set been built.
virtual bool	RewindAnyBufferedInput (bitreader &from)
	Let go of any buffered stream - this is an odd function that can be called be compressor if it wants to hand off the input stream to a new parser or otherwise access the input bitstream from after last symbol parsed.
virtual void	SynchronizeStateForNewStream ()
	Synchronize state for a new stream - this is called every time a new stream is parsed, to allow parser to get into 'start' state,.
virtual int	GetSymbolCount ()
	Get a count of the number of symbols stored in the parser.
virtual bool	ParseNextSymbolFromInput (bitreader &from, int &symbolnum)
	Parse the next symbol from the input and return its #.
virtual bool	WriteSymbolText (bitwriter &to, int symbolnum, bool &isendofstreamsymbol)
	Parse the next symbol from the input, and set symbolnum to the symbol id#,.
virtual string	LookupSymbolText (int symbolnum)
	Helper function to return the text string of a symbol number.
virtual void	ShowDebuggingInfo ()
	show any debugging info on request (used by various derived classes) [optional]
virtual unsigned int	GetMemoryUsed ()
	Report actual current memory usage (in bytes).
virtual unsigned int	GetDiskspaceUsed (bool fortempdecompressiononly)
	Report disk space (in bytes) that would be used when saving state to file (in bytes).
virtual std::string	GetParametersInformation ()
	Reports information about any parameters available.
virtual void	SetDefaultParameters ()
	Reset any parameters to their default values.
virtual bool	SetParameter (const std::string &parametername, const std::string &parametervalue)
	This function is called to set a variable value.
virtual bool	SaveState (bitwriter &to, bool fortempdecompressiononly)
	Save state of object to output stream (if appropriate).
virtual bool	LoadState (bitreader &from)
	Load state of object from input stream (if appropriate).
int	GetSetSymbolCount ()
int	LookupSymbolNumberFromText (string wordstring)
Protected Types
typedef std::set< SubstringSymbol *, TSubstringSymbolStringGreater< SubstringSymbol * > >	TSymbolSetTYPE
	Typedef for stl set of symbols (used for fast alphabetical lookup).
typedef std::vector< SubstringSymbol * >	TSymbolVectorTYPE
	Typedef for stl vector of symbols (used for fast lookup by id#).
Protected Attributes
TSymbolSetTYPE	symbolset
	STL set of symbols (used for fast alphabetical lookup).
TSymbolVectorTYPE	symbolvector
	STL vector of symbols (used for fast lookup by id#).
TSymbolSetTYPE::iterator	symbolset_pos
	STL set iterator - this is a non-local variable to eliminate cost of building it on stack on every local function.
TSymbolVectorTYPE::iterator	symbolvector_pos
	Stl vector iterator - this is a non-local variable to eliminate cost of building it on stack on every local function.
char	inputbufferstr [SubStrHuff_BiggestSubStringLen]
	Current window buffer for parsing, filled as we read input characters.
int	inputbufferlen
	Length of input window buffer.
bool	senteos
	The parser needs to return an end-of-symbol character before finishing reading the stream, so we need to track whether we sent an EOS yet.
unsigned int	Parameter_MaxSymbols_DuringBuild
	The dictionary will never be allowed to get bigger than this size (smaller will also increase building speed) when this size is exceeded, we will eliminate all symbols with frequencies of smaller than some small #.
unsigned int	Parameter_MaxSymbols_Final
	After the entire training file is parsed, we will repeat pruning steps to reduce it to a *maximum* of this many entries the actual symbols kept may be smaller depending on other pruning parameters.
int	Parameter_MaxSubstringSize
	How many characters is largest (sub)string stored in dictionary.
bool	Parameter_OnlyCodeWholeWords
	Only store characters and whole words?
bool	Parameter_SpanWordBoundaries
	Store Substrings that span words (i.e. they contain multiple words).
bool	Parameter_CountCRsAsEOTs
unsigned int	Parameter_PruneMinimumWeight
	Minimum count for a word or Substring in order to even consider leaving it in the dictionary.
int	Parameter_ParseMode
	We can either use a greedy search to find longest Substring starting with first char or we can use smarter but slower heuristics.
bool	Parameter_UseSmartLookup
	We can either use a smart search using stl find_lower_bound() to find longest Substring or we can search starting at biggest string backwards.
bool	Parameter_PruneReCalculations
	How many iterations should we recompress to test heuristic symbolset cost, if any this tests the currently built symbol set to 'reencode' the input stream and calculates actual usage counts and then reprunes.
int	symbolcount
	Keeps track of how many symbols have we created for fast replies.
int	endofstreamsymbolnum
	Keeps track of end of stream symbol number for fast replies.
bitreader *	current_bitreaderp
	Stores last bitreader , so that we can rewind when we want to reparse and check our heuristic symbolset costs.
size_t	start_bitreaderposition
	Stores last bitreader starting position before parsing, so that we can rewind when we want to reparse and check our heuristic symbolset costs.

---

Member Function Documentation

bool SubstringParser::CreateSymbolSetUsingStream (  bitreader &  from  )  [virtual]

Process (train on) an input stream to update/create a symbol set from it. Returns: true on success Reimplemented from OctaneParser. Definition at line 281 of file substringparser.cpp. References current_bitreaderp, Parameter_MaxSubstringSize, Parameter_MaxSymbols_DuringBuild, start_bitreaderposition, and symbolset. { // scan a file and add its "tokens" into our symbol set string valuestring; string slidingwindowstring; unsigned char c; bool slidingwindowfull=false; string eotstring=string(""); // clear any existing symbols FreeData_Symbols(); // create primitive characters AddPrimitiveCharacterSubstringSymbols(); // save the current bitreader and bitreader position for reparsing during pruning current_bitreaderp = &from; start_bitreaderposition = from.tell_bit(); // now parse the file while (!from.empty()) { // grab a character c=from.get_byte(); // add the character to our window slidingwindowstring+=c; // trim lefthand side if it is too big if (!slidingwindowfull) { // we keep a sliding window which is slightly bigger than the maxSubstring, to account for delimiter boundaries if ((int)(slidingwindowstring.length())>Parameter_MaxSubstringSize+5) { // set the flag saying from now on, we are full slidingwindowfull=true; } } if (slidingwindowfull) { // trim leftmost character slidingwindowstring.erase(0,1); } // now add the appropriate Substrings of slidingwindowstring to our dictionary SymbolSet AddSubstringsFromSlidingWindowString(slidingwindowstring); // when encoding single lines, each line must end with an end-of-stream (EOS) symbol // but if we train on a file, which is large and has only one EOS at end of file // then the freq. of EOS will be very low (1), so here we can say to count a pretend EOS // whenever we see a CR if (c==13 && Parameter_CountCRsAsEOTs) { // increment frequency for EOS UpdateValueStringInSymbolSet(eotstring,1); } if (symbolset.size()>Parameter_MaxSymbols_DuringBuild) { // periodically we may have to prune away lowest frequency symbols in order to keep dictionary manageable // how many should we remove - we don't want to remove just one since that would result in many repetitive calls here // so we just pick some fraction to remove PruneSymbolSet_ReduceSizeTo(((unsigned int)(symbolset.size())/5)+1); } } // now final pruning PruneSymbolSet(); // and now build the vector for fast random access BuildSymbolVector(); // return success return true; }

bool SubstringParser::RewindAnyBufferedInput (  bitreader &  from  )  [virtual]

Let go of any buffered stream - this is an odd function that can be called be compressor if it wants to hand off the input stream to a new parser or otherwise access the input bitstream from after last symbol parsed. it is necessary because some parsers can read-ahead in input buffer, and so must rewind the bitstream. Reimplemented from OctaneParser. Definition at line 258 of file substringparser.cpp. References inputbufferlen, bitreader::seek_bit(), and bitreader::tell_bit(). { // let go of any buffered stream - this is an odd function that can be called be compressor if it wants to hand // off the input stream to a new parser or otherwise access the input bitstream from after last symbol parsed. // it is necessary because some parsers can read-ahead in input buffer, and so must rewind the bitstream. // we have to implement this since we do a read-ahead. note this wouldn't be called in normal circumstances, // just if compressors wants us to stop prematurely and hand off the job to someone else. // return true on success // the number of characters we have read ahead in buffer is inputbufferlen from.seek_bit(from.tell_bit()-(inputbufferlen*8)); return true; }

bool SubstringParser::ParseNextSymbolFromInput (  bitreader &  from, int &  symbolnum )  [virtual]

Parse the next symbol from the input and return its #. Note: The end of stream situation must to be handled specially: When a parser encounters the end of a stream, it *MUST* return a symbol signifying an end-of-stream symbol. This end of stream symbol must be a unique symbol from the symbol set. Returns: false *after* the end of stream symbol is returned on prior call. Implements OctaneParser. Definition at line 362 of file substringparser.cpp. References current_bitreaderp, bitreader::get_byte(), SubstringSymbol::get_symbolvectorpos(), inputbufferlen, inputbufferstr, Parameter_MaxSubstringSize, and senteos. { // grab an input stream symbol and set its INDEX (in symbol vector) for symbolnum // return false after EOS unsigned char c; int maxSubstringlen=Parameter_MaxSubstringSize; SubstringSymbol *symbolp; // note that inputbufferlen are preserved across calls, and inputbufferstr[] is preserved state info // try to fill up the inputqueue to Parameter_MaxSubstringSize size, or as much as we got current_bitreaderp=&from; while (inputbufferlen<maxSubstringlen && !from.empty()) { // add the character c=from.get_byte(); inputbufferstr[inputbufferlen]=c; // increment character positions ++inputbufferlen; } if (inputbufferlen==0) { // no more symbols left - BUT the question now is, do we return an EOS symbol, or false for no symbols left if (senteos) { // we already sent an EOS so from now on any requests for a symbol returns false saying no more symbols available return false; } else { // we are going to drop down to return the EOS signal, but we set flag so we don't do it again senteos=true; } } // ok now we have a block of up to Parameter_MaxSubstringSize bytes from the left of the inputstr // now find the longest leftmost (prefix) Substring in our dictionary and encode it, and shift inputqueuestr to the left with remaining bytes // and return the new inputqueuestr with remaining bytes, and return length of remaining bytes. symbolp=FindNextSymbolToEncode(inputbufferstr,inputbufferlen); // symbolp=FindNextSubstringSymbolpFromInputQueueStr(inputbufferstr,inputbufferlen); symbolnum=symbolp->get_symbolvectorpos(); inputbufferlen=SwallowSymbolFromInputQueueStr(symbolp,inputbufferstr,inputbufferlen,false); return true; }

bool SubstringParser::WriteSymbolText (  bitwriter &  to, int  symbolnum, bool &  isendofstreamsymbol )  [virtual]

Parse the next symbol from the input, and set symbolnum to the symbol id#,. Returns: false *after* end of stream (i.e. first response at end of stream should be the end-of-stream symbol). Implements OctaneParser. Definition at line 409 of file substringparser.cpp. References endofstreamsymbolnum, SubstringSymbol::get_valuep(), symbolvector, and bitwriter::write(). { // write the symbol indexed by symbolnum // sets isendofostreamsymbol to true or false depending on if the symbol written is the EOS symbol // return true on success SubstringSymbol *symbolp=symbolvector[symbolnum]; int valuelength=(int)((symbolp->get_valuep())->length()); to.write((symbolp->get_valuep())->c_str(),valuelength); // set EOS flag isendofstreamsymbol=(symbolnum==endofstreamsymbolnum); // return success return true; }

virtual string SubstringParser::LookupSymbolText (  int  symbolnum  )  [inline, virtual]

Helper function to return the text string of a symbol number. Returns: a string with the text of the symbol Note: this should be the empty string to signify end of stream symbol. Implements OctaneParser. Definition at line 235 of file substringparser.hpp. References GetDiskspaceUsed(), GetMemoryUsed(), GetParametersInformation(), LoadState(), SaveState(), SetDefaultParameters(), SetParameter(), ShowDebuggingInfo(), and symbolset. {assert(symbolnum<(int)(symbolvector.size()));return symbolvector[symbolnum]->get_value();};

bool SubstringParser::SetParameter (  const std::string &  parametername, const std::string &  parametervalue )  [virtual]

This function is called to set a variable value. Note: this can be called with a variable not owned by this class, in which case the function should return false. Returns: true if the variable was found (whether it was set properly or not). Reimplemented from OctaneClass. Definition at line 178 of file substringparser.cpp. References Parameter_MaxSubstringSize, Parameter_MaxSymbols_DuringBuild, Parameter_MaxSymbols_Final, Parameter_OnlyCodeWholeWords, Parameter_ParseMode, Parameter_PruneMinimumWeight, Parameter_PruneReCalculations, Parameter_SpanWordBoundaries, Parameter_UseSmartLookup, and OctaneClass::ParseParameter(). Referenced by LookupSymbolText(). { // generic function for user-interactive modification of parameters // (see SetDefaultDictionaryBuildingParameters implementation for descriptions) // return true if we know this variable and use it bool bretv=false; if (parametername=="maxbuildsymbols") bretv=ParseParameter(parametervalue,Parameter_MaxSymbols_DuringBuild); else if (parametername=="maxsymbols") bretv=ParseParameter(parametervalue,Parameter_MaxSymbols_Final); else if (parametername=="maxSubstring") bretv=ParseParameter(parametervalue,Parameter_MaxSubstringSize); else if (parametername=="onlywords") bretv=ParseParameter(parametervalue,Parameter_OnlyCodeWholeWords); else if (parametername=="spanwords") bretv=ParseParameter(parametervalue,Parameter_SpanWordBoundaries); else if (parametername=="crends") bretv=ParseParameter(parametervalue,Parameter_CountCRsAsEOTs); else if (parametername=="minweight") bretv=ParseParameter(parametervalue,Parameter_PruneMinimumWeight); else if (parametername=="smartlookup") bretv=ParseParameter(parametervalue,Parameter_UseSmartLookup); else if (parametername=="parsemode") bretv=ParseParameter(parametervalue,Parameter_ParseMode); else if (parametername=="recalculations") bretv=ParseParameter(parametervalue,Parameter_PruneReCalculations); return bretv; }

bool SubstringParser::SaveState (  bitwriter &  to, bool  fortempdecompressiononly )  [virtual]

Save state of object to output stream (if appropriate). Returns: true on success (or if no information needs to be saved). Reimplemented from OctaneClass. Definition at line 55 of file substringparser.cpp. Referenced by LookupSymbolText(). { // save state // return true on success bool bretv; bretv=SaveParameters(to); if (bretv) bretv=SaveSymbols(to); return bretv; }

bool SubstringParser::LoadState (  bitreader &  from  )  [virtual]

Load state of object from input stream (if appropriate). Returns: true on success (or if no information needs to be loaded). Reimplemented from OctaneClass. Definition at line 66 of file substringparser.cpp. Referenced by LookupSymbolText(). { // load state // return true on success bool bretv; bretv=LoadParameters(from); if (bretv) bretv=LoadSymbols(from); return bretv; }

---

Member Data Documentation

bool SubstringParser::senteos [protected]

The parser needs to return an end-of-symbol character before finishing reading the stream, so we need to track whether we sent an EOS yet. Todo: this is an odd responsibility for the parser to have to deal with, so we should probably find a way to eliminate this. Definition at line 175 of file substringparser.hpp. Referenced by ParseNextSymbolFromInput(), SubstringParser(), and SynchronizeStateForNewStream().

---

The documentation for this class was generated from the following files:

• parsers/parser_substring/substringparser.hpp
• parsers/parser_substring/substringparser.cpp

 

Generated on 20 May 2004 by doxygen 1.3.3