LZ77 - алгоритм - разрешение

Question

Я читал об этом алгоритме ... И я закодировал класс для сжатия, я еще не закодировал класс распаковки ...

Что вы думаете о коде?

Я думаю, что у меня есть проблема ... Моя кодификация: "position | length", но я верю, что этот метод будет держать меня в проблемах при плохой декомпрессии, потому что я не буду знать, если количество позиций и длина 2, 3, 4 цифры ...: S

некоторые советы будут приняты ...: D

Любые предложения будут приняты.

Основной файл:

      #include <iostream>
      #include "Compressor.h"

      int main() {
          Compressor c( "/home/facu/text.txt", 3);
          std::cout << c.get_TEXT_FILE() << std::endl;
          std::cout << c.get_TEXT_ENCONDED() << std::endl;
          c.save_file_encoded();
          return 0;
      }

заголовочный файл:

#ifndef _Compressor_H_
#define _Compressor_H_

#include <utility>
#include <string>

typedef unsigned int T_UI;

class Compressor
{
    public:
    //Constructor
    Compressor( const std::string &PATH, const T_UI minbytes = 3 );

    /** GET BUFFERS **/
    std::string get_TEXT_FILE() const;
    std::string get_TEXT_ENCONDED() const;
    /** END GET BUFFERS **/

    void save_file_encoded();

    private:
    /** BUFFERS **/
    std::string TEXT_FILE; // contains the text from an archive
    std::string TEXT_ENCODED; // contains the text encoded
    std::string W_buffer; // contains the string to analyze
    std::string W_inspection; // contains the string where will search matches
    /** END BUFFERS **/

    T_UI size_of_minbytes;
    T_UI size_w_insp; // The size of window inspection
    T_UI actual_byte;

    std::pair< T_UI, T_UI> v_codes; // Values to code text

    // Utilitaries functions
    void change_size_insp(){ size_w_insp =  TEXT_FILE.length() ; }
    bool inspection_empty() const;
    std::string convert_pair() const;
    // Encode algorythm
    void lz77_encode();
};

#endif

файл реализации:

#include <iostream>

#include <fstream>
using std::ifstream;
using std::ofstream;

#include <string>

#include <cstdlib>

#include <sstream>

#include "Compressor.h"

Compressor::Compressor(const std::string& PATH, const T_UI minbytes)
{
    std::string buffer = "";
    TEXT_FILE = "";
    ifstream input_text( PATH.c_str(), std::ios::in );
    if( !input_text )
    {
    std::cerr << "Can't open the text file";
    std::exit( 1 );
    }
    while( !input_text.eof() )
    {
    std::getline( input_text, buffer );
    TEXT_FILE += buffer;
    TEXT_FILE += "\n";
    buffer.clear();
    }
    input_text.close();
    change_size_insp();
    size_of_minbytes = minbytes;
    TEXT_ENCODED = "";
    W_buffer = "";
    W_inspection = "";
    v_codes.first = 0;
    v_codes.second = 0;
    actual_byte = 0;
    lz77_encode();
}

std::string Compressor::get_TEXT_FILE() const
{
    return TEXT_FILE;
}

std::string Compressor::get_TEXT_ENCONDED() const
{
    return TEXT_ENCODED;
}

bool Compressor::inspection_empty() const
{
    return ( size_w_insp != 0 );
}

std::string Compressor::convert_pair() const
{
    std::stringstream out;
    out << v_codes.first;
    out << "|";
    out << v_codes.second;
    return out.str();
}

void Compressor::save_file_encoded()
{
    std::string path("/home/facu/encoded.txt");
    ofstream out_txt( path.c_str(),std::ios::out );
    out_txt << TEXT_ENCODED << "\n";
    out_txt.close();
}

void Compressor::lz77_encode()
{
    while( inspection_empty() )
    {
    W_buffer = TEXT_FILE.substr( actual_byte, 1);
    if( W_inspection.find( W_buffer ) == W_inspection.npos )
    {
        // Cant find any byte from buffer
        TEXT_ENCODED += W_buffer;
        W_inspection += W_buffer;
        W_buffer.clear();
        ++actual_byte;
        --size_w_insp;
    }
    else
    {
        // We founded any byte from buffer in inspection
        v_codes.first = W_inspection.find( W_buffer );
        v_codes.second = 1;
        while( W_inspection.find( W_buffer ) != W_inspection.npos )
        {
        ++actual_byte;
        --size_w_insp;
        v_codes.second++;
        W_inspection += TEXT_FILE[actual_byte - 1];
        W_buffer += TEXT_FILE[actual_byte];
        }    
        ++actual_byte;
        --size_w_insp;
        if( v_codes.second > size_of_minbytes )
        TEXT_ENCODED += convert_pair();
        else
        TEXT_ENCODED += W_buffer;
        W_buffer.clear();
    }
    }
}

Спасибо!

Я кодирую класс распаковки:)

Answer 1

Я обычно рекомендую сначала написать декомпрессор, а затем написать компрессор, соответствующий ему.

Я рекомендую сначала заставить компрессор и соответствующий декомпрессор работать с копируемыми элементами фиксированного размера, а затем - при необходимости - настраивать их для создания / потребления копируемых элементов переменного размера.

Многие LZ77-подобные алгоритмы используют фиксированный размер в сжатом файле для представления как положения, так и длины; часто одна шестнадцатеричная цифра для длины и 3 шестнадцатеричных цифры для позиции, всего 2 байта.

"|" между положением и длиной копии не требуется.

Если вы действительно пытаетесь реализовать оригинальный алгоритм LZ77, ваш алгоритм сжатия должен всегда выдавать длину копии с фиксированной длиной (даже если она равна нулю), позицию с фиксированной длиной (когда длина равна нулю, вы также можете придерживаться нуля и здесь) и литерал с фиксированной длиной значение.

Некоторые LZ77-подобные форматы файлов подразделяются на «элементы», которые представляют собой фиксированную длину копии, пару позиций или одно или несколько литеральных значений. Если вы идете по этому пути, компрессор должен сначала как-то сообщить декомпрессору, представляет ли предстоящий элемент буквальное значение (я) или пару позиций длины копии. Один из многих способов сделать это - зарезервировать специальное значение позиции «0», которое вместо указания какой-либо позиции в выходном распакованном потоке, как и все другие значения позиции, вместо этого указывает следующие несколько литеральных значений во входном сжатом файле.

Почти все алгоритмы, подобные LZ77, сохраняют «смещение» назад от текущего местоположения в открытом тексте, а не «положение» вперед от начала открытого текста. Например, «1» представляет самый последний декодированный байт открытого текста, а не первый декодированный байт открытого текста.

Как декодер может определить, где заканчивается одно целое число и начинается ли следующее, когда сжатый файл содержит серию целых чисел? Есть 3 популярных ответа:

• Используйте код фиксированной длины, где вы указали в камне во время компиляции, как долго будет длиться каждое целое число. (Простейшие)
• Используйте код переменной длины и зарезервируйте специальный символ, такой как "|" указать конец кода.
• Используйте префиксный код переменной длины .
• другие подходы, такие как кодирование диапазона. (самое сложное)

http://en.wikibooks.org/wiki/Data_Compression

Иаков Зив и Авраам Лемпель; Универсальный алгоритм последовательного сжатия данных , IEEE транзакции по теории информации, 23 (3), с.337-343, май 1977 г.