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 个十六进制数字，位置为 3 个十六进制数字，共 2 个字节。

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

如果你真的想实现原始的 LZ77 算法，你的压缩算法需要总是发出定长复制长度（即使为零），定长位置（当长度为零时，你也可以在这里也贴零）和固定长度的文字值。

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

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

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

• 使用固定长度的代码，您在编译时确定每个整数的长度。（最简单）
• 使用变长代码，并保留一个特殊符号，如“|” 表示代码结束。
• 使用可变长度的前缀代码。
• 其他方法，例如范围编码。（最复杂）

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

雅各布·齐夫和亚伯拉罕·伦佩尔；A Universal Algorithm for Sequential Data Compression，IEEE Transactions on Information Theory，23(3)，pp.337-343，1977 年 5 月。