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

http://octane.sourceforge.net/

parsers/parser_substring/substringparser.cpp

Go to the documentation of this file.

//---------------------------------------------------------------------------

//---------------------------------------------------------------------------
// Application includes
#include "substringparser.hpp"
// System includes
#include <iostream>
#include <iomanip>
#include <string>
//---------------------------------------------------------------------------




//---------------------------------------------------------------------------
SubstringParser::SubstringParser()
{
        // constructor
        // initialize default dictionary-building parameters
        SetDefaultParameters();
        // initialize our current symbol count and end-of-stream-symbol
        symbolcount=0;
        endofstreamsymbolnum=-1;
        // initialize input buffer pos
        inputbufferlen=0;
        senteos=false;
}

SubstringParser::~SubstringParser()
{
        // destructor frees the SubstringSymbols in symbolset
        FreeData();
}
//---------------------------------------------------------------------------



//---------------------------------------------------------------------------
// OCTANE PUBLIC API - AUXILIARY FUNCTIONS
bool SubstringParser::SaveState(bitwriter &to,bool fortempdecompressiononly)
{
        // save state
        // return true on success
        bool bretv;
        bretv=SaveParameters(to);
        if (bretv)
                bretv=SaveSymbols(to);
        return bretv;
}

bool SubstringParser::LoadState(bitreader &from)
{
        // load state
        // return true on success
        bool bretv;
        bretv=LoadParameters(from);
        if (bretv)
                bretv=LoadSymbols(from);
        return bretv;
}


unsigned int SubstringParser::GetMemoryUsed()
        {
        // return memory used by this data structure
        unsigned int memoryused=sizeof(this);

        // this returns the size of the symbolset, as it would take up on disk if saved in straightforward way
        //  memory usage will be almost identical.
        memoryused+=sizeof(symbolset);
        // write entries in compact binary form
        for (symbolset_pos=symbolset.begin();symbolset_pos!=symbolset.end();++symbolset_pos)
                {
                memoryused+=sizeof(*symbolset_pos);
                memoryused+=(*symbolset_pos)->get_memoryused();
                }
        // for vector
        for (symbolvector_pos=symbolvector.begin();symbolvector_pos!=symbolvector.end();++symbolvector_pos)
                memoryused+=sizeof(*symbolvector_pos);
        
        return memoryused;
        }


unsigned int SubstringParser::GetDiskspaceUsed(bool fortempdecompressiononly)
{
        // this returns the size of the symbolset, as it would take up on disk if saved in straightforward way
        //  memory usage will be almost identical.
        unsigned int memoryused=0;

        // byte for file type (see WriteSymbolSet routine)
        memoryused+=1;
        
        // write entries in compact binary form
        for (symbolset_pos=symbolset.begin();symbolset_pos!=symbolset.end();++symbolset_pos)
                {
                // length of the string
                memoryused+=1;
                // write string
                memoryused+=(unsigned int)(((*symbolset_pos)->get_valuep())->length());
                // weight of symbol
                memoryused+=sizeof(unsigned short int);
                }

        // end-of-header
        memoryused+=1;
        return memoryused;
}




void SubstringParser::ShowDebuggingInfo()
{
        // show some debugging info
        using namespace std;
        string bitset_string;
        string value;

        // size of tree is
        std::cout << " Memory used by SubStringParser: " << GetMemoryUsed() << " bytes ("<< (unsigned int)(GetSetSymbolCount())<<" elements).\n";
        
        // show the dictionary sorted alphabetically
        if (symbolset.size()>0)
                {
                cout << "Symbol Set - Sorted Alphabetically ("<<(unsigned int)(symbolset.size())<<" entries)\n";
                cout << " " << setiosflags(ios::left) << setw(Parameter_MaxSubstringSize) << "symboltext" << " " << setw(10) << "frequency\n";
                cout << " " << setiosflags(ios::left) << setw(Parameter_MaxSubstringSize) << "----------" << " " << setw(10) << "---------\n";
                for (symbolset_pos=symbolset.begin();symbolset_pos!=symbolset.end();++symbolset_pos)
                        {
                        value=(*symbolset_pos)->get_value();
                        NiceifyHighAsciiString(value);
                        cout << " " << setiosflags(ios::left) << setw(Parameter_MaxSubstringSize) << value << " " << setw(10) << (*symbolset_pos)->get_weight() << "\n";
                        }
                cout << "\n";
                }
}
//---------------------------------------------------------------------------


//---------------------------------------------------------------------------
// OCTANE PUBLIC API - AUXILIARY FUNCTIONS
        
