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

http://octane.sourceforge.net/

parsers/parser_substring/substringparser.hpp

Go to the documentation of this file.

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

//---------------------------------------------------------------------------
// recursive header protection
#ifndef Octane_SubstringParserH
#define Octane_SubstringParserH
//---------------------------------------------------------------------------

//---------------------------------------------------------------------------
// application includes
#include "../parser.hpp"
#include "../../bitio/bitio.hpp"
// system includes
#include <vector>
#include <set>
#include <assert.h>
using namespace std;
//---------------------------------------------------------------------------




//---------------------------------------------------------------------------
// Different types of parsing modes (greedy is fastest and usually not
//  significantly worse than LFF (longest substring first).  Deep is super
//  slow and not noticeably better.
#define Dictionary_ParseMode_GREEDY             0
#define Dictionary_ParseMode_LFF                1
#define Dictionary_ParseMode_DEEP               2
//---------------------------------------------------------------------------


//---------------------------------------------------------------------------
// What kind of precision should we use for the weights? int should be fine.
typedef unsigned int TSubStrParserWeight;
#define TSubStrParserWeight_MAX UINTMAX

// Biggest substring we will ever parser
#define SubStrHuff_BiggestSubStringLen 100
//---------------------------------------------------------------------------





//---------------------------------------------------------------------------
class SubstringSymbol
{
protected:
        TSubStrParserWeight weight;
        std::string value;
        int symbolvectorpos;
public:
        // Constructor and destructor
        SubstringSymbol () {weight=0;value="";}
        SubstringSymbol (const std::string &invalue, TSubStrParserWeight inweight=0) {weight=inweight; value=invalue;}
        ~SubstringSymbol () {;}
public:
        bool operator>( const SubstringSymbol * &a ) const {return weight > (a->get_weight());}
public:
        TSubStrParserWeight get_weight() const {return weight;}
        void increment_weight(int increment) {weight+=increment;}
        void set_weight(TSubStrParserWeight val) {weight=val;}
        std::string* get_valuep() {return &value;}
        std::string& get_value() {return value;}
        int get_valuelen() {return (int)(value.length());}
        void set_value(const std::string &invalue) {value=invalue;}
        int get_symbolvectorpos() {return symbolvectorpos;};
        void set_symbolvectorpos(int inpos) {symbolvectorpos=inpos;};
public:
        bool dontprune() {if (value.length()<=1) return true; else return false;}
        unsigned int get_memoryused() const {return (unsigned int)(sizeof(this)+value.capacity());}
        double get_cost() {return 1.0/(1.0+weight);};
};


template< class T >
class TSubstringSymbolWeightGreater
        {
        public:
                bool operator() (const T& pLeft, const T& pRight) const
                        { return pLeft->get_weight()>pRight->get_weight(); }
        };


template< class T >
class TSubstringSymbolStringGreater
        {
        public:
                bool operator() (const T& pLeft, const T& pRight) const
                        { return pLeft->get_value()<pRight->get_value(); }
        };
//---------------------------------------------------------------------------



