LZ77 คอมเพรสเซอร์และตัวคลายการบีบอัดใน C ++

Question

ฉันได้เขียนการใช้อัลกอริทึม 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;
}

Answer 1

ยินดีต้อนรับสู่การตรวจสอบโค้ด! ฉันมีข้อสังเกตหลายประการเกี่ยวกับรหัสของคุณและฉันพยายามสร้างบทเล็ก ๆ น้อย ๆ สำหรับแต่ละบทด้านล่าง ความประทับใจของฉันคือคุณมีประสบการณ์การเขียนโปรแกรมใน C อยู่แล้วและตอนนี้คุณกำลังพยายามย้ายไปที่ C ++ ในขณะที่โค้ด C ส่วนใหญ่สามารถรวบรวมได้โดยคอมไพเลอร์ C ++ แต่ภาษาจะแตกต่างกันบ้างและทุกอย่างที่เป็นสำนวน C นั้นมีความแตกต่างกันมากใน C ++ ;-) ที่กล่าวมานี่คือคำพูดของฉันหากคุณมีคำถามเกี่ยวกับอะไร โปรดถามและฉันจะอธิบายอย่างละเอียด:

---

using namespace std;

อย่าทำเช่นนี้ถือว่าเป็นนิสัยที่ไม่ดีอย่างยิ่งและในความเป็นจริงไม่มีนักพัฒนา C ++ มืออาชีพที่ฉันเคยเห็นเขียนถึงสิ่งนี้ สิ่งนี้จะเพิ่มตัวระบุทั้งหมดจากstdเนมสเปซไปยังขอบเขตของคุณและจะป้องกันไม่ให้คุณใช้ชื่อเหล่านั้นเป็นอย่างอื่น คุณควรใช้ชื่อเต็มของประเภทเช่น แทนstd::fstreamfstream

---

หากคุณกำหนดตัวแปรให้เป็นข้อมูลอ้างอิงหรือตัวชี้ให้ติดเครื่องหมายดอกจันหรือเครื่องหมายและเครื่องหมายกับชนิดไม่ใช่ตัวระบุของตัวแปร ดังนั้นแทนที่จะเขียน

, unsigned short &len,

เขียน

, unsigned short& len,

นี่คือความแตกต่างของ C ธรรมดาโดยที่เครื่องหมายดอกจันเขียนอยู่ถัดจากตัวระบุ

---

ใน C ++, ใช้std::coutในการเขียนไปstdout นอกจากนี้ควรพิมพ์ข้อผิดพลาดไปยังstderrซึ่ง ได้แก่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เพื่อดูว่ามีคำเตือนและแก้ไขหรือไม่

---