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个流行的答案：

• 使用固定长度的代码，您已经在编译时固定地设置了每个整数的长度。(最简单的)范围编码使用可变长度的代码，并保留一个特殊的符号，如"|“来表示end-of-code.
• Use可变长度的prefix code.
• other方法，如
• 。(最复杂的)

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

雅各布·泽夫和亚伯拉罕·兰佩尔；A Universal Algorithm for Sequential Data Compression，IEEE信息理论学报，23(3)，pp.337-343,1977年5月。