Kompresor dan dekompresor LZ77 di C ++
Saya telah menulis implementasi algoritma LZ77 yang berfungsi yang menggunakan daftar tertaut (mereka membantu mencari substring yang cocok lebih cepat). Saya ingin mendapatkan umpan balik tentang kualitas kode saya dan juga informasi tentang kesalahan dan tempat meragukan dalam program saya (jika saya punya).
#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;
}
Jawaban
selamat datang di review kode! Saya memiliki banyak komentar untuk kode Anda dan saya mencoba membuat bab-bab kecil untuk masing-masing di bawah ini. Kesan saya adalah, Anda sudah memiliki pengalaman pemrograman di C dan sekarang Anda mencoba pindah ke C ++. Sementara sebagian besar kode C dapat dikompilasi oleh kompiler C ++, bahasanya agak berbeda dan segala sesuatu yang idiomatik ke C sangat mungkin berbeda di C ++ ;-) Meskipun demikian, berikut adalah komentar saya, jika Anda memiliki pertanyaan tentang apa pun, tolong tanyakan dan saya akan menjelaskan:
using namespace std;
Jangan lakukan ini, ini dianggap kebiasaan yang sangat buruk dan faktanya, tidak ada pengembang profesional C ++ yang pernah saya lihat menulis ini. Ini akan menambahkan semua pengenal dari stdnamespace ke lingkup Anda dan akan mencegah Anda dari hanya menggunakan nama-nama itu sebaliknya. Anda juga harus menggunakan nama lengkap yang memenuhi syarat dari tipe tersebut, mis. std::fstreambukannya fstream.
Jika Anda mendefinisikan variabel untuk menjadi referensi atau penunjuk, tempelkan tanda bintang atau ampersand ke jenisnya, bukan pengenal variabel. Jadi, bukannya menulis
, unsigned short &len,
menulis
, unsigned short& len,
Ini adalah perbedaan dengan C biasa, di mana tanda bintang ditulis di sebelah pengenal.
Di C ++, gunakan std::coutuntuk menulis ke stdout . Juga, kesalahan harus dicetak ke stderr yaitu std::cerr:
std::cout << "Output file size: " << target_size << " bytes\n";
if(file_size==0) {
std::cerr << "Error! Input file is empty\n");
return;
}
Saat meneruskan struktur ke suatu fungsi, teruskan dengan referensi. Dengan cara itu Anda menghemat C ++ dari menyalin konten struktur. Jika Anda tidak mengubah konten struktur, teruskan dengan constreferensi:
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);
Anda sedang menulis daftar tertaut Anda sendiri, tetapi saya merekomendasikan untuk menggunakan std::listsebagai gantinya. Pustaka standar C ++ menawarkan banyak wadah untuk beberapa kasus penggunaan dan selalu lebih mudah untuk menggunakan salah satunya sambil juga menghasilkan kode yang lebih mudah dibaca. Jika Anda tertarik untuk menulis daftar tertaut, saya sarankan melakukan ini dalam proyek daftar tertaut saya sendiri sehingga Anda tidak terganggu dengan hal-hal LZZ itu ;-)
Saya bahkan akan melangkah lebih jauh dan menyarankan Anda membuat kelas kamus :
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>
};
Anda tidak perlu memasukkan <cstring>.
Sebagai petunjuk: Anda tidak boleh menggunakan new. Hampir selalu ada cara yang lebih baik. Untuk daftar tertaut Anda, saya sudah mengarahkan Anda ke std::list, untuk buffer yang dikembalikan dari readFile, Anda bisa meneruskan vektor ke fungsi dan menggunakannya untuk menyimpan buffer:
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;
}
Catatan: ada cara yang lebih baik dan lebih ringkas untuk membaca file: https://stackoverflow.com/questions/2602013/read-whole-ascii-file-into-c-stdstring
Alih-alih membagikan unsigned char* datadan unsigned int filesizemenggunakan std::vector<unsigned char>dan meneruskannya sebagai referensi. Jika Anda ingin tetap menggunakan pointer dan ukuran, jadikan pointer sebagai parameter pertama.
Masuk compressDatadan uncompressDataAnda tidak perlu vectorbuffer data. Karena Anda hanya menambahkannya, Anda cukup menulis ke aliran. Saya juga lebih suka menggunakan aliran umum, dengan cara itu lebih mudah untuk mengontrol dari luar apakah Anda ingin menulis ke file atau buffer.
Jika saya mengkompilasi kode Anda dengan g++ -Wall lzz.cc -o lzz(gcc 8.3.0) saya menerima peringatan berikut:
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));
Ini mungkin bagi saya menggunakan kompiler yang lebih baru, tetapi bagaimanapun, selalu coba untuk mengkompilasi dengan -Walluntuk melihat apakah ada peringatan dan memperbaikinya.