C++에서 데이터 압축 및 압축 풀기 알고리즘을 구현하는 방법은 무엇입니까?

C++에서 데이터 압축 및 압축 풀기 알고리즘을 구현하는 방법은 무엇입니까?

요약: 데이터 압축 및 압축 해제는 컴퓨터 분야에서 가장 중요한 기술 중 하나입니다. 이 기사에서는 C++를 사용하여 데이터 압축 및 압축 해제 알고리즘을 구현하는 방법을 소개하고 독자의 참조를 위한 코드 예제를 제공합니다.

1. 데이터 압축 알고리즘

데이터 압축 알고리즘은 대용량 데이터를 인코딩하여 저장 공간 점유와 전송 대역폭을 줄일 수 있습니다. C++에서는 Huffman 코딩과 LZ77 알고리즘을 사용하여 데이터 압축을 달성할 수 있습니다.

1.1 허프만 코딩

허프만 코딩은 주파수 기반 데이터 압축 알고리즘입니다. 데이터 압축 목적을 달성하기 위해 데이터 발생 빈도에 따라 각 문자에 더 짧은 코드를 할당합니다.

샘플 코드는 다음과 같습니다.

#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 알고리즘

LZ77 알고리즘은 사전 기반의 데이터 압축 알고리즘입니다. 반복되는 데이터 조각을 이전 데이터에 대한 포인터로 대체하여 데이터의 저장 공간을 줄입니다.

샘플 코드는 다음과 같습니다.

#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. 데이터 압축 해제 알고리즘

데이터 압축 해제 알고리즘은 압축된 데이터를 복원하는 데 사용됩니다. C++에서는 해당 압축 해제 알고리즘을 사용하여 데이터를 복원할 수 있습니다.

2.1 허프만 압축해제

샘플 코드는 다음과 같습니다.

#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 압축해제

샘플 코드는 다음과 같습니다.

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

결론:

이 글에서는 C++를 사용하여 데이터 압축 및 압축해제 알고리즘을 구현하는 방법을 소개합니다. . 허프만 코딩과 LZ77 알고리즘을 사용하여 데이터를 효율적으로 압축 및 압축 해제할 수 있습니다. 독자는 자신의 필요에 따라 자신에게 맞는 알고리즘을 선택하고, 샘플 코드를 기반으로 실습하고 최적화할 수 있습니다.

위 내용은 C++에서 데이터 압축 및 압축 풀기 알고리즘을 구현하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!