Biblioteca de compresión LZW
Escribí una biblioteca que implementa la compresión y descompresión LZW. Un objetivo de este proyecto era ayudarme a familiarizarme con las prácticas modernas de desarrollo de C ++ (principalmente vengo de una experiencia en Java y tengo un poco de experiencia en C).
Quiero usar esta biblioteca para comprimir datos y transmitirlos a través de sockets TCP para que el destinatario los descomprima, todo sin almacenar una versión comprimida de los datos completos en la máquina del remitente o del destinatario (con fines de afición / no producción).
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
Planeo reemplazar el unordered_map en el lzw_encoder con un diccionario trie en una edición futura.
¿Mi código muestra una forma razonable de usar io streams?
Siento que mi uso de lectura y escritura no tenía una sensación de C ++ moderno, y me pregunto si no conozco algunas herramientas de biblioteca estándar que me ayuden con io binario. En particular, no me gusta que utilicé en while(true)
lugar de alguna condición relacionada con los flujos de entrada. Además, me preguntaba si había una manera de hacer io binario sin usar reinterpret_cast
para lanzar punteros de datos numéricos / binarios a char *
.
Respuestas
Aquí hay algunas cosas que veo que pueden ayudarlo a mejorar su código.
¿No debería ser un archivo comprimido más pequeño?
Imagínese mi sorpresa cuando descubrí que un archivo de 2037 bytes (el código fuente lzw.cpp en sí mismo) se convertía en 3524 bytes cuando estaba "comprimido". El algoritmo LZW original codificó valores de 8 bits en códigos de 12 bits. Esto parece estar codificando valores de 8 bits como códigos de 32 bits, lo que es poco probable que ofrezca mucha compresión para archivos cortos como este. Yo, sin embargo, probarlo en la versión de texto de Bram Stoker Drácula y, como era de esperar, el archivo resultante fue de alrededor del 75% del tamaño del original. Debido a que es una transmisión y no tiene acceso a la longitud de la fuente, puede que no haya mucho que pueda hacer al respecto, pero probablemente sea bueno advertir a los usuarios potenciales.
Repensar la interfaz
Para usar la compresión, primero se debe crear un objeto y luego usarlo, tal vez así:
lzw::lzw_encoder lzw(in, out);
lzw.encode();
¿No sería mejor poder hacer esto?
lzw::encode(in, out);
Escribir inicializadores de miembros en orden de declaración
La lzw_encoder
clase tiene este constructor
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;
}
}
Eso se ve bien, pero de hecho, current_code
se inicializará antes is
y os
porque los miembros siempre se inicializan en el orden de declaración y current_code
se declaran antes is
en esta clase. Para evitar engañar a otro programador, simplemente puede omitir, current_code
ya que la declaración ya lo inicializa:
uint32_t current_code = 0;
Utilice algoritmos estándar cuando sea apropiado
La inicialización del libro de códigos usa esto:
for (current_code = 0; current_code < 256; ++current_code) {
codebook[std::string(1, static_cast<char>(current_code))] = current_code;
}
Esto se puede mejorar de varias formas. Primero, ya sabemos qué tan grande será el libro de códigos, por lo que podemos reducir el número de reasignaciones de memoria diciéndole al compilador esa información:
codebook.reserve(256);
A continuación, podemos evitar el lanzamiento y ganar un poco de eficiencia usando emplace
:
for (current_code = 0; current_code < 256; ++current_code) {
codebook.emplace(std::string(1, current_code), current_code);
}
También recomendaría reemplazar 256
aquí con un static constexpr initial_codebook_size
.
Cuidado con las diferencias de endianidad
El código contiene actualmente estas líneas:
auto code_val = codebook[current];
os.write(reinterpret_cast<char *>(&code_val), sizeof(code_val));
El problema es que, dependiendo de si se trata de una máquina big-endian o little-endian, la codificación será diferente. Si la secuencia comprimida está destinada a enviarse a una máquina diferente, debe ser coherente. Considere usar algo como la htonl
función POSIX aquí.
Considere reestructurar los bucles
El problema while(true)
es que oculta la condición de salida del bucle. En lugar de esto:
while (true) {
is.read(buffer, ENCODER_BUFFER_SIZE);
auto read_length = is.gcount();
if (read_length == 0)
break;
// etc
}
Considere algo como esto:
while (is.read(buffer, ENCODER_BUFFER_SIZE)) {
// handle full block
}
if (is.gcount()) {
// handle final partial block
}
Comprender el uso de arroyos
Es posible que la persona que llama haya configurado una o ambas transmisiones para generar una excepción al encontrar una falla, como el final del archivo al leer. O anule esto o manipúlelo apropiadamente.
Considere agregar funciones de conveniencia
El manejo de bloques para codificar y decodificar podría convertirse en funciones dentro del espacio de nombres. Esto haría que la reestructuración de los bucles como se mencionó anteriormente sea un poco más fácil y más limpia y aislaría el manejo de las estructuras de datos de la E / S de flujo básica. Eso puede facilitar un poco las cosas cuando se convierte a un trie. Aquí está mi reescritura del ciclo:
while (is.read(buffer, ENCODER_BUFFER_SIZE)) {
encode_buffer(buffer, ENCODER_BUFFER_SIZE);
}
encode_buffer(buffer, is.gcount());