Biblioteca de compressão LZW

Aug 17 2020

Eu escrevi uma biblioteca que implementa compactação e descompressão LZW. O objetivo deste projeto era me ajudar a me familiarizar com as práticas de desenvolvimento C ++ modernas (principalmente venho de Java e tenho um conhecimento superficial em C).

Quero usar essa biblioteca para compactar dados e transmiti-los por meio de soquetes TCP para serem descompactados pelo destinatário, tudo sem armazenar uma versão compactada dos dados completos no remetente ou na máquina do destinatário (para propósitos de hobby / não produção).

lzw.hpp

#pragma once

#include <iostream>
#include <optional>
#include <unordered_map>
#include <vector>

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<std::string, uint32_t> codebook;
  std::istream &is;
  std::ostream &os;
};

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

  void decode();

private:
  std::vector<std::string> codebook;
  std::optional<uint32_t> 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<char>(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<char *>(&code_val), sizeof(code_val));

        current.clear();
        current.push_back(buffer[i]);
      }
    }
  }
  if (current.size()) {
    auto code_val = codebook[current];
    os.write(reinterpret_cast<char *>(&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<char>(i));
  }
}

void lzw_decoder::decode() {
  uint32_t buffer[DECODER_BUFFER_SIZE];
  while (true) {
    is.read(reinterpret_cast<char *>(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

Pretendo substituir o unordered_map no lzw_encoder por um dicionário em uma edição futura.

Meu código exibe uma maneira razoável de usar fluxos IO?

Eu sinto que meu uso de leitura e escrita não tem uma sensação de C ++ moderno, e estou me perguntando se não conheço algumas ferramentas de biblioteca padrão para me ajudar com io binário. Em particular, não gosto de usar em while(true)vez de alguma condição relacionada aos fluxos de entrada. Além disso, eu queria saber se havia uma maneira de fazer io binário sem usar reinterpret_castpara lançar ponteiros de dados numéricos / binários char *.

Respostas

2 Edward Aug 18 2020 at 21:35

Aqui estão algumas coisas que vejo que podem ajudá-lo a melhorar seu código.

Um arquivo compactado não deveria ser menor?

Imagine minha surpresa quando descobri que um arquivo de 2037 bytes (o próprio código-fonte lzw.cpp) tornou-se 3524 bytes quando "compactado!" O algoritmo LZW original codificou valores de 8 bits em códigos de 12 bits. Isso parece codificar valores de 8 bits como códigos de 32 bits, o que é improvável que ofereça muita compactação para arquivos curtos como este. Eu, no entanto, experimentei na versão em texto simples do Drácula de Bram Stoker e, como esperado, o arquivo resultante tinha cerca de 75% do tamanho do original. Como é um stream e você não tem acesso ao comprimento da fonte, pode não haver muito que você possa fazer a respeito, mas provavelmente é uma boa coisa alertar os usuários em potencial.

Repense a interface

Para usar a compressão, deve-se primeiro criar um objeto e depois usá-lo, talvez assim:

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

Não seria melhor simplesmente ser capaz de fazer isso?

lzw::encode(in, out);

Grave inicializadores de membro na ordem de declaração

A lzw_encoderclasse tem este construtor

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<char>(current_code))] = current_code;
  }
}

Parece bom, mas, na verdade, current_codeserá inicializado antes is e osporque os membros são sempre inicializados na ordem de declaração e current_codesão declarados antes isnesta classe. Para evitar enganar outro programador, você pode simplesmente omitir, current_codeuma vez que já foi inicializado pela declaração:

uint32_t current_code = 0;

Use algoritmos padrão quando apropriado

A inicialização do livro de código usa isto:

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

Isso pode ser melhorado de várias maneiras. Em primeiro lugar, já sabemos o quão grande será o livro de códigos, então podemos reduzir o número de realocações de memória, dizendo ao compilador essas informações:

codebook.reserve(256);

Em seguida, podemos evitar o elenco e ganhar um pouco de eficiência usando emplace:

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

Eu também recomendo substituir 256aqui por um static constexpr initial_codebook_size.

Cuidado com as diferenças de endianismo

O código atualmente contém estas linhas:

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

O problema é que, dependendo se esta é uma máquina big-endian ou little-endian, a codificação será diferente. Se o fluxo compactado for enviado para uma máquina diferente, isso precisa ser consistente. Considere usar algo como a htonlfunção POSIX aqui.

Considere a reestruturação de loops

O problema while(true)é que ele oculta a condição de saída do loop. Em vez disso:

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

Considere algo assim:

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

Entenda o uso de fluxos

É possível que o chamador tenha definido um ou ambos os fluxos para lançar uma exceção ao encontrar uma falha, como fim de arquivo na leitura. Substitua isso ou trate-o de maneira adequada.

Considere adicionar funções de conveniência

A manipulação de blocos para codificação e decodificação pode ser transformada em funções dentro do namespace. Isso tornaria a reestruturação dos loops conforme mencionado acima um pouco mais fácil e limpa e isolaria o manuseio das estruturas de dados da E / S de fluxo básico. Isso pode tornar as coisas um pouco mais fáceis quando você converter em um trie. Aqui está minha reescrita do loop:

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