ไลบรารีการบีบอัด 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
ฉันวางแผนที่จะแทนที่ unordered_map ใน lzw_encoder ด้วยพจนานุกรมสามตัวในการแก้ไขในอนาคต
รหัสของฉันแสดงวิธีที่เหมาะสมในการใช้สตรีม io หรือไม่
ฉันรู้สึกว่าการใช้งานการอ่านและเขียนของฉันไม่ได้มีความรู้สึกถึง C ++ ที่ทันสมัยและฉันสงสัยว่าฉันไม่รู้จักเครื่องมือไลบรารีมาตรฐานบางอย่างที่จะช่วยฉันในการใช้ไบนารี io โดยเฉพาะอย่างยิ่งฉันไม่ชอบที่ฉันใช้while(true)
แทนเงื่อนไขบางอย่างที่เกี่ยวข้องกับสตรีมอินพุต นอกจากนี้ฉันสงสัยว่ามีวิธีทำ io ไบนารีโดยไม่ต้องใช้reinterpret_cast
ตัวชี้ข้อมูลตัวเลข / ไบนารีchar *
หรือไม่
คำตอบ
นี่คือบางสิ่งที่ฉันเห็นซึ่งอาจช่วยคุณปรับปรุงโค้ดของคุณได้
ไฟล์บีบอัดควรมีขนาดเล็กกว่าไม่ใช่หรือ?
ลองนึกภาพความประหลาดใจของฉันเมื่อฉันพบว่าไฟล์ 2037 ไบต์ (ซอร์สโค้ด lzw.cpp เอง) กลายเป็น 3524 ไบต์เมื่อ "บีบอัด!" อัลกอริทึม LZW ดั้งเดิมเข้ารหัสค่า 8 บิตเป็นรหัส 12 บิต ดูเหมือนจะเข้ารหัสค่า 8 บิตเป็นรหัส 32 บิตซึ่งไม่น่าจะมีการบีบอัดมากนักสำหรับไฟล์สั้น ๆ เช่นนี้ ฉันได้ แต่ลองในรูปแบบข้อความธรรมดาของแบของถ่านหินแดรกคิวลาและเป็นไปตามคาดแฟ้มผลเป็นประมาณ 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;
ใช้อัลกอริทึมมาตรฐานตามความเหมาะสม
การเริ่มต้น codebook ใช้สิ่งนี้:
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
.
ระวังความแตกต่างของ endian-ness
ปัจจุบันโค้ดประกอบด้วยบรรทัดเหล่านี้:
auto code_val = codebook[current];
os.write(reinterpret_cast<char *>(&code_val), sizeof(code_val));
มีปัญหาขึ้นอยู่กับว่าเครื่องนี้เป็นเครื่อง big-endian หรือ little-endian การเข้ารหัสจะแตกต่างกัน หากต้องการส่งสตรีมที่บีบอัดไปยังเครื่องอื่นสิ่งนี้จะต้องสอดคล้องกัน ลองใช้บางอย่างเช่น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 สตรีมพื้นฐาน นั่นอาจทำให้ง่ายขึ้นเล็กน้อยเมื่อคุณแปลงเป็น Trie นี่คือการเขียนวนซ้ำของฉัน:
while (is.read(buffer, ENCODER_BUFFER_SIZE)) {
encode_buffer(buffer, ENCODER_BUFFER_SIZE);
}
encode_buffer(buffer, is.gcount());