LZ77Compression.h

Go to the documentation of this file.

 
#pragma once
 
#include <tuple>
#include <vector>
 
#include <string/LinearString.h>
 
#include <exception/CommonException.h>
 
namespace stringology {
 
namespace compression {
 
class LZ77Compression {
public:
    template < class SymbolType >
    static std::vector < std::tuple < unsigned, unsigned, SymbolType > > compress ( const string::LinearString < SymbolType > & string, unsigned searchBufferSize, unsigned lookaheadBufferSize );
 
private:
    template < class SymbolType >
    static int equal ( const string::LinearString < SymbolType > & string, unsigned first1, unsigned last1, unsigned first2 );
};
 
// Main method that handle compress
template < class SymbolType >
std::vector < std::tuple < unsigned, unsigned, SymbolType > > LZ77Compression::compress ( const string::LinearString < SymbolType > & string, unsigned searchBufferSize, unsigned lookaheadBufferSize ) {
 
    if(searchBufferSize == 0)
        throw exception::CommonException("LZ77: search buffer size must be greater than 0");
 
    if(lookaheadBufferSize == 0)
        throw exception::CommonException("LZ77: lookahead buffer size must be greater than 0");
 
    size_t pointer = 0;
 
    std::vector < std::tuple < unsigned, unsigned, SymbolType > > output;
 
    while ( pointer < string.getContent ( ).size ( ) ) {
        unsigned lookaheadBufferRealSize = lookaheadBufferSize;
        if ( pointer + lookaheadBufferSize + 1 > string.getContent ( ).size ( ) )
            lookaheadBufferRealSize = string.getContent ( ).size ( ) - pointer - 1;
 
        unsigned searchBufferRealSize = searchBufferSize;
        if ( pointer < searchBufferSize )
            searchBufferRealSize = pointer;
 
        unsigned maxMatch = 0;
        unsigned sbPointer = pointer;
        for ( unsigned j = pointer - searchBufferRealSize; j < pointer; j ++ ) {
            unsigned match = equal ( string, pointer, pointer + lookaheadBufferRealSize, j );
 
            if ( maxMatch <= match ) {
                maxMatch = match;
                sbPointer = j;
            }
        }
 
        output.push_back ( std::tuple < unsigned, unsigned, SymbolType > ( pointer - sbPointer, maxMatch, string.getContent ( ) [ pointer + maxMatch ] ) );
        pointer = pointer + maxMatch + 1;
    }
 
    return output;
}
 
// Method that return longest match of two substrings that are defined as incoming string and index of first staring letter
template < class SymbolType >
int LZ77Compression::equal ( const string::LinearString < SymbolType > & string, unsigned first1, unsigned last1, unsigned first2 ) {
 
    int steps = 0;
 
    while ( first1 < last1 ) {
        if ( string.getContent ( )[first1] != string.getContent ( )[first2] )
            return steps;
 
        first1++;
        first2++;
        steps++;
    }
 
    return steps;
}
 
} /* namespace compression */
 
} /* namespace stringology */