Wie implementiert man Datenkomprimierungs- und Dekomprimierungsalgorithmen in C++?

Wie implementiert man Datenkomprimierungs- und Dekomprimierungsalgorithmen in C++?

Zusammenfassung: Datenkomprimierung und -dekomprimierung ist eine der wichtigsten Technologien im Computerbereich. In diesem Artikel wird die Verwendung von C++ zum Implementieren von Datenkomprimierungs- und Dekomprimierungsalgorithmen vorgestellt und Codebeispiele als Referenz für die Leser bereitgestellt.

1. Datenkomprimierungsalgorithmus

Der Datenkomprimierungsalgorithmus kann eine große Datenmenge kodieren, um die Belegung von Speicherplatz und Übertragungsbandbreite zu reduzieren. In C++ können wir die Huffman-Codierung und den LZ77-Algorithmus verwenden, um eine Datenkomprimierung zu erreichen.

1.1 Huffman-Codierung

Huffman-Codierung ist ein frequenzbasierter Datenkomprimierungsalgorithmus. Es weist jedem Zeichen basierend auf der Häufigkeit des Datenvorkommens einen kürzeren Code zu, um den Zweck der Datenkomprimierung zu erreichen.

Der Beispielcode lautet wie folgt:

#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-Algorithmus

Der LZ77-Algorithmus ist ein wörterbuchbasierter Datenkomprimierungsalgorithmus. Es ersetzt wiederkehrende Datenfragmente durch Zeiger auf alte Daten, um den Speicherplatz der Daten zu reduzieren.

Der Beispielcode lautet wie folgt:

#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. Datendekomprimierungsalgorithmus

Der Datendekomprimierungsalgorithmus wird zum Wiederherstellen komprimierter Daten verwendet. In C++ können wir den entsprechenden Dekomprimierungsalgorithmus verwenden, um die Daten wiederherzustellen.

2.1 Huffman-Dekomprimierung

Der Beispielcode lautet wie folgt:

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

// 解压缩数据
string decompressData(string compressedData, unordered_map<string, char>& codeTable) {
    string decompressedData;
    string code;

    for (char ch : compressedData) {
        code += ch;

        if (codeTable.count(code) > 0) {
            decompressedData += codeTable[code];
            code = "";
        }
    }

    return decompressedData;
}

int main() {
    string compressedData = "010101001111011001";
    unordered_map<string, char> codeTable = { {"0", 'a'}, {"10", 'b'}, {"110", 'c'}, {"1110", 'd'}, {"1111", 'e'} };
    string decompressedData = decompressData(compressedData, codeTable);

    cout << "Decompressed Data: " << decompressedData << endl;

    return 0;
}

2.2 LZ77-Dekomprimierung

Der Beispielcode lautet wie folgt:

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

// 解压缩数据
string decompressData(string compressedData) {
    string decompressedData;
    int i = 0;

    while (i < compressedData.length()) {
        if (compressedData[i] == '(') {
            int j = i + 1;

            while (compressedData[j] != ',') {
                j++;
            }

            int offset = stoi(compressedData.substr(i + 1, j - i - 1));
            int k = j + 1;

            while (compressedData[k] != ')') {
                k++;
            }

            int len = stoi(compressedData.substr(j + 1, k - j - 1));

            for (int l = 0; l < len; l++) {
                decompressedData += decompressedData[decompressedData.length() - offset];
            }

            i = k + 1;
        } else {
            decompressedData += compressedData[i];
            i++;
        }
    }

    return decompressedData;
}

int main() {
    string compressedData = "a(1,1)ab(3,3)b(9,2)";
    string decompressedData = decompressData(compressedData);

    cout << "Decompressed Data: " << decompressedData << endl;

    return 0;
}

Fazit:

In diesem Artikel wird erläutert, wie Sie mit C++ Datenkomprimierungs- und Dekomprimierungsalgorithmen implementieren . Mit der Huffman-Codierung und dem LZ77-Algorithmus sind wir in der Lage, Daten effizient zu komprimieren und zu dekomprimieren. Leser können je nach Bedarf den für sie passenden Algorithmus auswählen und ihn anhand des Beispielcodes üben und optimieren.

Das obige ist der detaillierte Inhalt vonWie implementiert man Datenkomprimierungs- und Dekomprimierungsalgorithmen in C++?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!