Libreria di compressione LZW
Ho scritto una libreria che implementa la compressione e la decompressione LZW. Uno degli obiettivi di questo progetto era aiutarmi a familiarizzare con le moderne pratiche di sviluppo C ++ (provengo principalmente da un background Java e ho un'infarinatura di esperienza C).
Voglio usare questa libreria per comprimere i dati e trasmetterli in streaming su socket TCP per essere decompressi dal destinatario, il tutto senza memorizzare una versione compressa dei dati completi sul mittente o sulla macchina del destinatario (per scopi di hobby / non produzione).
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
Ho intenzione di sostituire unordered_map in lzw_encoder con un dizionario trie in una futura modifica.
Il mio codice mostra un modo ragionevole per utilizzare i flussi io?
Sento che il mio uso di lettura e scrittura non ha avuto una sensazione del moderno C ++ e mi chiedo se non sono a conoscenza di alcuni strumenti di libreria standard che mi aiutano con io binario. In particolare, non mi piace che ho usato al while(true)posto di alcune condizioni relative ai flussi di input. Inoltre, mi chiedevo se ci fosse un modo per fare io binario senza usare reinterpret_castper lanciare puntatori a dati numerici / binari char *.
Risposte
Ecco alcune cose che vedo che potrebbero aiutarti a migliorare il tuo codice.
Un file compresso non dovrebbe essere più piccolo?
Immagina la mia sorpresa quando ho scoperto che un file da 2037 byte (il codice sorgente lzw.cpp stesso) diventava 3524 byte quando "compresso!" L'algoritmo LZW originale codificava i valori a 8 bit in codici a 12 bit. Questo sembra codificare i valori a 8 bit come codici a 32 bit, il che è improbabile che offra molta compressione per file brevi come questo. Tuttavia, l'ho provato sulla versione in testo normale di Dracula di Bram Stoker e, come previsto, il file risultante era circa il 75% delle dimensioni dell'originale. Poiché è un flusso e non hai accesso alla lunghezza della sorgente, potrebbe non esserci molto che puoi fare al riguardo, ma probabilmente è una buona cosa per avvisare i potenziali utenti.
Ripensa l'interfaccia
Per poter utilizzare la compressione bisogna prima creare un oggetto e poi usarlo, magari così:
lzw::lzw_encoder lzw(in, out);
lzw.encode();
Non sarebbe più bello essere in grado di farlo?
lzw::encode(in, out);
Scrive gli inizializzatori dei membri in ordine di dichiarazione
La lzw_encoderclasse ha questo costruttore
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;
}
}
Sembra corretto, ma in realtà current_codeverrà inizializzato prima is e osperché i membri vengono sempre inizializzati in ordine di dichiarazione e current_codevengono dichiarati prima isin questa classe. Per evitare di fuorviare un altro programmatore, potresti semplicemente omettere current_codepoiché è già inizializzato dalla dichiarazione:
uint32_t current_code = 0;
Usa algoritmi standard dove appropriato
L'inizializzazione del codebook usa questo:
for (current_code = 0; current_code < 256; ++current_code) {
codebook[std::string(1, static_cast<char>(current_code))] = current_code;
}
Questo può essere migliorato in diversi modi. Innanzitutto, sappiamo già quanto sarà grande il codebook, quindi possiamo ridurre il numero di riallocazioni di memoria dicendo al compilatore che le informazioni:
codebook.reserve(256);
Successivamente, possiamo evitare il cast e guadagnare un po 'di efficienza usando emplace:
for (current_code = 0; current_code < 256; ++current_code) {
codebook.emplace(std::string(1, current_code), current_code);
}
Consiglierei anche di sostituire 256qui con un file static constexpr initial_codebook_size.
Fai attenzione alle differenze di endianness
Il codice attualmente contiene queste righe:
auto code_val = codebook[current];
os.write(reinterpret_cast<char *>(&code_val), sizeof(code_val));
Il problema è che a seconda che si tratti di una macchina big-endian o little-endian, la codifica sarà diversa. Se il flusso compresso deve essere inviato a una macchina diversa, questo deve essere coerente. Considera l'idea di utilizzare qualcosa come la htonlfunzione POSIX qui.
Considera i cicli di ristrutturazione
Il problema while(true)è che nasconde la condizione di uscita dal ciclo. Invece di questo:
while (true) {
is.read(buffer, ENCODER_BUFFER_SIZE);
auto read_length = is.gcount();
if (read_length == 0)
break;
// etc
}
Considera qualcosa del genere:
while (is.read(buffer, ENCODER_BUFFER_SIZE)) {
// handle full block
}
if (is.gcount()) {
// handle final partial block
}
Comprendi l'uso dei flussi
È possibile che il chiamante abbia impostato uno o entrambi i flussi per generare un'eccezione in caso di errore come la fine del file durante la lettura. Ignoralo o gestiscilo in modo appropriato.
Considera l'idea di aggiungere funzioni utili
La gestione dei blocchi per la codifica e la decodifica potrebbe essere trasformata in funzioni all'interno dello spazio dei nomi. Ciò renderebbe la ristrutturazione dei loop come menzionato sopra un po 'più semplice e pulita e isolerebbe la gestione delle strutture dati dall'I / O del flusso di base. Ciò potrebbe rendere le cose un po 'più facili quando ti converti in un trie. Ecco la mia riscrittura del ciclo:
while (is.read(buffer, ENCODER_BUFFER_SIZE)) {
encode_buffer(buffer, ENCODER_BUFFER_SIZE);
}
encode_buffer(buffer, is.gcount());