Bagaimana untuk melaksanakan algoritma pemampatan dan penyahmampatan data dalam C++?

Bagaimana untuk melaksanakan algoritma pemampatan dan penyahmampatan data dalam C++?

Abstrak: Pemampatan dan penyahmampatan data adalah salah satu teknologi terpenting dalam bidang komputer. Artikel ini akan memperkenalkan cara menggunakan C++ untuk melaksanakan algoritma pemampatan dan penyahmampatan data serta menyediakan contoh kod untuk rujukan pembaca.

1. Algoritma pemampatan data

Algoritma pemampatan data boleh mengekod sejumlah besar data untuk mengurangkan penggunaan ruang storan dan jalur lebar penghantaran. Dalam C++, kita boleh menggunakan pengekodan Huffman dan algoritma LZ77 untuk mencapai pemampatan data.

1.1 Pengekodan Huffman

Pengekodan Huffman ialah algoritma pemampatan data berasaskan frekuensi. Ia memberikan kod yang lebih pendek kepada setiap aksara berdasarkan kekerapan kejadian data untuk mencapai tujuan memampatkan data.

Kod sampel adalah seperti berikut:

#include<iostream>
#include<queue>
#include<string>
#include<unordered_map>
using namespace std;

// Huffman树的节点
struct Node {
    char ch;
    int freq;
    Node* left;
    Node* right;
};

// 用于比较树节点的优先队列
class Compare {
public:
    bool operator() (Node* a, Node* b) {
        return a->freq > b->freq;
    }
};

// 生成Huffman树
Node* generateHuffmanTree(string text) {
    // 统计每个字符出现的频率
    unordered_map<char, int> freqTable;
    for (char ch : text) {
        freqTable[ch]++;
    }

    // 将频率和字符转换为Huffman树节点
    priority_queue<Node*, vector<Node*>, Compare> pq;
    for (auto it = freqTable.begin(); it != freqTable.end(); it++) {
        Node* node = new Node();
        node->ch = it->first;
        node->freq = it->second;
        node->left = nullptr;
        node->right = nullptr;
        pq.push(node);
    }

    // 构建Huffman树
    while (pq.size() > 1) {
        Node* left = pq.top();
        pq.pop();
        Node* right = pq.top();
        pq.pop();
        Node* parent = new Node();
        parent->ch = '';
        parent->freq = left->freq + right->freq;
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }

    return pq.top();
}

// 生成Huffman编码表
void generateHuffmanCodeTable(Node* root, string code, unordered_map<char, string>& codeTable) {
    if (root == nullptr) {
        return;
    }

    if (root->ch != '') {
        codeTable[root->ch] = code;
    }

    generateHuffmanCodeTable(root->left, code + "0", codeTable);
    generateHuffmanCodeTable(root->right, code + "1", codeTable);
}

// 压缩数据
string compressData(string text, unordered_map<char, string>& codeTable) {
    string compressedData;

    for (char ch : text) {
        compressedData += codeTable[ch];
    }

    return compressedData;
}


int main() {
    string text = "Hello, World!";
    Node* root = generateHuffmanTree(text);
    unordered_map<char, string> codeTable;
    generateHuffmanCodeTable(root, "", codeTable);
    string compressedData = compressData(text, codeTable);

    cout << "Compressed Data: " << compressedData << endl;

    return 0;
}

1.2 LZ77 algoritma

LZ77 algoritma ialah algoritma pemampatan data berasaskan kamus. Ia menggantikan serpihan data berulang dengan penunjuk kepada data lama untuk mengurangkan ruang penyimpanan data.

Kod sampel adalah seperti berikut:

#include<iostream>
#include<string>
#include<vector>
using namespace std;

// 压缩数据
string compressData(string text) {
    string compressedData;
    int i = 0;

    while (i < text.length()) {
        int len = 0;
        int offset = 0;

        for (int j = 0; j < i; j++) {
            int k = 0;
            while (i + k < text.length() && text[j + k] == text[i + k]) {
                k++;
            }

            if (k > len) {
                len = k;
                offset = i - j;
            }
        }

        if (len > 0) {
            compressedData += "(" + to_string(offset) + "," + to_string(len) + ")";
            i += len;
        } else {
            compressedData += text[i];
            i++;
        }
    }

    return compressedData;
}


int main() {
    string text = "ababaabababbbb";
    string compressedData = compressData(text);

    cout << "Compressed Data: " << compressedData << endl;

    return 0;
}

2. Algoritma penyahmampatan data

Algoritma penyahmampatan data digunakan untuk memulihkan data yang dimampatkan. Dalam C++, kita boleh menggunakan algoritma penyahmampatan yang sepadan untuk memulihkan data. . . Dengan pengekodan Huffman dan algoritma LZ77, kami dapat memampatkan dan menyahmampat data dengan cekap. Pembaca boleh memilih algoritma yang sesuai dengan mereka mengikut keperluan mereka, dan mengamalkan serta mengoptimumkannya berdasarkan kod sampel.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan algoritma pemampatan dan penyahmampatan data dalam C++?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!