Bagaimana untuk menggunakan C++ untuk pemampatan data dan penyimpanan data yang cekap?

Bagaimana menggunakan C++ untuk pemampatan data dan penyimpanan data yang cekap?

Pengenalan:
Apabila jumlah data meningkat, pemampatan data dan penyimpanan data menjadi semakin penting. Terdapat banyak cara untuk mencapai pemampatan dan penyimpanan data yang cekap dalam C++. Artikel ini akan memperkenalkan beberapa algoritma pemampatan data biasa dan teknologi storan data dalam C++, dan memberikan contoh kod yang sepadan.

1. Algoritma pemampatan data

1.1 Algoritma pemampatan berdasarkan pengekodan Huffman
Pengekodan Huffman ialah algoritma pemampatan data berdasarkan pengekodan panjang berubah-ubah. Ia mencapai pemampatan data dengan memberikan kod yang lebih pendek kepada aksara (atau blok data) dengan kekerapan yang lebih tinggi dan kod yang lebih panjang kepada aksara (atau blok data) dengan frekuensi yang lebih rendah. Berikut ialah contoh kod untuk melaksanakan pengekodan Huffman menggunakan C++:

#include <iostream>
#include <unordered_map>
#include <queue>
#include <string>

struct TreeNode {
    char data;
    int freq;
    TreeNode* left;
    TreeNode* right;
    
    TreeNode(char data, int freq) : data(data), freq(freq), left(nullptr), right(nullptr) {}
};

struct compare {
    bool operator()(TreeNode* a, TreeNode* b) {
        return a->freq > b->freq;
    }
};

void generateCodes(TreeNode* root, std::string code, std::unordered_map<char, std::string>& codes) {
    if (root->left == nullptr && root->right == nullptr) {
        codes[root->data] = code;
        return;
    }
    generateCodes(root->left, code + "0", codes);
    generateCodes(root->right, code + "1", codes);
}

