c++ - LZ77 - 算法 - 分辨率

Question

我正在阅读有关此算法的信息...我编写了一个要压缩的类，但我还没有编写解压缩类的代码...

你觉得这段代码怎么样？

我想我遇到了一个问题......我的编码是:“位置|长度”，但我相信这种方法会让我在解压时遇到问题，因为我不知道位置和长度的数量是否是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 的算法在压缩文件中使用固定大小来表示位置和长度；通常1个16进制的长度和3个16进制的位置，共2个字节。

“|”位置和复制长度之间是不必要的。

如果你真的想实现原始的 LZ77 算法，您的压缩算法需要始终发出固定长度的复制长度(即使它为零)、固定长度的位置(当长度为零时，您也可以在此处粘贴零)和固定长度的文字值(value)。

一些类似 LZ77 的文件格式分为“项目”，这些项目要么是固定长度的复制长度、位置对，要么是一个或多个文字值。如果你走那条路，压缩器必须首先以某种方式告诉解压缩器即将到来的项目是代表文字值还是复制长度，位置对。许多方法之一是保留一个特殊的“0”位置值，而不是像所有其他位置值一样指示输出解压缩流中的某个位置，而是指示输入压缩文件中接下来的几个文字值。

几乎所有类似 LZ77 的算法都存储明文中从当前位置向后的“偏移量”，而不是从明文开头向前的“位置”。例如，“1”表示最近解码的明文字节，而不是第一个解码的明文字节。

当压缩文件包含一系列整数时，解码器如何判断一个整数在哪里结束，下一个整数从哪里开始？有 3 个流行的答案:

• 使用固定长度的代码，您在编译时就已经确定了每个整数的长度。 (最简单的)
• 使用变长代码，并保留“|”等特殊符号指示代码结束。
• 使用可变长度 prefix code .
• 其他方法，例如范围编码。 (最复杂)

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

Jacob Ziv 和 Abraham Lempel； A Universal Algorithm for Sequential Data Compression , IEEE Transactions on Information Theory，23(3)，pp.337-343，1977 年 5 月。