string SubstringParser::GetParametersInformation()
{
        // show user available variables and their current values
        // ATTN: this has not been converted from cout to string
        string returnstring;
        cout << setiosflags(ios::left) << setw(17) << "maxbuildsymbols" << setiosflags(ios::left) << " " << setw(10) << Parameter_MaxSymbols_DuringBuild << " " << "parsing dictionary pruned to not exceed this size" << endl;
        cout << setiosflags(ios::left) << setw(17) << "maxsymbols" << setiosflags(ios::left) << " " << setw(10) << Parameter_MaxSymbols_Final << " " << "final dictionary pruned to reach this size" << endl;
        cout << setiosflags(ios::left) << setw(17) << "maxSubstring" << setiosflags(ios::left) << " " << setw(10) << Parameter_MaxSubstringSize << " " << "max size of Substrings in dictionary" << endl;
        cout << setiosflags(ios::left) << setw(17) << "onlywords" << setiosflags(ios::left) << " " << setw(10) << Parameter_OnlyCodeWholeWords << " " << "only add whole word symbols? (bool)" << endl;
        cout << setiosflags(ios::left) << setw(17) << "spanwords" << setiosflags(ios::left) << " " << setw(10) << Parameter_SpanWordBoundaries << " " << "encode symbols that span words? (bool)" << endl;
        cout << setiosflags(ios::left) << setw(17) << "crends" << setiosflags(ios::left) << " " << setw(10) << Parameter_CountCRsAsEOTs << " " << "count CRs as end-of-stream symbols? (bool)" << endl;
        cout << setiosflags(ios::left) << setw(17) << "minweight" << setiosflags(ios::left) << " " << setw(10) << Parameter_PruneMinimumWeight << " " << "minimum threshold weight for final pruning" << endl;
        cout << setiosflags(ios::left) << setw(17) << "smartlookup" << setiosflags(ios::left) << " " << setw(10) << Parameter_UseSmartLookup << " " << "when true, use lower_bound stl dictionary search" << endl;
        cout << setiosflags(ios::left) << setw(17) << "parsemode" << setiosflags(ios::left) << " " << setw(10) << Parameter_ParseMode << " " << "parse heuristic (0=greedy 1=lff 2=deep&slow)" << endl;
        cout << setiosflags(ios::left) << setw(17) << "recalculations" << setiosflags(ios::left) << " " << setw(10) << Parameter_PruneReCalculations << " " << "recalculate symbol costs during pruning?" << endl;
        return returnstring;
}


bool SubstringParser::SetParameter(const std::string &parametername,const std::string &parametervalue)
{
        // 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;
}


void SubstringParser::SetDefaultParameters()
{
        // encoding parameters that govern how dictionary is built

        // 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 #
        Parameter_MaxSymbols_DuringBuild=200000;

        // 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
        Parameter_MaxSymbols_Final=2000;

        // how many characters is largest (sub)string stored in dictionary
        Parameter_MaxSubstringSize=12;
        //      Parameter_MaxSubstringSize=3;
        //      Parameter_MaxSubstringSize=1;

        // only store characters and whole words?
        //      Parameter_OnlyCodeWholeWords=false;
        Parameter_OnlyCodeWholeWords=false;

        // store Substrings that span words (i.e. they contain multiple words)
        Parameter_SpanWordBoundaries=false;

        // minimum count for a word or Substring in order to even consider leaving it in the dictionary
        Parameter_PruneMinimumWeight=10;

        // 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.
        //Parameter_CountCRsAsEOTs=false;
        Parameter_CountCRsAsEOTs=true;

        // 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
        Parameter_UseSmartLookup=true;

        // we can either use a greedy search to find longest Substring starting with first char or we can use smarter but slower heuristics
        Parameter_ParseMode=Dictionary_ParseMode_GREEDY;

        // should we recompute symbol costs during pruning? (this actually employs the dictionary set and calculates actual usage counts and then reprunes)
        Parameter_PruneReCalculations=true;
}
//---------------------------------------------------------------------------



//---------------------------------------------------------------------------
// PARSER PUBLIC API - PREPARATIONS FOR PARSING
        
bool SubstringParser::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.
        //  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;
}

void SubstringParser::SynchronizeStateForNewStream()
{
        // synchronize state for a new stream
        // this MUST be called before beginning a new parsing stream
        // reset input buffer and end-of-stream sent flag
        inputbufferlen=0;
        senteos=false;
}

bool SubstringParser::CreateSymbolSetUsingStream(bitreader &from)
{
        // 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;
}
//---------------------------------------------------------------------------



//---------------------------------------------------------------------------
// Parser API