void huffmanCompression(std::string input) {
    std::unordered_map<char, int> freqMap;
    for (char c : input) {
        freqMap[c]++;
    }

    std::priority_queue<TreeNode*, std::vector<TreeNode*>, compare> minHeap;
    for (auto& entry : freqMap) {
        minHeap.push(new TreeNode(entry.first, entry.second));
    }

    while (minHeap.size() > 1) {
        TreeNode* left = minHeap.top();
        minHeap.pop();
        TreeNode* right = minHeap.top();
        minHeap.pop();
        
        TreeNode* parent = new TreeNode('', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        minHeap.push(parent);
    }

    TreeNode* root = minHeap.top();
    std::unordered_map<char, std::string> codes;
    generateCodes(root, "", codes);

    std::string compressed;
    for (char c : input) {
        compressed += codes[c];
    }

    std::cout << "Compressed: " << compressed << std::endl;
    std::cout << "Uncompressed: " << input << std::endl;
    std::cout << "Compression ratio: " << (double)compressed.size() / input.size() << std::endl;

    // 清理内存
    delete root;
}

int main() {
    std::string input = "abracadabra";
    huffmanCompression(input);
    return 0;
}

1.2 Algoritma Lempel-Ziv-Welch (LZW)
Algoritma LZW ialah algoritma pemampatan data tanpa kehilangan yang biasa digunakan dalam format imej GIF. Ia menggunakan kamus untuk menyimpan rentetan sedia ada dan mengurangkan panjang rentetan termampat dengan mengembangkan kamus secara berterusan. Berikut adalah contoh kod untuk melaksanakan algoritma LZW menggunakan C++:

#include <iostream>
#include <unordered_map>
#include <string>

void lzwCompression(std::string input) {
    std::unordered_map<std::string, int> dictionary;
    for (int i = 0; i < 256; i++) {
        dictionary[std::string(1, i)] = i;
    }

    std::string output;
    std::string current;
    for (char c : input) {
        std::string temp = current + c;
        if (dictionary.find(temp) != dictionary.end()) {
            current = temp;
        } else {
            output += std::to_string(dictionary[current]) + " ";
            dictionary[temp] = dictionary.size();
            current = std::string(1, c);
        }
    }

    if (!current.empty()) {
        output += std::to_string(dictionary[current]) + " ";
    }

    std::cout << "Compressed: " << output << std::endl;
    std::cout << "Uncompressed: " << input << std::endl;
    std::cout << "Compression ratio: " << (double)output.size() / input.size() << std::endl;
}

int main() {
    std::string input = "abracadabra";
    lzwCompression(input);
    return 0;
}

2. Teknologi penyimpanan data

2.1 Penyimpanan fail binari
Storan fail binari ialah kaedah menulis data ke fail dalam bentuk binari. Berbanding dengan storan fail teks, storan fail binari boleh menjimatkan ruang storan dan membaca dan menulis dengan lebih pantas. Berikut adalah contoh kod untuk storan fail binari menggunakan C++:

#include <iostream>
#include <fstream>

struct Data {
    int i;
    double d;
    char c;
};

void binaryFileStorage(Data data) {
    std::ofstream outfile("data.bin", std::ios::binary);
    outfile.write(reinterpret_cast<char*>(&data), sizeof(data));
    outfile.close();

    std::ifstream infile("data.bin", std::ios::binary);
    Data readData;
    infile.read(reinterpret_cast<char*>(&readData), sizeof(readData));
    infile.close();

    std::cout << "Original: " << data.i << ", " << data.d << ", " << data.c << std::endl;
    std::cout << "Read from file: " << readData.i << ", " << readData.d << ", " << readData.c << std::endl;
}

int main() {
    Data data {42, 3.14, 'A'};
    binaryFileStorage(data);
    return 0;
}

2.2 Storan Fail Termampat
Storan fail termampat ialah kaedah menulis data ke fail dalam format termampat. Storan fail termampat boleh menjimatkan ruang storan, tetapi kelajuan membaca dan menulis lebih perlahan. Berikut ialah contoh kod untuk penyimpanan fail termampat menggunakan C++:

#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <zlib.h>

void compressFileStorage(std::string input) {
    std::ostringstream compressedStream;
    z_stream defStream;
    defStream.zalloc = Z_NULL;
    defStream.zfree = Z_NULL;
    defStream.opaque = Z_NULL;
    defStream.avail_in = input.size();
    defStream.next_in = (Bytef*)input.c_str();
    defStream.avail_out = input.size() + (input.size() / 100) + 12;
    defStream.next_out = (Bytef*)compressedStream.str().c_str();

    deflateInit(&defStream, Z_DEFAULT_COMPRESSION);
    deflate(&defStream, Z_FINISH);
    deflateEnd(&defStream);

    std::string compressed = compressedStream.str();

    std::ofstream outfile("compressed.txt", std::ios::binary);
    outfile.write(compressed.c_str(), compressed.size());
    outfile.close();

    std::ifstream infile("compressed.txt", std::ios::binary);
    std::ostringstream decompressedStream;
    z_stream infStream;
    infStream.zalloc = Z_NULL;
    infStream.zfree = Z_NULL;
    infStream.opaque = Z_NULL;
    infStream.avail_in = compressed.size();
    infStream.next_in = (Bytef*)compressed.c_str();
    infStream.avail_out = compressed.size() * 10;
    infStream.next_out = (Bytef*)decompressedStream.str().c_str();

    inflateInit(&infStream);
    inflate(&infStream, Z_NO_FLUSH);
    inflateEnd(&infStream);

    std::string decompressed = decompressedStream.str();

    std::cout << "Original: " << input << std::endl;
    std::cout << "Compressed: " << compressed << std::endl;
    std::cout << "Decompressed: " << decompressed << std::endl;
}

int main() {
    std::string input = "abracadabra";
    compressFileStorage(input);
    return 0;
}

Kesimpulan:
Artikel ini memperkenalkan beberapa algoritma pemampatan data biasa dan teknologi storan data dalam C++, dan menyediakan contoh kod yang sepadan. Pemampatan dan penyimpanan data yang cekap boleh dicapai dengan memilih algoritma pemampatan data dan teknologi storan yang sesuai. Dalam aplikasi praktikal, kaedah yang paling sesuai boleh dipilih berdasarkan ciri dan keperluan data.

Atas ialah kandungan terperinci Bagaimana untuk menggunakan C++ untuk pemampatan data dan penyimpanan data yang cekap?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!