C ++의 LZ77 압축기 및 압축 해제 기

Aug 20 2020

연결된 목록을 사용하는 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;
}

답변

1 Cornholio Aug 20 2020 at 14:29

코드 리뷰에 오신 것을 환영합니다! 나는 당신의 코드에 대한 여러 발언을 가지고 있으며 아래 각각에 대해 작은 장을 만들려고 노력합니다. 제 인상은 이미 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>참조로 전달하십시오. 포인터와 크기를 고수하려면 포인터를 첫 번째 매개 변수로 만드십시오.


에서 compressDatauncompressData당신이 필요하지 않은 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경고가 있는지 확인하고 수정하십시오.