bool SubstringParser::ParseNextSymbolFromInput(bitreader &from, int &symbolnum)
{
        // 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)
{
        // 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;
}
//---------------------------------------------------------------------------














//---------------------------------------------------------------------------
// Internal functions for freeing data structure

void SubstringParser::FreeData()
{
        // free symbolset - this will key any SubstringSymbol nodes
        FreeData_Symbols();
}

void SubstringParser::FreeData_Symbols()
{
        // free set,vector and symbols
        
        // we only want to free the symbols once, even if they are in both set and vector
        for (symbolset_pos=symbolset.begin();symbolset_pos!=symbolset.end();++symbolset_pos)
                {
                // delete the pointed to node
                delete (*symbolset_pos);
                }

        // clear main symbolset
        symbolset.clear();

        // and now rebuild the vector, which will clear it
        BuildSymbolVector();
}
//---------------------------------------------------------------------------


//---------------------------------------------------------------------------
// Internal Helper functions for saving and loading state

bool SubstringParser::SaveParameters(bitwriter &to)
{
        // write parameter settings
        to.put(Parameter_MaxSymbols_DuringBuild);
        to.put(Parameter_MaxSymbols_Final);
        to.put(Parameter_MaxSubstringSize);
        to.put(Parameter_OnlyCodeWholeWords);
        to.put(Parameter_SpanWordBoundaries);
        to.put(Parameter_PruneMinimumWeight);
        to.put(Parameter_CountCRsAsEOTs);
        to.put(Parameter_UseSmartLookup);
        to.put(Parameter_ParseMode);
        to.put(Parameter_PruneReCalculations);
        return true;
}


bool SubstringParser::LoadParameters(bitreader &from)
{
        // read parameter settings
        from.get(Parameter_MaxSymbols_DuringBuild);
        from.get(Parameter_MaxSymbols_Final);
        from.get(Parameter_MaxSubstringSize);
        from.get(Parameter_OnlyCodeWholeWords);
        from.get(Parameter_SpanWordBoundaries);
        from.get(Parameter_PruneMinimumWeight);
        from.get(Parameter_CountCRsAsEOTs);
        from.get(Parameter_UseSmartLookup);
        from.get(Parameter_ParseMode);
        from.get(Parameter_PruneReCalculations);
        return true;
}


bool SubstringParser::SaveSymbols(bitwriter &to)
{
        // write the symboldset to file
        // return true on success
        unsigned char valuelength;

        // write entries in compact binary form
        for (symbolset_pos=symbolset.begin();symbolset_pos!=symbolset.end();++symbolset_pos)
                WriteSubstringSymbol((*symbolset_pos),to);

        // write an end-of-header in case we want to add this header as prefix of another file
        // we use a string-length==255 to mean end of table (no strings ever allowed greater than 254 characters)
        valuelength=255;
        to.put(valuelength);

        // return success
        return true;
}


bool SubstringParser::LoadSymbols(bitreader &from)
{
        // load a previously saved dictionary from file
        bool bretv=true;
        bool bretv2;

        // read dictionary
        while (!from.empty())
                {
                // read length of the string, as an unsigned car
                bretv2=ReadSubstringSymbol(from);
                if (!bretv2)
                        break;
                }

        // and now build the vector for fast random access
        BuildSymbolVector();

        // return true on success
        return bretv;
}
//---------------------------------------------------------------------------


//---------------------------------------------------------------------------
// Internal Parsing
bool SubstringParser::WriteSubstringSymbol(SubstringSymbol *SubstringSymbolp,bitwriter &to)
{
        // SubstringSymbol reader/writer - derived classes will take these over if necessary
        // return true on success
        TSubStrParserWeight weightvalue;
        unsigned int weightvalue_uint;
        unsigned char valuelength;

        // write length of the string, as an unsigned int
        valuelength=(int)(((*symbolset_pos)->get_valuep())->length());
        to.put(valuelength);
        // write string
        to.write(((*symbolset_pos)->get_valuep())->c_str(),valuelength);
        // get weight of symbol
        weightvalue=(*symbolset_pos)->get_weight();
        // SubstringSymbols should be writable as unsigned ints, but we dynamic cast in case, which will throw an exception if not
        weightvalue_uint=static_cast<unsigned int>(weightvalue);
        to.put(weightvalue_uint);

        // return success
        return true;
}

bool SubstringParser::ReadSubstringSymbol(bitreader &from)
{
        // virtual SubstringSymbol reader/writer - derived classes will take these over if necessary
        // return false when we hit end
        unsigned int weightvalue_uint;
        unsigned char valuelength;
        char valuestr[256];
        std::string valuestring;
        
        from.get(valuelength);
        if (valuelength>=255)
                {
                // all done
                return false;
                }
        // read string
        from.read(valuestr,valuelength);
        valuestring=string(valuestr,valuelength);
        // read weight
        from.get(weightvalue_uint);
        // now add the symbol SubstringSymbol
        AddSymbol(valuestring,(TSubStrParserWeight)weightvalue_uint);
        return true;
}
//---------------------------------------------------------------------------



//---------------------------------------------------------------------------
// Internal symbol construction

void SubstringParser::AddPrimitiveCharacterSubstringSymbols()
        {
        // Push every possible character as SubstringSymbol into the set
        string valuestring;
        char valuestr[20];

        for ( int i = 0 ; i < 256 ; i++ )
                {
                // form the string value of this (just the dictionary character or word)
                valuestr[0]=i;valuestr[1]='\0';
                valuestring=string(valuestr,1);
                // create a new SubstringSymbol node with this character, with a count of 1 (if you try to add a weight of 0 you will mess up the tree since sums must be strictly increasing)
                UpdateValueStringInSymbolSet(valuestring,1);
                }

        // we are going to use the empty string "" as our EOS (or End of Encoding) symbol, and record its number
        valuestring="";
        UpdateValueStringInSymbolSet(valuestring,1);
        }


bool SubstringParser::UpdateValueStringInSymbolSet(const string &stringvalue,int increment)
{
        // add a symbol as a SubstringSymbol with 0 count
        // return false on a FAILURE to add the symbol (ran out of memory)
        bool bretv=true;

        // use a static local variable to reduce memory allocation-deallocation thrashing, and use it for searching
        static SubstringSymbol searchSubstringSymbol("",1);
        // now we use this searchSubstringSymbol for searching
        searchSubstringSymbol.set_value(stringvalue);

        // look it up
        symbolset_pos=symbolset.find(&searchSubstringSymbol);
        // if its not found, create it
        if (symbolset_pos==symbolset.end())
                {
                // create the SubstringSymbol and add it, with weight = increment
                AddSymbol(stringvalue,increment);
                }
        else
                {
                // we found it, so increment its count
                (*symbolset_pos)->increment_weight(increment);
                }

        // return false on failure
        return bretv;
}

void SubstringParser::ResetWeights()
{
        // reset weights for every symbol
        for (symbolset_pos=symbolset.begin();symbolset_pos!=symbolset.end();++symbolset_pos)
                (*symbolset_pos)->set_weight(0);
}
//---------------------------------------------------------------------------



//---------------------------------------------------------------------------
// Internal symbol construction

void SubstringParser::AddSubstringsFromSlidingWindowString(string &slidingwindowstring)
{
        // According to our parameters, increment frequency counts (adding symbols when needed) of some Substrings from our sliding window
        // The way we do this is, our primary character is the rightmost one; thats the one that will be different on each call.
        // If we want to do standard huffman on characters, we would simply update the frequency of the rightmost character.
        // Alternatively, we have various other parameters which can govern which Substrings we track.
        // Some of many settings can generate HUGE trees and sets, but these trees will eventually be pruned of least-useful entries.
        // Note this procedure is the most convoluted one in the file, because it deals with various parameters
        //  which regulate what kinds of Substrings from the input stream get tokenized.

        string valuestring;
        bool bretv;
        int len=(int)(slidingwindowstring.length());
        unsigned char c,c2;
        int leftpos,rightpos,curpos;
        bool delimiteronborder;

        // first add the rightmost character, by incrementing its usage count by 1
        valuestring=slidingwindowstring.substr(len-1,1);
        bretv=UpdateValueStringInSymbolSet(valuestring,1);

        // if the string length is only one character, then we are done.
        if (len==1)
                return;

        // reset flag which helps us prevent from adding a keyword which ends in a delimiter
        delimiteronborder=false;

        if (Parameter_OnlyCodeWholeWords)
                {
                // we only want to store full words, so if we have not hit a new word boundary, then return
                c=slidingwindowstring[len-1];
                c2=slidingwindowstring[len-2];
                if (len<3)
                        {
                        // too small to be on a word boundary
                        return;
                        }
                if (!IsNonWordCharacter(c) && !IsNonWordCharacter(c2))
                        {
                        // we are within a word
                        return;
                        }
                if (IsNonWordCharacter(c) && IsNonWordCharacter(c2))
                        {
                        // we are within a word
                        return;
                        }
                // start end pointer at last non-delimiter
                rightpos=len-2;
                }
        else
                {
                // start end position at last character
                rightpos=len-1;
                }

        // set flag to tell us whether the new character is a delimiter and shouldn't be coded on the end of a real word
        if (IsNonWordCharacter(slidingwindowstring[rightpos]))
                {
                // other than adding delimiters as their own characters (done above), we don't want to code them as part of a word
                // so we set a flag here saying that we are only going to move leftward to catch a sequence of delimiters as a Substring, and NOT
                // allows a Substring which has delimiters on the *borders* of words
                delimiteronborder=true;
                }
        else
                delimiteronborder=false;

        // set left pos
        leftpos=rightpos-Parameter_MaxSubstringSize;
        if (leftpos<0)
                leftpos=0;

        // start walking backwards from right to left and add Substrings to dictionary
        //  always encoding from curpos to end (rightpos)
        for (curpos=rightpos-1;curpos>leftpos;--curpos)
                {
                c=slidingwindowstring[curpos];
                if (delimiteronborder && IsNonWordCharacter(c))
                        {
                        if (Parameter_OnlyCodeWholeWords && curpos>leftpos)
                                {
                                // since we only code words, we don't want to code this Substring of delimiters yet
                                continue;
                                }
                        // because we are parsing a string of delimiters, we want to just drop through to write out this Substring
                        }
                else if (IsNonWordCharacter(c) || delimiteronborder)
                        {
                        if (IsNonWordCharacter(c) && IsNonWordCharacter(slidingwindowstring[curpos+1]))
                                {
                                // we have hit a series of delimiters to the left of a word, so we've already encoded the non-delimiter-bordered stuff to our right
                                // so we don't want to encode it again.
                                continue;
                                }
                        if (Parameter_OnlyCodeWholeWords || delimiteronborder)
                                {
                                // we found a new word (or sequence of words), so encode it
                                valuestring=slidingwindowstring.substr(curpos+1,rightpos-curpos);
                                //cout << "type 1 word: "<<valuestring<< endl;
                                bretv=UpdateValueStringInSymbolSet(valuestring,1);
                                if (delimiteronborder)
                                        {
                                        // we just finished writing out a string of delimiters bordered on left by non-delimiter, so we stop now
                                        break;
                                        }
                                else if (!Parameter_SpanWordBoundaries)
                                        {
                                        // since we don't span word boundaries, we are done
                                        break;
                                        }
                                else
                                        {
                                        // let it continue to look for next whole word
                                        continue;
                                        }
                                }
                        else if (!Parameter_SpanWordBoundaries)
                                {
                                // we hit a word boundary, so we are done
                                break;
                                }
                        else if (IsNonWordCharacter(c) && !delimiteronborder)
                                {
                                // we don't want to let any word Substring start with a delimiter (or end with one, which is checked above)
                                // actually i think by the time we drop down to here this is always true
                                continue;
                                }
                        }
                else if (delimiteronborder)
                        {
                        // our rightmost character was a delimiter so we wont consider any non-delimiters words to the left of it
                        break;
                        }
                else if (Parameter_OnlyCodeWholeWords)
                        {
                        // we are in the middle of a word, so we do nothing
                        continue;
                        }

                // update the Substring
                valuestring=slidingwindowstring.substr(curpos,(rightpos-curpos)+1);
                bretv=UpdateValueStringInSymbolSet(valuestring,1);
                }
}
//---------------------------------------------------------------------------




//---------------------------------------------------------------------------
// Internal Parsing

int SubstringParser::SwallowSymbolFromInputQueueStr(SubstringSymbol *symbolp,char *inputqueuestr,int inputqueuestrlen,bool debugmode)
{
        // find which symbol to encode
        if (symbolp==NULL)
                {
                // no match found
                return -1;
                }

        // debugmode shows the sub-string used for encoding
        if (debugmode)
                cout << symbolp->get_value() << "*";

        // shift inputqueuestrlen
        int writepos=0;
        for (int pos=(int)((symbolp->get_valuep())->length());pos<inputqueuestrlen;++pos)
                {
                inputqueuestr[writepos]=inputqueuestr[pos];
                ++writepos;
                }
        inputqueuestrlen=writepos;

        // return length of shifted inputqueuestr
        return inputqueuestrlen;
}


SubstringSymbol* SubstringParser::FindNextSymbolToEncode(char *inputqueuestr,int inputqueuestrlen)
{
        // 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.
        // return the new inputqueuestr with remaining bytes, and return length of remaining bytes.
        SubstringSymbol *symbolnodep = 0;

        if (Parameter_ParseMode==Dictionary_ParseMode_GREEDY || inputqueuestrlen<=2)
                {
                // GREEDY PARSE
                // find biggest matching prefix in symbol dictionary - this should never fail unless the dictionary is not built at all,
                //  since the dictionary is supposed to contain every character, so at least the leftmost character should match
                symbolnodep = FindNextSymbolToEncode_Greedy(inputqueuestr,inputqueuestrlen);
                }
        else if (Parameter_ParseMode==Dictionary_ParseMode_LFF)
                {
                // SMARTER HEURISTIC PARSE (slower than greedy, but *maybe* better)
                int bestindex=inputqueuestrlen;
                int bestscore=-1;
                for (int index=0;index<=inputqueuestrlen-1;++index)
                        {
                        // find length of the string beginning at index
                        // early stop if we know we cant do better
                        if (bestscore>=inputqueuestrlen-index)
                                break;
                        symbolnodep = FindNextSymbolToEncode_Greedy(&inputqueuestr[index],inputqueuestrlen-index);
                        if (symbolnodep==NULL)
                                break;
                        if (bestscore==-1 || symbolnodep->get_valuelen()>bestscore)
                                {
                                bestscore=symbolnodep->get_valuelen();
                                bestindex=index;
                                }
                        }
                // now that we found the longest Substring, parse the string BEFORE it
                if (bestindex==0)
                        bestindex=inputqueuestrlen;
                symbolnodep = FindNextSymbolToEncode_Greedy(inputqueuestr,bestindex);
                }
        else if (Parameter_ParseMode==Dictionary_ParseMode_DEEP)
                {
                // SMARTER HEURISTIC PARSE (slower than greedy, but *maybe* better)
                double encodecost;
                double bestscore;
                int longestlen=inputqueuestrlen;
                int bestindex=longestlen;
                bool firstscore=true;
                do
                        {
                        bestscore=-1;
                        longestlen=bestindex;
                        for (int index=1;index<=longestlen;++index)
                                {
                                // find cost if we encode based on split at index
                                encodecost=CalculateEncodeCost(inputqueuestr,index);
                                if (index<longestlen)
                                encodecost+=CalculateEncodeCost(&inputqueuestr[index],longestlen-index);
                                // update our tracking of best score
                                if (firstscore || encodecost<=bestscore)
                                        {
                                        bestscore=encodecost;
                                        bestindex=index;
                                        firstscore=false;
                                        }
                                }
                        } while (bestindex!=longestlen);
                // and do the search with this limit (note we could have asked CalculateEncodeCost to return best found first match
                symbolnodep = FindNextSymbolToEncode_Greedy(inputqueuestr,bestindex);
                }
        else
                {
                // unknown parse mode
                cout << "ERROR: unknown parse mode "<<Parameter_ParseMode<<"."<<endl;
                }

        return symbolnodep;
        }


SubstringSymbol* SubstringParser::FindNextSymbolToEncode_Greedy(char *inputqueuestr,int inputqueuestrlen)
{
        // find biggest matching prefix in symbol dictionary - this should never fail unless the dictionary is not built at all,
        //  since the dictionary is supposed to contain every character, so at least the leftmost character should match
        // return a pointer to the symbol, or NULL if there is some error and we cant find one.

        // there are several ways to do this dictionary search within the SymbolSet, which is a binary tree
        // one way is to start with full string and gradually shorten it until we get an exact match
        // another is to ask the stl set to find the nearest match, and search back from there for shortest exact match
        int originputqueuestrlen=inputqueuestrlen;
        string inputstring;

        // use a static local variable to reduce memory allocation-deallocation thrashing
        static SubstringSymbol searchSubstringSymbol("",1);

        // convert char * to string, using exactly inputqueuestrlen, regardless of any '\0'
        if (inputqueuestrlen==0)
                inputstring="";
        else
                inputstring=string(inputqueuestr,inputqueuestrlen);

        // truncate it to max length of any symbol, incase caller sometimes passes more
        if (inputqueuestrlen>Parameter_MaxSubstringSize)
                {
                inputqueuestrlen=Parameter_MaxSubstringSize;
                inputstring=inputstring.substr(0,inputqueuestrlen);
                }

        // now we use this searchSubstringSymbol for searching
        searchSubstringSymbol.set_value(inputstring);

        // find the longest Substring, using a smarter use of stl lower_bound instead of find()
        if (Parameter_UseSmartLookup)
                {
                // smarter method (22:00 seconds on a test, about 3x faster than slow method below
                //  ATTN: can we simplify this?
                int len;
                int index;
                string teststring;
                for (;;)
                        {
                        symbolset_pos=symbolset.lower_bound(&searchSubstringSymbol);
                        // check for error
                        if (symbolset_pos==symbolset.end())
                                {
                                // nothing smaller so the LAST symbol, single character (we verify to make sure there isnt an error)
                                --symbolset_pos;
                                // shorten main string to match
                                inputqueuestrlen=1;
                                inputstring=inputstring.substr(0,inputqueuestrlen);
                                teststring=(*symbolset_pos)->get_value();
                                if (inputstring[0]!=teststring[0])
                                        {
                                        cout << "ERROR: Unexpectedly didn't find any match for a string that started out "<<originputqueuestrlen<<" characters (we hit "<<inputqueuestrlen<<").  last char was "<<(int)((unsigned char)(inputqueuestr[0]))<<"."<<endl;
                                        return NULL;
                                        }
                                // ok the best match is the last symbol
                                searchSubstringSymbol.set_value(inputstring);
                                break;
                                }

                        //teststring=(*symbolset_pos)->get_value();
                        //len=(int)(teststring.length());
                        //cout << "lowerbound for '"<<inputstring<<"' = '" << teststring <<"' (len="<<len<<")."<<endl;;

                        // if we have an exact match we are done
                        teststring=(*symbolset_pos)->get_value();
                        len=(int)(teststring.length());
                        if (teststring==inputstring)
                                break;

                        // try one previous
                        --symbolset_pos;
                        teststring=(*symbolset_pos)->get_value();
                        len=(int)(teststring.length());
                        if (len<inputqueuestrlen)
                                {
                                // shorten main string to match
                                inputqueuestrlen=len;
                                inputstring=inputstring.substr(0,inputqueuestrlen);
                                }
                        // if we have an exact match we are done
                        if (teststring==inputstring)
                                break;

                        // if not, find the last character they agree on and find next bound
                        len=(int)(teststring.length());
                        for (index=0;index<len;++index)
                                {
                                if (teststring[index]!=inputstring[index])
                                        break;
                                }

                        // now shorten it and try again
                    inputqueuestrlen=index;
                    if (inputqueuestrlen==0)
                                {
                                cout << "ERROR: unexpectedly truncated search string that started out "<<originputqueuestrlen<<" characters (we hit "<<inputqueuestrlen<<").  last char was "<<(int)inputqueuestr[0]<<"."<<endl;
                        inputstring="";
                        }
                        else
                                inputstring=inputstring.substr(0,inputqueuestrlen);
                        searchSubstringSymbol.set_value(inputstring);
                        }
                }
        else
                {
                // dumb method (67:00 seconds on a test, about 3x slower than smart method)
                for(;;)
                        {
                        symbolset_pos=symbolset.find(&searchSubstringSymbol);
                        if (symbolset_pos!=symbolset.end())
                                {
                                // we found an exact match
                                break;
                                }
                        // not found, so shorten string by removing rightmost character
                        --inputqueuestrlen;
                        if (inputqueuestrlen<=0)
                                {
                                cout << "ERROR: unexpectedly didn't find any match for a string that started out with "<<originputqueuestrlen<<" characters (we hit "<<inputqueuestrlen<<").  last char was "<<(int)inputqueuestr[0]<<"."<<endl;
                                return NULL;
                                }
                        // decrease length of Substring currently being searched for and continue
                        inputstring=inputstring.substr(0,inputqueuestrlen);
                        searchSubstringSymbol.set_value(inputstring);
                        }
                }

        // return the pointer
        return *symbolset_pos;
}


double SubstringParser::CalculateEncodeCost(char *inputqueuestr,int inputqueuestrlen)
{
        // try to find the optimal cost of encoding the string, using currently selected methods
        //  and return its cost, ASSUMING that we start by parsing longest matching leftmost substr
        SubstringSymbol* symbolnodep;
        double cost=0;

        // start by greedy parse of biggest leftmost substr
        symbolnodep = FindNextSymbolToEncode_Greedy(inputqueuestr,inputqueuestrlen);
        if (symbolnodep==NULL)
                {
                // no match found - this should never happen
                cout << "$no match found."<<endl;
                return 99999;
                }

        // add cost of initial Substring
        cost+=GetSymbolCost(symbolnodep);

        // advance pointer
        inputqueuestr+=symbolnodep->get_valuelen();
        inputqueuestrlen-=symbolnodep->get_valuelen();

        // now the remainder of the string could be done smart or greedy
        if (Parameter_ParseMode!=Dictionary_ParseMode_GREEDY && inputqueuestrlen>2)
                {
                // SMARTER HEURISTIC PARSE (slower than greedy, but *maybe* better)
                int bestindex=inputqueuestrlen;
                double bestscore=0;
                double encodecost;
                bool firstscore=true;
                for (int index=1;index<=inputqueuestrlen;++index)
                        {
                        // find cost if we encode based on split at index
                        encodecost=CalculateEncodeCost(inputqueuestr,index);
                        if (index<inputqueuestrlen)
                        encodecost+=CalculateEncodeCost(&inputqueuestr[index],inputqueuestrlen-index);
                        // update our tracking of best score
                        if (firstscore || encodecost<bestscore)
                                {
                                bestscore=encodecost;
                                bestindex=index;
                                firstscore=false;
                                }
                        }
                // now set cost to best cost found
                cost+=bestscore;
                }
        else if (inputqueuestrlen>0)
                {
                // GREEDY PARSE cost
                cost+=CalculateEncodeCost(inputqueuestr,inputqueuestrlen);
                }
        else
                {
                // nothing left to score
                }

        // now return cost
        return cost;
}
//---------------------------------------------------------------------------




//---------------------------------------------------------------------------
// Internal Pruning functions

void SubstringParser::PruneSymbolSet_WeightThreshold(TSubStrParserWeight thresholdweight)
{
        // remove all weights below some threshold set by parameter
        // this is a fast and easy step that will remove almost the entire current symbol set :)
        TSymbolSetTYPE::iterator nextsymbolpos;
        TSubStrParserWeight weight;
        int index=0;

        // First simplest pruning operation - simply remove all symbols which don't have some threshold count
        for (symbolset_pos=symbolset.begin();symbolset_pos!=symbolset.end();)
                {
                ++index;
                nextsymbolpos=symbolset_pos;
                ++nextsymbolpos;
                // only show non-zero weights (i.e. symbols used at least once)
                if (!((*symbolset_pos)->dontprune()))
                        {
                        weight=(*symbolset_pos)->get_weight();
                        if (weight<thresholdweight)
                                {
                                // delete this symbol
                                delete (*symbolset_pos);
                                symbolset.erase(symbolset_pos);
                                }
                        }
                // advance pointer
                symbolset_pos=nextsymbolpos;
                }
}


void SubstringParser::PruneSymbolSet_RemoveRedundantPrefixes()
{
        // some Substring symbols are simply prefixes of others, with no independent occurrences
        //  for example the Substring "supercomput" is a redundant Substring of "supercomputer"
        //  so we can remove those with no cost.
        TSymbolSetTYPE::iterator nextsymbolpos;
        TSymbolSetTYPE::iterator lastsymbolpos;
        TSubStrParserWeight weight,lastweight;
        string lastvalue;
        int lastvaluelen;

        lastweight=0;
        for (symbolset_pos=symbolset.begin();symbolset_pos!=symbolset.end();)
                {
                nextsymbolpos=symbolset_pos;
                ++nextsymbolpos;
                // some symbols (like primitive characters, cannot be pruned)
                if ((*symbolset_pos)->dontprune())
                        lastweight=0;
                else
                        {
                        weight=(*symbolset_pos)->get_weight();
                        if (weight==lastweight && weight!=0)
                                {
                                // got a candidate for pruning, IFF our prior string is a proper prefix of us
                                lastvaluelen=(int)(lastvalue.length());
                                if (((*symbolset_pos)->get_value()).compare(0,lastvaluelen,lastvalue.c_str(),lastvaluelen)==0)
                                        {
                                        // yes it is, so kill our last value
                                        delete *lastsymbolpos;
                                        symbolset.erase(lastsymbolpos);
                                        }
                                }
                        // remember last symbol details
                        lastweight=weight;
                        lastvalue=(*symbolset_pos)->get_value();
                        lastsymbolpos=symbolset_pos;
                        }
                // advance pointer
                symbolset_pos=nextsymbolpos;
                }
}


void SubstringParser::PruneSymbolSet_ReduceSizeTo(unsigned int targetsize)
{
        // we have exceeded our maximum # of symbols allowed during build process, so reduce the size
        //  this is done quite inefficiently, but we can worry about that later, or not, since its not in a time-critical place
        // ATTN: a smarter way would be to sort by weight and pop off smallest weights.
        if (symbolset.size()<targetsize)
                return;

        for (int count=2;count<10000;++count)
                {
                // remove all removable symbols with a weight < count and then check set size again
                PruneSymbolSet_WeightThreshold((TSubStrParserWeight)count);
                if (symbolset.size()<=targetsize)
                        break;
                }
}


void SubstringParser::PruneSymbolSet()
{
        // we need to reduce the size of the dictionary SymbolSet by pruning symbols we think are not worth the coding space
        //  having silly symbols increases our cost in two main ways:
        //   1) cost in memory needed to store the dictionary in memory and time needed to search dictionary
        //   2) cost incurred due to the fact that the more words in dictionary, the more bits needed to encode other symbols.
        //      this is a very serious issue and suggests the dictionary should be as small as possible.
        // the bitreader is passed so that we can reparse the input in order to test our created symbol set.

        // display info
        cout << endl << "Total symbols in dictionary before pruning: " << GetSetSymbolCount() << endl;

        // remove weights below a threshold
        PruneSymbolSet_WeightThreshold(Parameter_PruneMinimumWeight);
        cout << "After Stage 1 Pruning (removed scores below "<<Parameter_PruneMinimumWeight<<"), symbols: " << GetSetSymbolCount() << endl;

        // remove redundant prefixes
        PruneSymbolSet_RemoveRedundantPrefixes();
        cout << "After Stage 2 Pruning (removed redundant prefixes), symbols: " << GetSetSymbolCount() << endl;

        // pre-capping recompression
        if (Parameter_PruneReCalculations)
                {
                // now actually re-compress the file using current symbol set to get better real-world weight counts, and repeat prunings
                ReParseFileReComputeCosts(true);
                PruneSymbolSet_WeightThreshold(Parameter_PruneMinimumWeight);
                PruneSymbolSet_RemoveRedundantPrefixes();
                // some info for user
                cout << "After pre-ceil pre-compression, re-evaluation, and repruning, symbols: " << GetSetSymbolCount() << endl;
                }

        // finally, cap symbol count.  there are smart and dumb ways this can be done
        PruneSymbolSet_ReduceSizeTo(Parameter_MaxSymbols_Final);
        cout << "After Stage 3 Pruning (killed worst scores to reach target), symbols: " << GetSetSymbolCount() << endl;

        // more recompression loops after capping
        if (Parameter_PruneReCalculations)
                {
                // now actually re-compress the file using current symbol set to get better real-world weight counts, and repeat prunings
                ReParseFileReComputeCosts(true);
                PruneSymbolSet_WeightThreshold(Parameter_PruneMinimumWeight);
                PruneSymbolSet_RemoveRedundantPrefixes();
                cout << "After re-compression, re-evaluation, and repruning, symbols: " << GetSetSymbolCount() << endl;
                }
}
//---------------------------------------------------------------------------




//---------------------------------------------------------------------------
// For reparsing and recomputing scores

double SubstringParser::ReParseFileReComputeCosts(bool updateweights)
{
        // USING the current symbolset we have just created, reparse it and recalculate the 'cost'
        //  and frequency of each symbol.
        // This is useful because as we create and modify(prune) the symbolset, the symbols interact
        //  and effect frequencies, so its helpful to reparse the input and recalculate frequencies.
        // return sum cost of parsed symbols IFF updateweights == false

        // First we need to rebuild the symbol vector before we can parse
        BuildSymbolVector();

        int symbolnum;
        SubstringSymbol *symbolp;
        double totalcost=0;

        // reset input bitreader to where we started dictionarizing
        current_bitreaderp->seek_bit(start_bitreaderposition);

        // reset weights if we are recalculating them
        if (updateweights)
                ResetWeights();

        // loop through input grabbing symbols
        // ATTN: are we properly updating weights?
        while (ParseNextSymbolFromInput(*current_bitreaderp,symbolnum))
                {
                symbolp=symbolvector[symbolnum];
                if (updateweights)
                        {
                        // we can be run in a mode to actually update weights while encoding
                        if (updateweights)
                                {
                                // note this will not change priority queue, and is therefore somewhat skidding on what is 'allowed' by stl
                                //  but we use this purposefully so that we are modifying the weights while preserving current priority queue.
                                symbolp->increment_weight(1);
                                // we need to also keep track of CRs for EOS's if appropriate
                                if (Parameter_CountCRsAsEOTs && strchr(symbolp->get_valuep()->c_str(),13)!=NULL)
                                        {
                                        symbolp=FindNextSymbolToEncode_Greedy("",0);
                                        if (symbolp!=NULL)
                                                symbolp->increment_weight(1);
                                        }
                                }
                        }
                else
                        totalcost+=symbolp->get_cost();
                }

        // return success
        return totalcost;
}
//---------------------------------------------------------------------------


//---------------------------------------------------------------------------
// Internal symbol construction

void SubstringParser::BuildSymbolVector()
{
        // build a vector of symbol pointers, for efficient random access
        // clear any existing vector
        symbolvector.clear();
        // add symbols from set
        int index=0;
        for (symbolset_pos=symbolset.begin();symbolset_pos!=symbolset.end();++symbolset_pos)
                {
                // add symbol to vector
                symbolvector.push_back(*symbolset_pos);
                // tell symbol what number it is
                (*symbolset_pos)->set_symbolvectorpos(index++);
                }
        // now we need to update our count of how many symbols we have
        symbolcount=(int)(symbolvector.size());
        // and record the symbol representing the end-of-stream (EOS is "")
        endofstreamsymbolnum=LookupSymbolNumberFromText(string(""));
}


int SubstringParser::LookupSymbolNumberFromText(string wordstring)
{
        // return the number of a symbol in the parsing symbolset (or -1 if not found)
        static SubstringSymbol searchSubstringSymbol("",1);
        // now we use this searchSubstringSymbol for searching
        searchSubstringSymbol.set_value(wordstring);
        symbolset_pos=symbolset.find(&searchSubstringSymbol);
        // if its not found, return -1
        if (symbolset_pos==symbolset.end())
                return -1;
        // otherwise return its index symbol number
        return ((*symbolset_pos)->get_symbolvectorpos());
}
//---------------------------------------------------------------------------

 

Generated on 20 May 2004 by doxygen 1.3.3