LZW圧縮ライブラリ
LZWの圧縮と解凍を実装するライブラリを作成しました。このプロジェクトの目標は、最新のC ++開発プラクティスを理解するのに役立つことでした（私は主にJavaのバックグラウンドを持っており、Cの経験が少しあります）。
このライブラリを使用してデータを圧縮し、TCPソケットを介してストリーミングして、受信者が解凍します。すべてのデータの圧縮バージョンを送信者または受信者のマシンに保存する必要はありません（趣味/非本番目的）。
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
将来の編集で、lzw_encoderのunordered_mapを辞書トライに置き換える予定です。
私のコードは、ioストリームを使用するための合理的な方法を示していますか？
私の読み取りと書き込みの使用法は現代のC ++の感覚を持っていなかったと感じており、バイナリioを支援するいくつかの標準ライブラリツールを知らないのではないかと思います。特に、while(true)入力ストリームに関連する条件の代わりに使用したものは好きではありません。また、reinterpret_cast数値/バイナリデータポインタをにキャストするために使用せずにバイナリioを実行する方法があるかどうか疑問に思いましたchar *。
回答
コードの改善に役立つと思われることがいくつかあります。
圧縮ファイルを小さくするべきではありませんか？
2037バイトのファイル（lzw.cppソースコード自体）が「圧縮」されたときに3524バイトになったことを発見したときの驚きを想像してみてください。元のLZWアルゴリズムは、8ビット値を12ビットコードにエンコードしました。これは、8ビット値を32ビットコードとしてエンコードしているように見えます。これは、このような短いファイルに対して多くの圧縮を提供する可能性は低いです。ただし、Bram StokerのDraculaのプレーンテキストバージョンで試してみたところ、予想どおり、結果のファイルは元のファイルのサイズの約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<char>(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<char>(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ます。
エンディアンの違いに注意してください
現在、コードには次の行が含まれています。
auto code_val = codebook[current];
os.write(reinterpret_cast<char *>(&code_val), sizeof(code_val));
これがビッグエンディアンとリトルエンディアンのどちらのマシンであるかによって、エンコーディングが異なるという問題があります。圧縮されたストリームを別のマシンに送信する場合は、一貫性を保つ必要があります。htonlここでPOSIX関数のようなものを使用することを検討してください。
ループの再構築を検討してください
の問題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から分離されます。それはあなたがトライに変換するときに物事を少し簡単にするかもしれません。これが私のループの書き直しです：
while (is.read(buffer, ENCODER_BUFFER_SIZE)) {
encode_buffer(buffer, ENCODER_BUFFER_SIZE);
}
encode_buffer(buffer, is.gcount());