LZW Sıkıştırma Kitaplığı

Aug 17 2020

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_castsayısal / ikili veri işaretçileri çevirmek için kullanmadan ikili io yapmanın bir yolu olup olmadığını merak ediyordum char *.

Yanıtlar

2 Edward Aug 18 2020 at 21:35

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_encoderSı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_codebaşlatılır önce is ve osüyeleri her zaman başlatılır çünkü beyanı düzen ve current_codedaha önce bildirilmiş isbu 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 256burayı 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. htonlBurada 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());