LZW संपीड़न लाइब्रेरी

Question

मैंने एक पुस्तकालय लिखा था जो एलजेडडब्ल्यू संपीड़न और विघटन को लागू करता है। इस परियोजना का एक लक्ष्य मुझे आधुनिक C ++ विकास प्रथाओं से परिचित कराने में मदद करना था (मैं मुख्य रूप से एक जावा पृष्ठभूमि से आता हूं और सी अनुभव का एक smattering है)।

मैं डेटा को संपीड़ित करने के लिए इस लाइब्रेरी का उपयोग करना चाहता हूं और प्राप्तकर्ता द्वारा विघटित होने के लिए इसे टीसीपी सॉकेट्स पर स्ट्रीम करना है, बिना प्रेषक या प्राप्तकर्ता की मशीन (शौक / गैर-उत्पादन उद्देश्यों के लिए) पर पूर्ण डेटा के एक संपीड़ित संस्करण को संग्रहीत किए बिना।

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 *।

Answer 1

यहां कुछ चीजें दी गई हैं, जो आपके कोड को बेहतर बनाने में आपकी मदद कर सकती हैं।

एक संपीड़ित फ़ाइल छोटा नहीं होना चाहिए?

जब मुझे पता चला कि मेरे आश्चर्य की बात यह है कि एक 2037-बाइट फ़ाइल (lzw.cpp स्रोत कोड) 3524 बाइट्स बन गई जब "संकुचित!" मूल LZW एल्गोरिथ्म ने 8-बिट मानों को 12-बिट कोड में एन्कोड किया। यह 32-बिट कोड के रूप में 8-बिट मान एन्कोडिंग प्रतीत होता है, जो इस तरह की छोटी फ़ाइलों के लिए बहुत अधिक संपीड़न की पेशकश करने की संभावना नहीं है। हालाँकि, मैंने इसे ब्रैम स्टोकर की ड्रैकुला के सादे पाठ संस्करण पर आज़माया और, जैसा कि अपेक्षित था, परिणामस्वरूप फ़ाइल मूल के आकार का लगभग 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 आरंभीकृत किया जाएगा और क्योंकि सदस्यों को हमेशा घोषणा के क्रम में आरंभीकृत किया जाता है और इस वर्ग में पहले घोषित किया जाता है । एक अन्य प्रोग्रामर को गुमराह करने से बचने के लिए, आप बस छोड़ सकते हैं क्योंकि यह पहले से ही घोषणा द्वारा आरंभ किया गया है: isoscurrent_codeiscurrent_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());