LZW压缩库

Question

我编写了一个实现LZW压缩和解压缩的库。这个项目的目标是帮助我熟悉现代的C++开发实践(我主要来自于一个Java背景，并且有少量的C经验)。

我想使用这个库来压缩数据并通过TCP套接字进行流，以便由接收方解压缩，所有这些都不需要在发送方或接收者的机器上存储完整数据的压缩版本(用于业余/非生产目的)。

lzw.hpp

#pragma once

#include 
#include 
#include 
#include 

namespace lzw {

class lzw_encoder {
public:
  lzw_encoder(std::istream &is, std::ostream &os);

  void encode();

private:
  uint32_t current_code = 0;
  std::string current;

  std::unordered_map codebook;
  std::istream &is;
  std::ostream &os;
};

class lzw_decoder {
public:
  lzw_decoder(std::istream &is, std::ostream &os);

  void decode();

private:
  std::vector codebook;
  std::optional prev;
  std::istream &is;
  std::ostream &os;
};
} // namespace lzw

lzw.cpp

#include "lzw.hpp"

namespace lzw {

static constexpr size_t ENCODER_BUFFER_SIZE = 256;

static constexpr size_t DECODER_BUFFER_SIZE = 64;

lzw_encoder::lzw_encoder(std::istream &is, std::ostream &os)
    : is(is), os(os), current_code(0) {
  for (current_code = 0; current_code < 256; ++current_code) {
    codebook[std::string(1, static_cast(current_code))] = current_code;
  }
}

void lzw_encoder::encode() {
  char buffer[ENCODER_BUFFER_SIZE];

  while (true) {
    is.read(buffer, ENCODER_BUFFER_SIZE);
    auto read_length = is.gcount();
    if (read_length == 0)
      break;

    for (size_t i = 0; i < read_length; ++i) {
      current.push_back(buffer[i]);

      auto iter = codebook.find(current);
      if (iter == codebook.end()) {
        codebook[current] = current_code++;

        current.pop_back();
        auto code_val = codebook[current];
        os.write(reinterpret_cast(&code_val), sizeof(code_val));

        current.clear();
        current.push_back(buffer[i]);
      }
    }
  }
  if (current.size()) {
    auto code_val = codebook[current];
    os.write(reinterpret_cast(&code_val), sizeof(code_val));
  }
}

lzw_decoder::lzw_decoder(std::istream &is, std::ostream &os)
    : is(is), os(os), prev{} {
  for (int i = 0; i < 256; ++i) {
    codebook.emplace_back(1, static_cast(i));
  }
}

void lzw_decoder::decode() {
  uint32_t buffer[DECODER_BUFFER_SIZE];
  while (true) {
    is.read(reinterpret_cast(buffer),
            DECODER_BUFFER_SIZE * sizeof(uint32_t));
    auto read_length = is.gcount() / sizeof(uint32_t);
    if (read_length == 0)
      break;

    for (size_t i = 0; i < read_length; ++i) {
      if (buffer[i] < codebook.size()) {
        os << codebook[buffer[i]];
        if (prev) {
          codebook.push_back(codebook[*prev] + codebook[buffer[i]].front());
        }
      } else {
        codebook.push_back(codebook[*prev] + codebook[*prev].front());
        os << codebook.back();
      }
      prev = buffer[i];
    }
  }
}
} // namespace lzw

我计划在将来的编辑中用字典trie替换unordered_map中的lzw_encoder。

我的代码是否展示了一种合理的使用io流的方法？

我觉得我对读和写的使用没有现代C++的感觉，我想知道我是否不知道有一些标准的库工具可以帮助我处理二进制io。特别是，我不喜欢使用while(true)而不是与输入流相关的一些条件。另外，我想知道是否有一种不使用reinterpret_cast将数字/二进制数据指针转换为char *的二进制io的方法。

Answer 1

下面是我看到的一些可以帮助您改进代码的东西。

不应该压缩文件更小吗？

想象一下，当我发现一个2037字节的文件( lzw.cpp源代码本身)在“压缩”时变成3524字节时，我感到惊讶！最初的LZW算法将8位值编码成12位代码.这似乎是将8位值编码为32位代码，这不太可能为这样的短文件提供太多的压缩。但是，我确实在布拉姆斯托克氏德古拉的纯文本版本上尝试了它，正如预期的那样，结果文件的大小大约是原始文件的75%。因为它是一个流，而且您无法访问源的长度，所以您可能对它无能为力，但是警告潜在的用户可能是件好事。

重新思考接口

为了使用压缩，必须首先创建一个对象，然后使用它，也许如下所示：

lzw::lzw_encoder lzw(in, out);
lzw.encode();

就这么做不是更好吗？

lzw::encode(in, out);

按声明顺序写入成员初始化器

lzw_encoder类具有以下构造函数

lzw_encoder::lzw_encoder(std::istream &is, std::ostream &os)
    : is(is), os(os), current_code(0) {
  for (current_code = 0; current_code < 256; ++current_code) {
    codebook[std::string(1, static_cast(current_code))] = current_code;
  }
}

这看起来不错，但实际上，current_code将在is和os之前初始化，因为成员总是按声明顺序初始化，而在该类中，current_code是在is之前声明的。为了避免误导其他程序员，您可以简单地省略current_code，因为声明已经初始化了它：

uint32_t current_code = 0;

在适当的情况下使用标准算法

初始化代码本使用如下：

for (current_code = 0; current_code < 256; ++current_code) {
  codebook[std::string(1, static_cast(current_code))] = current_code;
}

这可以通过多种方式加以改进。首先，我们已经知道代码本的大小，这样我们就可以通过告诉编译器这个信息来减少内存重新分配的数量：

codebook.reserve(256);

接下来，我们可以通过使用emplace来避免强制转换并获得一定的效率：

for (current_code = 0; current_code < 256; ++current_code) {
    codebook.emplace(std::string(1, current_code), current_code);
}

我还建议用一个256代替static constexpr initial_codebook_size。

‘.’.‘K126

’

目前的代码包含以下几行：

auto code_val = codebook[current];
os.write(reinterpret_cast(&code_val), sizeof(code_val));

问题在于，取决于这是大端机器还是小端机器，编码将是不同的。如果要将压缩的流发送到另一台机器，则需要保持一致。考虑在这里使用类似于POSIX htonl函数的东西。

考虑重组循环

while(true)的问题在于它隐藏了循环退出条件。而不是这样：

while (true) {
    is.read(buffer, ENCODER_BUFFER_SIZE);
    auto read_length = is.gcount();
    if (read_length == 0)
      break;
    // etc
}

考虑一下这样的事情：

while (is.read(buffer, ENCODER_BUFFER_SIZE)) {
    // handle full block
}
if (is.gcount()) {
    // handle final partial block
}

理解流

的使用

调用方可能设置了一个或两个流，以便在遇到故障时抛出异常，例如读取时的文件结束。要么重写它，要么适当地处理它。

考虑添加方便函数

代码块和解码块的处理都可以转换为命名空间中的函数。这将使上面提到的循环的重组变得更容易和更简洁，并将数据结构的处理与基本的流I/O隔离开来，这可能会使您在转换为trie时更容易一些。下面是我对循环的重写：

while (is.read(buffer, ENCODER_BUFFER_SIZE)) {
  encode_buffer(buffer, ENCODER_BUFFER_SIZE);
}
encode_buffer(buffer, is.gcount());