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
lzw_encoder의 unordered_map을 향후 편집에서 사전 트라이로 대체 할 계획입니다.
내 코드가 io 스트림을 사용하는 합리적인 방법을 보여줍니까?
읽기 및 쓰기 사용이 최신 C ++ 느낌이 들지 않는다고 생각하고 바이너리 io를 지원하는 표준 라이브러리 도구를 모르고 있는지 궁금합니다. 특히 while(true)입력 스트림과 관련된 조건 대신 사용하는 것이 마음에 들지 않습니다 . 또한 reinterpret_cast숫자 / 이진 데이터 포인터를 .NET 에 캐스트 하는 데 사용하지 않고 이진 io를 수행하는 방법이 있는지 궁금합니다 char *.
답변
다음은 코드를 개선하는 데 도움이 될 수있는 몇 가지 사항입니다.
압축 파일이 더 작아야하지 않나요?
2037 바이트 파일 (lzw.cpp 소스 코드 자체)이 "압축"되었을 때 3524 바이트가된다는 사실을 발견했을 때 놀랍게도 상상해보십시오. 원래 LZW 알고리즘은 8 비트 값을 12 비트 코드로 인코딩했습니다. 이것은 8 비트 값을 32 비트 코드로 인코딩하는 것으로 보이며 이와 같은 짧은 파일에 대해 많은 압축을 제공하지 않을 것입니다. 그러나 Bram Stoker의 Dracula 의 일반 텍스트 버전에서 시도해 보았고 예상대로 결과 파일은 원본 크기의 약 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;
적절한 경우 표준 알고리즘 사용
코드북 초기화는 다음을 사용합니다.
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
}
스트림 사용 이해
호출자가 읽기시 파일 끝과 같은 오류 발생시 예외 를 throw하도록 하나 또는 두 스트림을 설정 했을 수 있습니다. 이것을 무시하거나 적절하게 처리하십시오.
편의 기능 추가 고려
인코딩 및 디코딩을위한 블록 처리는 모두 네임 스페이스 내의 함수로 만들 수 있습니다. 이것은 위에서 언급 한 루프의 재구성을 조금 더 쉽고 깨끗하게 만들고 기본 스트림 I / O에서 데이터 구조의 처리를 분리합니다. 트라이로 변환 할 때 작업이 좀 더 쉬워 질 수 있습니다. 다음은 루프를 다시 작성한 것입니다.
while (is.read(buffer, ENCODER_BUFFER_SIZE)) {
encode_buffer(buffer, ENCODER_BUFFER_SIZE);
}
encode_buffer(buffer, is.gcount());