How to use C++ for efficient data compression and data storage?

How to use C for efficient data compression and data storage?

Introduction:
As the amount of data increases, data compression and data storage become more and more important. In C, there are many ways to achieve efficient data compression and storage. This article will introduce some common data compression algorithms and data storage techniques in C, and provide corresponding code examples.

1. Data compression algorithm

1.1 Compression algorithm based on Huffman coding
Huffman coding is a data compression algorithm based on variable length coding. It compresses data by assigning shorter codes to characters (or data blocks) with higher frequency and longer codes to characters (or data blocks) with lower frequency. The following is sample code for implementing Huffman coding using 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 Lempel-Ziv-Welch (LZW) algorithm
The LZW algorithm is a lossless data compression algorithm commonly used in the GIF image format. It uses a dictionary to store existing strings and reduces the length of the compressed string by continuously expanding the dictionary. The following is a sample code using C to implement the LZW algorithm:

#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. Data storage technology

2.1 Binary file storage
Binary file storage is a method of writing data to files in binary form Methods. Compared with text file storage, binary file storage can save storage space and read and write faster. The following is sample code for implementing binary file storage using 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 Compressed file storage
Compressed file storage is a method of writing data to a file in a compressed format. Compressed file storage can save storage space, but the reading and writing speed is slower. The following is a sample code for compressed file storage using 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;
}

Conclusion:
This article introduces several common data compression algorithms and data storage technologies in C, and provides corresponding code examples. Efficient data compression and storage can be achieved by selecting appropriate data compression algorithms and storage technologies. In practical applications, the most appropriate method can be selected based on the characteristics and needs of the data.

The above is the detailed content of How to use C++ for efficient data compression and data storage?. For more information, please follow other related articles on the PHP Chinese website!