Perpustakaan Kompresi LZW

Question

Saya menulis perpustakaan yang mengimplementasikan kompresi dan dekompresi LZW. Tujuan dari proyek ini adalah untuk membantu saya mengenal diri saya dengan praktik pengembangan C ++ modern (saya terutama berasal dari latar belakang Java dan memiliki sedikit pengalaman C).

Saya ingin menggunakan pustaka ini untuk memampatkan data dan mengalirkannya melalui soket TCP untuk didekompresi oleh penerima, semua tanpa menyimpan versi terkompresi dari data lengkap baik pada mesin pengirim atau penerima (untuk tujuan hobi / non-produksi).

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

Saya berencana mengganti unordered_map di lzw_encoder dengan kamus trie di masa edit mendatang.

Apakah kode saya menunjukkan cara yang wajar untuk menggunakan io stream?

Saya merasa bahwa penggunaan baca dan tulis saya tidak memiliki perasaan C ++ modern, dan saya bertanya-tanya apakah saya tidak mengetahui beberapa alat pustaka standar untuk membantu saya dengan biner io. Secara khusus, saya tidak suka yang saya gunakan while(true)alih-alih beberapa kondisi yang terkait dengan aliran input. Juga, saya bertanya-tanya apakah ada cara untuk melakukan io biner tanpa menggunakan reinterpret_castuntuk mentransmisikan pointer data numerik / biner ke char *.

Answer 1

Berikut beberapa hal yang saya lihat yang dapat membantu Anda meningkatkan kode Anda.

Bukankah file terkompresi harus lebih kecil?

Bayangkan betapa terkejutnya saya ketika saya menemukan bahwa file 2037-byte (kode sumber lzw.cpp itu sendiri) menjadi 3524 byte ketika "dikompresi!" Algoritma LZW asli mengkodekan nilai 8-bit menjadi kode 12-bit. Ini tampaknya menyandikan nilai 8-bit sebagai kode 32-bit yang tidak mungkin menawarkan banyak kompresi untuk file pendek seperti ini. Aku, bagaimanapun, mencobanya pada versi teks biasa dari Bram Stoker Dracula dan, seperti yang diharapkan, file yang dihasilkan adalah sekitar 75% dari ukuran aslinya. Karena ini adalah aliran dan Anda tidak memiliki akses ke panjang sumbernya, mungkin tidak banyak yang dapat Anda lakukan, tetapi mungkin hal yang baik untuk memperingatkan calon pengguna.

Pikirkan kembali antarmuka

Untuk menggunakan kompresi, seseorang harus terlebih dahulu membuat objek dan kemudian menggunakannya, mungkin seperti ini:

lzw::lzw_encoder lzw(in, out);
lzw.encode();

Bukankah lebih baik hanya bisa melakukan ini?

lzw::encode(in, out);

Tulis penginisialisasi anggota dalam urutan deklarasi

The lzw_encoderkelas memiliki konstruktor ini

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;
  }
}

Kelihatannya bagus, tapi kenyataannya, current_codeakan diinisialisasi sebelumnya is dan oskarena anggota selalu diinisialisasi dalam urutan deklarasi dan current_codedideklarasikan sebelumnya isdi kelas ini. Untuk menghindari menyesatkan programmer lain, Anda dapat mengabaikannya current_codekarena sudah diinisialisasi oleh deklarasi:

uint32_t current_code = 0;

Gunakan algoritme standar jika sesuai

Menginisialisasi buku kode menggunakan ini:

for (current_code = 0; current_code < 256; ++current_code) {
  codebook[std::string(1, static_cast<char>(current_code))] = current_code;
}

Ini dapat ditingkatkan dengan berbagai cara. Pertama, kita sudah mengetahui seberapa besar codebook tersebut sehingga kita dapat mengurangi jumlah realokasi memori dengan memberi tahu kompiler informasi itu:

codebook.reserve(256);

Selanjutnya, kita dapat menghindari cast dan mendapatkan sedikit efisiensi dengan menggunakan emplace:

for (current_code = 0; current_code < 256; ++current_code) {
    codebook.emplace(std::string(1, current_code), current_code);
}

Saya juga merekomendasikan untuk mengganti di 256sini dengan static constexpr initial_codebook_size.

Waspadai perbedaan endian-an

Kode saat ini berisi baris-baris ini:

auto code_val = codebook[current];
os.write(reinterpret_cast<char *>(&code_val), sizeof(code_val));

Masalahnya adalah bahwa bergantung pada apakah ini mesin big-endian atau little-endian, encodingnya akan berbeda. Jika aliran terkompresi dimaksudkan untuk dikirim ke mesin lain, ini harus konsisten. Pertimbangkan untuk menggunakan sesuatu seperti htonlfungsi POSIX di sini.

Pertimbangkan untuk merestrukturisasi loop

Masalahnya while(true)adalah ia menyembunyikan kondisi keluar loop. Daripada ini:

while (true) {
    is.read(buffer, ENCODER_BUFFER_SIZE);
    auto read_length = is.gcount();
    if (read_length == 0)
      break;
    // etc
}

Pertimbangkan sesuatu seperti ini:

while (is.read(buffer, ENCODER_BUFFER_SIZE)) {
    // handle full block
}
if (is.gcount()) {
    // handle final partial block
}

Pahami penggunaan aliran

Ada kemungkinan bahwa pemanggil telah menyetel satu atau kedua aliran untuk membuat pengecualian jika mengalami kegagalan seperti akhir file saat dibaca. Timpa ini atau tangani dengan tepat.

Pertimbangkan untuk menambahkan fungsi kenyamanan

Penanganan blok untuk encode dan untuk decode keduanya dapat dibuat menjadi fungsi di dalam namespace. Ini akan membuat restrukturisasi loop seperti yang disebutkan di atas sedikit lebih mudah dan lebih bersih dan akan mengisolasi penanganan struktur data dari aliran dasar I / O. Itu mungkin membuat segalanya lebih mudah saat Anda mengonversi ke trie. Inilah penulisan ulang loop saya:

while (is.read(buffer, ENCODER_BUFFER_SIZE)) {
  encode_buffer(buffer, ENCODER_BUFFER_SIZE);
}
encode_buffer(buffer, is.gcount());