LZW Sıkıştırma Kitaplığı
LZW sıkıştırma ve açma işlemini uygulayan bir kitaplık yazdım. Bu projenin amacı, kendimi modern C ++ geliştirme uygulamaları hakkında bilgilendirmeme yardımcı olmaktı (öncelikle Java geçmişinden geliyorum ve çok az C deneyimim var).
Bu kitaplığı, verileri sıkıştırmak ve alıcı tarafından sıkıştırılmış TCP soketleri üzerinden yayınlamak için kullanmak istiyorum, bunların tümünü gönderen veya alıcının makinesinde (hobi / üretim dışı amaçlarla) tüm verilerin sıkıştırılmış bir sürümünü depolamadan.
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
Gelecekteki bir düzenlemede lzw_encoder'daki unordered_map'i bir sözlük trie ile değiştirmeyi planlıyorum.
Kodum, io akışlarını kullanmanın makul bir yolunu gösteriyor mu?
Okuma ve yazma kullanımımın modern C ++ hissine sahip olmadığını hissediyorum ve ikili io konusunda bana yardımcı olacak bazı standart kütüphane araçlarının farkında olup olmadığımı merak ediyorum. Özellikle, while(true)
girdi akışlarıyla ilgili bazı koşullar yerine kullanmamdan hoşlanmıyorum . Ayrıca, reinterpret_cast
sayısal / ikili veri işaretçileri çevirmek için kullanmadan ikili io yapmanın bir yolu olup olmadığını merak ediyordum char *
.
Yanıtlar
Kodunuzu geliştirmenize yardımcı olabilecek bazı şeyler burada verilmiştir.
Sıkıştırılmış bir dosyanın daha küçük olması gerekmez mi?
2037 baytlık bir dosyanın (lzw.cpp kaynak kodunun kendisi) "sıkıştırıldığında" 3524 bayt olduğunu keşfettiğimde şaşırdığımı hayal edin! Orijinal LZW algoritması 8 bitlik değerleri 12 bitlik kodlara kodladı. Bu, 8 bitlik değerleri 32 bit kodlar olarak kodluyor gibi görünüyor ki bu, bunun gibi kısa dosyalar için fazla sıkıştırma sunma olasılığı düşük. Bununla birlikte, bunu Bram Stoker'ın Drakula'sının düz metin sürümünde denedim ve beklendiği gibi ortaya çıkan dosya orijinalin boyutunun yaklaşık% 75'iydi. Bu bir akış olduğu ve kaynağın uzunluğuna erişiminiz olmadığı için, bu konuda yapabileceğiniz pek bir şey olmayabilir, ancak potansiyel kullanıcıları hakkında uyarmak muhtemelen iyi bir şeydir.
Arayüzü yeniden düşünün
Sıkıştırmayı kullanmak için, önce bir nesne oluşturmalı ve sonra onu kullanmalı, belki şu şekilde:
lzw::lzw_encoder lzw(in, out);
lzw.encode();
Bunu yapabilmek daha güzel olmaz mıydı?
lzw::encode(in, out);
Üye başlatıcıları bildirim sırasına göre yazın
lzw_encoder
Sınıfı bu Oluşturucu sahip
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;
}
}
Bakışlar cezası Yani, ama aslında, current_code
başlatılır önce is
ve os
üyeleri her zaman başlatılır çünkü beyanı düzen ve current_code
daha önce bildirilmiş is
bu sınıfta. Başka bir programcıyı yanıltmaktan kaçınmak için current_code
, bildirimle zaten başlatıldığı için atlayabilirsiniz :
uint32_t current_code = 0;
Uygun olduğunda standart algoritmalar kullanın
Kod kitabının başlatılması şunu kullanır:
for (current_code = 0; current_code < 256; ++current_code) {
codebook[std::string(1, static_cast<char>(current_code))] = current_code;
}
Bu, birkaç yolla geliştirilebilir. İlk olarak, kod kitabının ne kadar büyük olacağını zaten biliyoruz, böylece derleyiciye şu bilgileri söyleyerek bellek yeniden tahsislerinin sayısını azaltabiliriz:
codebook.reserve(256);
Daha sonra, şunları kullanarak dökümden kaçınabilir ve biraz verimlilik kazanabiliriz emplace
:
for (current_code = 0; current_code < 256; ++current_code) {
codebook.emplace(std::string(1, current_code), current_code);
}
Ayrıca 256
burayı bir static constexpr initial_codebook_size
.
Sonsuzluk farklılıklarına dikkat edin
Kod şu anda şu satırları içeriyor:
auto code_val = codebook[current];
os.write(reinterpret_cast<char *>(&code_val), sizeof(code_val));
Sorun şu ki, bunun bir big-endian veya little-endian makinesi olmasına bağlı olarak, kodlama farklı olacaktır. Sıkıştırılmış akışın farklı bir makineye gönderilmesi amaçlanıyorsa, bunun tutarlı olması gerekir. htonl
Burada POSIX işlevi gibi bir şey kullanmayı düşünün .
Döngüleri yeniden yapılandırmayı düşünün
Sorun while(true)
, döngüden çıkış koşulunu gizlemesidir. Bunun yerine:
while (true) {
is.read(buffer, ENCODER_BUFFER_SIZE);
auto read_length = is.gcount();
if (read_length == 0)
break;
// etc
}
Bunun gibi bir şey düşünün:
while (is.read(buffer, ENCODER_BUFFER_SIZE)) {
// handle full block
}
if (is.gcount()) {
// handle final partial block
}
Akışların kullanımını anlayın
Arayanın, okuma sırasında dosya sonu gibi bir hatayla karşılaşıldığında bir istisna atması için akışlardan birini veya her ikisini ayarlamış olması mümkündür . Ya bunu geçersiz kılın ya da uygun şekilde ele alın.
Kolaylık işlevleri eklemeyi düşünün
Kodlama ve kod çözme için blokların işlenmesi ad alanı içindeki fonksiyonlara dönüştürülebilir. Bu, yukarıda belirtildiği gibi döngülerin yeniden yapılandırılmasını biraz daha kolay ve daha temiz hale getirecek ve veri yapılarının işlenmesini temel akış I / O'dan izole edecektir. Bu, bir trie'ye dönüştüğünüzde işleri biraz daha kolaylaştırabilir. İşte döngüyü yeniden yazmam:
while (is.read(buffer, ENCODER_BUFFER_SIZE)) {
encode_buffer(buffer, ENCODER_BUFFER_SIZE);
}
encode_buffer(buffer, is.gcount());