How to implement data compression and decompression algorithms in C++?

How to implement data compression and decompression algorithms in C?

Abstract: Data compression and decompression is one of the most important technologies in the computer field. This article will introduce how to use C to implement data compression and decompression algorithms, and provide code examples for readers' reference.

1. Data compression algorithm

The data compression algorithm can encode a large amount of data to reduce the occupation of storage space and transmission bandwidth. In C, we can use Huffman coding and LZ77 algorithm to achieve data compression.

1.1 Huffman coding

Huffman coding is a frequency-based data compression algorithm. It assigns a shorter code to each character based on the frequency of data occurrence to achieve the purpose of compressing data.

The sample code is as follows:

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

The LZ77 algorithm is a dictionary-based data compression algorithm. It replaces recurring data fragments with pointers to old data to reduce the storage space of the data.

The sample code is as follows:

#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. Data decompression algorithm

The data decompression algorithm is used to restore compressed data. In C, we can use the corresponding decompression algorithm to restore the data.

2.1 Huffman decompression

The sample code is as follows:

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

The sample code is as follows:

#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;
}

Conclusion:

This article introduces how to use C to implement data compression and decompression algorithms. With Huffman coding and LZ77 algorithm, we are able to compress and decompress data efficiently. Readers can choose the algorithm that suits them according to their needs, and practice and optimize based on the sample code.

The above is the detailed content of How to implement data compression and decompression algorithms in C++?. For more information, please follow other related articles on the PHP Chinese website!