Bibliothèque de compression LZW
J'ai écrit une bibliothèque qui implémente la compression et la décompression LZW. Un objectif de ce projet était de m'aider à me familiariser avec les pratiques de développement C ++ modernes (je viens principalement d'un fond Java et j'ai un peu d'expérience en C).
Je souhaite utiliser cette bibliothèque pour compresser les données et les diffuser sur des sockets TCP à décompresser par le destinataire, le tout sans stocker une version compressée des données complètes sur l'expéditeur ou sur la machine du destinataire (à des fins de loisirs / non-production).
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
Je prévois de remplacer unordered_map dans le lzw_encoder par un trie de dictionnaire dans une prochaine édition.
Mon code présente-t-il un moyen raisonnable d'utiliser les flux io?
J'ai le sentiment que mon utilisation de la lecture et de l'écriture n'avait pas le sentiment du C ++ moderne, et je me demande si je ne connais pas certains outils de bibliothèque standard pour m'aider avec io binaire. En particulier, je n'aime pas le fait que j'ai utilisé à la while(true)place d'une condition liée aux flux d'entrée. De plus, je me demandais s'il y avait un moyen de faire io binaire sans utiliser reinterpret_castpour convertir des pointeurs de données numériques / binaires char *.
Réponses
Voici quelques éléments que je vois qui peuvent vous aider à améliorer votre code.
Un fichier compressé ne devrait-il pas être plus petit?
Imaginez ma surprise quand j'ai découvert qu'un fichier de 2037 octets (le code source lzw.cpp lui-même) devenait 3524 octets lorsqu'il était "compressé"! L'algorithme LZW d'origine codait des valeurs 8 bits en codes 12 bits. Cela semble encoder des valeurs 8 bits sous forme de codes 32 bits, ce qui est peu susceptible d'offrir beaucoup de compression pour des fichiers courts comme celui-ci. Je, cependant, essayer sur la version texte de Bram Stoker Dracula et, comme prévu, le fichier résultant était d' environ 75% de la taille de l'original. Comme il s'agit d'un flux et que vous n'avez pas accès à la longueur de la source, vous ne pouvez peut-être pas faire grand-chose à ce sujet, mais c'est probablement une bonne chose d'avertir les utilisateurs potentiels.
Repenser l'interface
Pour utiliser la compression, il faut d'abord créer un objet puis l' utiliser, peut-être comme ceci:
lzw::lzw_encoder lzw(in, out);
lzw.encode();
Ne serait-il pas plus agréable de pouvoir le faire?
lzw::encode(in, out);
Ecrire les initialiseurs de membres dans l'ordre des déclarations
La lzw_encoderclasse a ce constructeur
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;
}
}
Cela semble correct, mais en fait, current_codesera initialisé avant is et osparce que les membres sont toujours initialisés dans l' ordre de déclaration et current_codesont déclarés avant isdans cette classe. Pour éviter de tromper un autre programmeur, vous pouvez simplement omettre current_codecar il est déjà initialisé par la déclaration:
uint32_t current_code = 0;
Utilisez des algorithmes standard le cas échéant
L'initialisation du livre de codes utilise ceci:
for (current_code = 0; current_code < 256; ++current_code) {
codebook[std::string(1, static_cast<char>(current_code))] = current_code;
}
Cela peut être amélioré de plusieurs manières. Tout d'abord, nous savons déjà quelle sera la taille du livre de codes afin de réduire le nombre de réallocations de mémoire en indiquant au compilateur ces informations:
codebook.reserve(256);
Ensuite, nous pouvons éviter le casting et gagner un peu d'efficacité en utilisant emplace:
for (current_code = 0; current_code < 256; ++current_code) {
codebook.emplace(std::string(1, current_code), current_code);
}
Je recommanderais également de remplacer 256ici par un fichier static constexpr initial_codebook_size.
Méfiez-vous des différences d'endian-ness
Le code contient actuellement ces lignes:
auto code_val = codebook[current];
os.write(reinterpret_cast<char *>(&code_val), sizeof(code_val));
Le problème est que selon qu'il s'agit d'une machine big-endian ou little-endian, l'encodage sera différent. Si le flux compressé est destiné à être envoyé vers une autre machine, cela doit être cohérent. Pensez à utiliser quelque chose comme la htonlfonction POSIX ici.
Envisagez de restructurer les boucles
Le problème avec while(true)est qu'il masque la condition de sortie de la boucle. Au lieu de cela:
while (true) {
is.read(buffer, ENCODER_BUFFER_SIZE);
auto read_length = is.gcount();
if (read_length == 0)
break;
// etc
}
Considérez quelque chose comme ceci:
while (is.read(buffer, ENCODER_BUFFER_SIZE)) {
// handle full block
}
if (is.gcount()) {
// handle final partial block
}
Comprendre l'utilisation des flux
Il est possible que l'appelant ait défini un ou les deux flux pour lever une exception en cas d'échec tel que la fin du fichier en lecture. Remplacez-le ou gérez-le de manière appropriée.
Pensez à ajouter des fonctions pratiques
La gestion des blocs pour l'encodage et pour le décodage peut être transformée en fonctions dans l'espace de noms. Cela rendrait la restructuration des boucles comme mentionné ci-dessus un peu plus facile et plus propre et isolerait la gestion des structures de données des E / S de flux de base. Cela peut rendre les choses un peu plus faciles lorsque vous vous convertissez en trie. Voici ma réécriture de la boucle:
while (is.read(buffer, ENCODER_BUFFER_SIZE)) {
encode_buffer(buffer, ENCODER_BUFFER_SIZE);
}
encode_buffer(buffer, is.gcount());