C ++의 LZ77 압축기 및 압축 해제 기
연결된 목록을 사용하는 LZ77 알고리즘 구현을 작성했습니다 (일치하는 부분 문자열을 더 빨리 찾는 데 도움이 됨). 내 코드의 품질에 대한 피드백과 내 프로그램의 실수 및 모호한 부분에 대한 정보 (있는 경우)를 받고 싶습니다.
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
unsigned int max_buf_length=0;
unsigned int max_dict_length=0;
unsigned int cur_dict_length=0;
unsigned int cur_buf_length=0;
struct link {
unsigned short length;
unsigned short offset;
unsigned char next;
};
struct Node
{
Node* prev;
unsigned int index;
};
class LinkedList
{
public: Node* lastNode;
LinkedList()
{
lastNode=nullptr;
}
~LinkedList()
{
Node* temp;
while(lastNode!=nullptr)
{
temp=lastNode;
lastNode = lastNode->prev;
delete temp;
}
}
void PushBack(unsigned int val)
{
Node* myNode = new Node;
myNode->index=val;
myNode->prev=lastNode;
lastNode=myNode;
}
};
unsigned int readFile(unsigned char* &raw, fstream &inp)
{
inp.seekg(0, ios::beg);
unsigned int file_start = inp.tellg();
inp.seekg(0, ios::end);
unsigned int file_end = inp.tellg();
unsigned int file_size = file_end - file_start;
inp.seekg(0, ios::beg);
raw = new unsigned char[file_size];
inp.read((char*)raw, file_size);
return file_size;
}
void FindLongestMatch(unsigned char* s, unsigned int buf_start, unsigned short &len, unsigned short &off, LinkedList dict[])
{
Node* current = dict[s[buf_start]].lastNode;
unsigned int max_offset = buf_start - cur_dict_length;
unsigned int j = 0;
unsigned int k = 0;
if(current!=nullptr && (current->index)>=max_offset) { len=1; off=buf_start-(current->index); }
while(current!=nullptr && (current->index)>=max_offset)
{
j=1;
k=1;
while(k<cur_buf_length && s[(current->index)+j]==s[buf_start+k])
{
if((current->index)+j==buf_start-1) { j=0; }
else j++;
k++;
}
if(k>len)
{
len = k;
off = buf_start-(current->index);
if(len==cur_buf_length) break;
}
else
{
current=current->prev;
}
}
}
int UpdateDictionary(unsigned char* s, unsigned int shift_start, unsigned short Length, LinkedList dict[])
{
for(unsigned int i=shift_start; i<(shift_start+Length+1); i++)
{
dict[s[i]].PushBack(i);
}
return Length;
}
void compactAndWriteLink(link inp, vector<unsigned char> &out)
{
if(inp.length!=0)
{
out.push_back((unsigned char)((inp.length << 4) | (inp.offset >> 8)));
out.push_back((unsigned char)(inp.offset));
}
else
{
out.push_back((unsigned char)((inp.length << 4)));
}
out.push_back(inp.next);
}
void compressData(unsigned int file_size, unsigned char* data, fstream &file_out)
{
LinkedList dict[256];
link myLink;
vector<unsigned char> lz77_coded;
lz77_coded.reserve(2*file_size);
bool hasOddSymbol=false;
unsigned int target_size = 0;
file_out.seekp(0, ios_base::beg);
cur_dict_length = 0;
cur_buf_length = max_buf_length;
for(unsigned int i=0; i<file_size; i++)
{
if((i+max_buf_length)>=file_size)
{
cur_buf_length = file_size-i;
}
myLink.length=0;myLink.offset=0;
FindLongestMatch(data,i,myLink.length,myLink.offset, dict);
i=i+UpdateDictionary(data, i, myLink.length, dict);
if(i<file_size) {
myLink.next=data[i]; }
else { myLink.next='_'; hasOddSymbol=true; }
compactAndWriteLink(myLink, lz77_coded);
if(cur_dict_length<max_dict_length) {
while((cur_dict_length < max_dict_length) && cur_dict_length < (i+1)) cur_dict_length++;
}
}
if(hasOddSymbol==true) { lz77_coded.push_back((unsigned char)0x1); }
else lz77_coded.push_back((unsigned char)0x0);
target_size=lz77_coded.size();
file_out.write((char*)lz77_coded.data(), target_size);
lz77_coded.clear();
printf("Output file size: %d bytes\n", target_size);
printf("Compression ratio: %.3Lf:1\n", ((double)file_size/(double)target_size));
}
void uncompressData(unsigned int file_size, unsigned char* data, fstream &file_out)
{
if(file_size==0) { printf("Error! Input file is empty\n"); return; }
link myLink;
vector<unsigned char> lz77_decoded;
lz77_decoded.reserve(4*file_size);
unsigned int target_size = 0;
unsigned int i=0;
int k=0;
file_out.seekg(0, ios::beg);
while(i<(file_size-1))
{
if(i!=0) { lz77_decoded.push_back(myLink.next); }
myLink.length = (unsigned short)(data[i] >> 4);
if(myLink.length!=0)
{
myLink.offset = (unsigned short)(data[i] & 0xF);
myLink.offset = myLink.offset << 8;
myLink.offset = myLink.offset | (unsigned short)data[i+1];
myLink.next = (unsigned char)data[i+2];
if(myLink.offset>lz77_decoded.size()) {
printf("Error! Offset is out of range!");
lz77_decoded.clear();
return;
}
if(myLink.length>myLink.offset)
{
k = myLink.length;
while(k>0)
{
if(k>=myLink.offset)
{
lz77_decoded.insert(lz77_decoded.end(), lz77_decoded.end()-myLink.offset, lz77_decoded.end());
k=k-myLink.offset;
}
else
{
lz77_decoded.insert(lz77_decoded.end(), lz77_decoded.end()-myLink.offset, lz77_decoded.end()-myLink.offset+k);
k=0;
}
}
}
else lz77_decoded.insert(lz77_decoded.end(), lz77_decoded.end()-myLink.offset, lz77_decoded.end()-myLink.offset+myLink.length);
i++;
}
else {
myLink.offset = 0;
myLink.next = (unsigned char)data[i+1];
}
i=i+2;
}
unsigned char hasOddSymbol = data[file_size-1];
if(hasOddSymbol==0x0 && file_size>1) { lz77_decoded.push_back(myLink.next); }
target_size = lz77_decoded.size();
file_out.write((char*)lz77_decoded.data(), target_size);
lz77_decoded.clear();
printf("Output file size: %d bytes\n", target_size);
printf("Unpacking finished!");
}
int main(int argc, char* argv[])
{
max_buf_length=15; //16-1;
max_dict_length=4095; //4096-1
string filename_in ="";
string filename_out="";
fstream file_in;
fstream file_out;
unsigned int raw_size = 0;
unsigned char* raw = nullptr;
int mode = 0;
printf("Simple LZ77 compression/decompression program\n");
printf("Coded by MVoloshin, TSU, 2020\n");
if(argc==4) {
if(strcmp(argv[1], "-u")==0) mode = 0;
else if(strcmp(argv[1], "-c")==0) mode = 1;
else { printf("Unknown parameter, use -c or -u\n"); return 0; }
filename_in=std::string(argv[2]);
filename_out=std::string(argv[3]);
}
else
{
printf("Usage: [-c | -u] [input_file] [output_file]\n");
return 0;
}
file_in.open(filename_in, ios::in | ios::binary);
file_in.unsetf(ios_base::skipws);
file_out.open(filename_out, ios::out);
file_out.close();
file_out.open(filename_out, ios::in | ios::out | ios::binary);
file_out.unsetf(ios_base::skipws);
if(file_in && file_out) {
raw_size=readFile(raw, file_in);
printf("Input file size: %d bytes\n", raw_size);
}
else
{
if(!file_in) printf("Error! Couldn't open input file!\n");
if(!file_out) printf("Error! Couldn't open output file!\n");
mode = -1;
}
file_in.close();
if(mode==0)
{
uncompressData(raw_size, raw, file_out);
}
else if(mode==1)
{
compressData(raw_size, raw, file_out);
}
if(raw!=nullptr) delete[] raw;
file_out.close();
return 0;
}
답변
코드 리뷰에 오신 것을 환영합니다! 나는 당신의 코드에 대한 여러 발언을 가지고 있으며 아래 각각에 대해 작은 장을 만들려고 노력합니다. 제 인상은 이미 C 프로그래밍 경험이 있고 이제 C ++로 이동하려고한다는 것입니다. 대부분의 C 코드는 C ++ 컴파일러로 컴파일 할 수 있지만 언어는 다소 다르며 C에 관용적 인 모든 것은 C ++에서 매우 다를 수 있습니다. ;-) 즉, 질문이있는 경우 여기에 제 발언이 있습니다. 질문 해 주시면 자세히 설명하겠습니다.
using namespace std;
이렇게하지 마십시오. 이것은 매우 나쁜 습관으로 간주되며 실제로 지금까지 본 적이있는 전문 C ++ 개발자가 이것을 작성하지 않습니다. 이렇게하면 std
네임 스페이스의 모든 식별자가 범위에 추가 되고 단순히 해당 이름을 사용하지 못하게됩니다. 또한 유형의 정규화 된 이름을 사용해야합니다. std::fstream
대신 fstream
.
변수를 참조 또는 포인터로 정의하는 경우 변수의 식별자가 아닌 유형에 별표 또는 앰퍼샌드를 붙입니다. 그래서 글을 쓰는 대신
, unsigned short &len,
쓰다
, unsigned short& len,
이것은 식별자 옆에 별표가 쓰여진 일반 C와 다른 점입니다.
C ++에서는 stdoutstd::cout
에 쓰는 데 사용 합니다 . 또한, 오류에 인쇄해야 표준 에러 이다 :std::cerr
std::cout << "Output file size: " << target_size << " bytes\n";
if(file_size==0) {
std::cerr << "Error! Input file is empty\n");
return;
}
함수에 구조를 전달할 때 참조로 전달하십시오. 이렇게하면 구조의 내용을 복사하지 못하도록 C ++를 절약 할 수 있습니다. 구조의 내용을 수정하지 않으면 const
참조로 전달하십시오 .
int UpdateDictionary(unsigned char* s, unsigned int shift_start, unsigned short Length, std::list<unsigned>& dict);
void compactAndWriteLink(const link& inp, vector<unsigned char> &out);
자신의 연결 목록을 작성하고 있지만 std::list
대신 사용 하는 것이 좋습니다 . C ++ 표준 라이브러리는 여러 사용 사례에 대해 많은 컨테이너를 제공하며 더 읽기 쉬운 코드를 생성하는 동시에 그 중 하나를 사용하는 것이 항상 더 쉽습니다. 연결 목록 작성에 관심이 있다면 LZZ 항목에주의가 산만 해지지 않도록 내 연결 목록 프로젝트에서이 작업을 수행하는 것이 좋습니다 .-)
조금 더 나아가 사전 클래스 를 만드는 것이 좋습니다 .
class dictionary
{
public:
unsigned short update(unsigned char* s, unsigned int shift_start, unsigned short length);
void longest_match(unsigned char* s, unsigned int buf_start, unsigned short& len, unsigned short& off);
private:
std::list<unsigned int> dict[256]; // or even better, use std::array<std::list<unsigned int>, 256>
};
을 포함 할 필요가 없습니다 <cstring>
.
힌트 : new
. 거의 항상 더 나은 방법이 있습니다. 연결된 목록의 경우 std::list
에서 반환 된 버퍼의 readFile
경우 벡터를 함수에 전달하고이를 사용하여 버퍼를 저장할 수 있습니다.
unsigned int readFile(std::vector<char>& buffer, std::fstream& inp)
{
inp.seekg(0, ios::beg);
unsigned int file_start = inp.tellg();
inp.seekg(0, ios::end);
unsigned int file_end = inp.tellg();
unsigned int file_size = file_end - file_start;
inp.seekg(0, ios::beg);
buffer.reserve(file_size);
inp.read(&buffer[0], file_size);
return file_size;
}
참고 : 파일을 읽는 더 좋고 더 간결한 방법이 있습니다. https://stackoverflow.com/questions/2602013/read-whole-ascii-file-into-c-stdstring
전달 unsigned char* data
하고 unsigned int filesize
사용하는 대신 std::vector<unsigned char>
참조로 전달하십시오. 포인터와 크기를 고수하려면 포인터를 첫 번째 매개 변수로 만드십시오.
에서 compressData
와 uncompressData
당신이 필요하지 않은 vector
데이터를 버퍼링 할 수 있습니다. 추가 할 뿐이므로 스트림에 간단히 쓸 수 있습니다. 또한 일반 스트림을 사용하는 것이 좋습니다. 이렇게하면 파일이나 버퍼에 쓸 것인지 여부를 외부에서 제어하는 것이 더 쉽습니다.
g++ -Wall lzz.cc -o lzz
(gcc 8.3.0)으로 코드를 컴파일하면 다음 경고가 표시됩니다.
lzz.cc: In function ‘void compressData(unsigned int, unsigned char*, std::fstream&)’:
lzz.cc:154:11: warning: format ‘%Lf’ expects argument of type ‘long double’, but argument 2 has type ‘double’ [-Wformat=]
printf("Compression ratio: %.3Lf:1\n", ((double)file_size/(double)target_size));
이것은 나에게 새로운 컴파일러를 사용하는 것일 수 있지만 어쨌든 항상 컴파일하여 -Wall
경고가 있는지 확인하고 수정하십시오.