//---------------------------------------------------------------------------
class SubstringParser : public OctaneParser
{
protected:
        typedef std::set< SubstringSymbol* , TSubstringSymbolStringGreater<SubstringSymbol*> > TSymbolSetTYPE;
        typedef std::vector< SubstringSymbol* > TSymbolVectorTYPE;
        TSymbolSetTYPE symbolset;
        TSymbolVectorTYPE symbolvector;
        TSymbolSetTYPE::iterator symbolset_pos;
        TSymbolVectorTYPE::iterator symbolvector_pos;
        char inputbufferstr[SubStrHuff_BiggestSubStringLen] ;
        int inputbufferlen;
        bool senteos;
protected:
        // Encoding parameters which govern how dictionary is built (see SetDefaultDictionaryBuildingParameters implementation for descriptions)
        unsigned int Parameter_MaxSymbols_DuringBuild;
        unsigned int Parameter_MaxSymbols_Final;
        int Parameter_MaxSubstringSize;
        bool Parameter_OnlyCodeWholeWords;
        bool Parameter_SpanWordBoundaries;
        // 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.
        bool Parameter_CountCRsAsEOTs;
        unsigned int Parameter_PruneMinimumWeight;
        int Parameter_ParseMode;
        bool Parameter_UseSmartLookup;
        bool Parameter_PruneReCalculations;
protected:
        int symbolcount;
        int endofstreamsymbolnum;
        bitreader *current_bitreaderp;
        size_t start_bitreaderposition;
public:
        //---------------------------------------------------------------------------
        SubstringParser();
        ~SubstringParser();
        //---------------------------------------------------------------------------
public:
        //---------------------------------------------------------------------------
        // PARSER PUBLIC API - PREPARATIONS FOR PARSING
        virtual bool CreateSymbolSetUsingStream(bitreader &from);
        virtual bool IsReadyToParse() {if (symbolcount>0) return true; else return false;};
        virtual bool RewindAnyBufferedInput(bitreader &from);
        //---------------------------------------------------------------------------
public:
        //---------------------------------------------------------------------------
        // PARSER PUBLIC API - MAIN PARSING FUNCTIONS
        virtual void SynchronizeStateForNewStream();
        virtual int GetSymbolCount() {return symbolcount;};
        virtual bool ParseNextSymbolFromInput(bitreader &from, int &symbolnum);
        virtual bool WriteSymbolText(bitwriter &to, int symbolnum,bool &isendofstreamsymbol);
        virtual string LookupSymbolText(int symbolnum) {assert(symbolnum<(int)(symbolvector.size()));return symbolvector[symbolnum]->get_value();};
        //---------------------------------------------------------------------------
public:
        //---------------------------------------------------------------------------
        // OCTANE PUBLIC API - AUXILIARY FUNCTIONS - these are supported by all derived classes
        virtual void ShowDebuggingInfo();
        virtual unsigned int GetMemoryUsed();
        virtual unsigned int GetDiskspaceUsed(bool fortempdecompressiononly);
        virtual std::string GetParametersInformation();
        virtual void SetDefaultParameters();
        virtual bool SetParameter(const std::string &parametername,const std::string &parametervalue);
        virtual bool SaveState(bitwriter &to,bool fortempdecompressiononly);
        virtual bool LoadState(bitreader &from);
        //---------------------------------------------------------------------------
public:
        //---------------------------------------------------------------------------
        // OCTANE PARSER PUBLIC API - AUXILIARY FUNCTIONS - symbol helpers
        int GetSetSymbolCount() {return (int)(symbolset.size());};
        int LookupSymbolNumberFromText(string wordstring);
        //---------------------------------------------------------------------------
private:
        // save and load state information
        bool SaveSymbols(bitwriter &to);
        bool LoadSymbols(bitreader &from);
private:
        // symbol manipulation
        void AddPrimitiveCharacterSubstringSymbols();
        bool UpdateValueStringInSymbolSet(const string &stringvalue,int increment);
        void AddSubstringsFromSlidingWindowString(string &slidingwindowstring);
        SubstringSymbol* AddSymbol(const std::string &stringvalue, const TSubStrParserWeight weightvalue) {SubstringSymbol* p=new SubstringSymbol(stringvalue,weightvalue);if (p!=NULL) symbolset.insert(p);return p;}
private:
        // internal save/load helper functions
        bool SaveParameters(bitwriter &to);
        bool LoadParameters(bitreader &from);
        bool ReadSubstringSymbol(bitreader &from);
        bool WriteSubstringSymbol(SubstringSymbol *SubstringSymbolp,bitwriter &to);
private:
        void ResetWeights();
private:
        // Prune symbols from the set
        void PruneSymbolSet();
        void PruneSymbolSet_ReduceSizeTo(unsigned int targetsize);
        void PruneSymbolSet_WeightThreshold(TSubStrParserWeight thresholdweight);
        void PruneSymbolSet_RemoveRedundantPrefixes();
        double ReParseFileReComputeCosts(bool updateweights);
private:
        double GetSymbolCost(SubstringSymbol* symbolnodep) {return symbolnodep->get_cost();};
private:
        // Internal encoding and finding symbols to encode
        SubstringSymbol* FindNextSymbolToEncode(char *inputqueuestr,int inputqueuestrlen);
        SubstringSymbol* FindNextSymbolToEncode_Greedy(char *inputqueuestr,int inputqueuestrlen);
        int SwallowSymbolFromInputQueueStr(SubstringSymbol *symbolp,char *inputqueuestr,int inputqueuestrlen,bool debugmode);
        double CalculateEncodeCost(char *inputqueuestr,int inputqueuestrlen);
private:
        void BuildSymbolVector();
private:
        void FreeData();
        void FreeData_Symbols();
};
//---------------------------------------------------------------------------





//---------------------------------------------------------------------------
#endif
//---------------------------------------------------------------------------

 

Generated on 20 May 2004 by doxygen 1.3.3