基于哈夫曼树的数据压缩算法

哈夫曼树是一种经典的数据压缩算法，其原理是根据字符出现的频率构建一棵二叉树，出现频率高的字符在树的顶部，出现频率低的字符在树的底部。然后，通过对字符的编码来进行压缩，出现频率高的字符编码较短，出现频率低的字符编码较长。

具体的实现过程如下：

1. 统计字符出现的频率，并按照频率从小到大排序；
2. 将最小的两个频率合并为一个节点，并将其权值设为这两个节点权值之和；
3. 重复步骤2，直到所有节点都被合并为一棵树；
4. 对树进行遍历，为每个叶子节点分配一个唯一的编码；
5. 使用编码表对原始数据进行编码，得到压缩后的数据。

哈夫曼编码的优点是可以实现无损压缩，即压缩后的数据可以完全还原为原始数据。同时，由于出现频率高的字符编码较短，因此可以实现较高的压缩比。

相关问题

基于哈夫曼树的数据压缩算法java

哈夫曼树是一种常用的数据压缩算法，以下是基于哈夫曼树的数据压缩算法的Java实现。

首先，我们需要定义一个哈夫曼树的节点类，包含字符、权重和左右子节点等属性：

class HuffmanNode {
    char c;
    int weight;
    HuffmanNode left;
    HuffmanNode right;

    public HuffmanNode(char c, int weight) {
        this.c = c;
        this.weight = weight;
    }

    public HuffmanNode(HuffmanNode left, HuffmanNode right) {
        this.weight = left.weight + right.weight;
        this.left = left;
        this.right = right;
    }

    public boolean isLeaf() {
        return left == null && right == null;
    }
}

接下来，我们需要实现构建哈夫曼树的方法。我们可以先统计字符出现的频率，然后根据频率构建哈夫曼树。具体实现如下：

public static HuffmanNode buildHuffmanTree(String text) {
    Map<Character, Integer> freqMap = new HashMap<>();
    for (char c : text.toCharArray()) {
        freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
    }

    PriorityQueue<HuffmanNode> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.weight));
    for (Map.Entry<Character, Integer> entry : freqMap.entrySet()) {
        pq.offer(new HuffmanNode(entry.getKey(), entry.getValue()));
    }

    while (pq.size() > 1) {
        HuffmanNode left = pq.poll();
        HuffmanNode right = pq.poll();
        pq.offer(new HuffmanNode(left, right));
    }

    return pq.poll();
}

接着，我们可以实现编码和解码方法。编码方法将输入的字符串转换为二进制编码，解码方法将二进制编码转换为原字符串。具体实现如下：

public static Map<Character, String> buildEncodingMap(HuffmanNode root) {
    Map<Character, String> map = new HashMap<>();
    buildEncodingMapHelper(root, "", map);
    return map;
}

private static void buildEncodingMapHelper(HuffmanNode node, String code, Map<Character, String> map) {
    if (node.isLeaf()) {
        map.put(node.c, code);
        return;
    }
    buildEncodingMapHelper(node.left, code + "0", map);
    buildEncodingMapHelper(node.right, code + "1", map);
}

public static String encode(String text, HuffmanNode root) {
    Map<Character, String> encodingMap = buildEncodingMap(root);
    StringBuilder sb = new StringBuilder();
    for (char c : text.toCharArray()) {
        sb.append(encodingMap.get(c));
    }
    return sb.toString();
}

public static String decode(String code, HuffmanNode root) {
    StringBuilder sb = new StringBuilder();
    HuffmanNode node = root;
    for (char c : code.toCharArray()) {
        node = c == '0' ? node.left : node.right;
        if (node.isLeaf()) {
            sb.append(node.c);
            node = root;
        }
    }
    return sb.toString();
}

最后，我们可以将上述方法组合在一起，实现完整的数据压缩算法：

public static String compress(String text) {
    HuffmanNode root = buildHuffmanTree(text);
    String code = encode(text, root);
    String header = buildHeader(root);
    return header + code;
}

public static String decompress(String compressedText) {
    String[] parts = compressedText.split(":", 2);
    HuffmanNode root = parseHeader(parts[0]);
    String code = parts[1];
    return decode(code, root);
}

private static String buildHeader(HuffmanNode root) {
    StringBuilder sb = new StringBuilder();
    buildHeaderHelper(root, sb);
    sb.append(":");
    return sb.toString();
}

private static void buildHeaderHelper(HuffmanNode node, StringBuilder sb) {
    if (node.isLeaf()) {
        sb.append(node.c);
        return;
    }
    sb.append("0");
    buildHeaderHelper(node.left, sb);
    sb.append("1");
    buildHeaderHelper(node.right, sb);
}

private static HuffmanNode parseHeader(String header) {
    Stack<HuffmanNode> stack = new Stack<>();
    HuffmanNode root = null;
    for (char c : header.toCharArray()) {
        if (c == '0') {
            HuffmanNode node = new HuffmanNode('\0', 0);
            if (!stack.isEmpty()) {
                HuffmanNode parent = stack.peek();
                if (parent.left == null) {
                    parent.left = node;
                } else {
                    parent.right = node;
                }
            }
            stack.push(node);
        } else if (c == '1') {
            HuffmanNode right = stack.pop();
            HuffmanNode left = stack.pop();
            HuffmanNode parent = new HuffmanNode(left, right);
            if (stack.isEmpty()) {
                root = parent;
            } else {
                HuffmanNode grandParent = stack.peek();
                if (grandParent.left == left) {
                    grandParent.left = parent;
                } else {
                    grandParent.right = parent;
                }
            }
            stack.push(parent);
        } else {
            throw new IllegalArgumentException("Invalid header: " + header);
        }
    }
    if (stack.size() != 1) {
        throw new IllegalArgumentException("Invalid header: " + header);
    }
    return root;
}

这样，我们就实现了一个基于哈夫曼树的数据压缩算法。

基于哈夫曼树的数据压缩算法代码

以下是基于哈夫曼树的数据压缩算法的C++代码：

#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>

using namespace std;

// 定义哈夫曼树节点
struct HuffmanNode {
    char ch;                // 字符
    int freq;               // 频率
    HuffmanNode* left;      // 左子树
    HuffmanNode* right;     // 右子树

    HuffmanNode(char ch, int freq) {
        this->ch = ch;
        this->freq = freq;
        left = nullptr;
        right = nullptr;
    }

    // 定义比较运算符，用于优先队列排序
    bool operator<(const HuffmanNode& other) const {
        return freq > other.freq;
    }
};

// 建立哈夫曼树
HuffmanNode* buildHuffmanTree(unordered_map<char, int>& freqMap) {
    // 构建优先队列，按照频率从小到大排序
    priority_queue<HuffmanNode> minHeap;
    for (auto& pair : freqMap) {
        minHeap.push(HuffmanNode(pair.first, pair.second));
    }

    // 循环取出两个频率最小的节点，合并为一个新节点，并将新节点加入队列
    while (minHeap.size() > 1) {
        HuffmanNode* left = new HuffmanNode(minHeap.top().ch, minHeap.top().freq);
        minHeap.pop();
        HuffmanNode* right = new HuffmanNode(minHeap.top().ch, minHeap.top().freq);
        minHeap.pop();
        HuffmanNode* parent = new HuffmanNode('\0', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        minHeap.push(*parent);
    }

    // 队列中剩余的节点即为根节点
    HuffmanNode* root = new HuffmanNode(minHeap.top().ch, minHeap.top().freq);
    root->left = minHeap.top().left;
    root->right = minHeap.top().right;

    return root;
}

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

    if (root->left == nullptr && root->right == nullptr) {
        codeTable[root->ch] = code;
        return;
    }

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

// 压缩数据
string compressData(string data) {
    // 统计字符频率
    unordered_map<char, int> freqMap;
    for (char ch : data) {
        freqMap[ch]++;
    }

    // 建立哈夫曼树
    HuffmanNode* root = buildHuffmanTree(freqMap);

    // 生成哈夫曼编码表
    unordered_map<char, string> codeTable;
    generateHuffmanCodeTable(root, "", codeTable);

    // 压缩数据
    string compressedData;
    for (char ch : data) {
        compressedData += codeTable[ch];
    }

    return compressedData;
}

// 解压数据
string decompressData(string compressedData, HuffmanNode* root) {
    string decompressedData;
    HuffmanNode* node = root;

    for (char bit : compressedData) {
        if (bit == '0') {
            node = node->left;
        } else {
            node = node->right;
        }

        if (node->left == nullptr && node->right == nullptr) {
            decompressedData += node->ch;
            node = root;
        }
    }

    return decompressedData;
}

int main() {
    string data = "hello world";
    cout << "Original data: " << data << endl;

    // 压缩数据
    string compressedData = compressData(data);
    cout << "Compressed data: " << compressedData << endl;

    // 解压数据
    string decompressedData = decompressData(compressedData, buildHuffmanTree(unordered_map<char, int>()));
    cout << "Decompressed data: " << decompressedData << endl;

    return 0;
}

以上代码中，首先统计字符频率，然后建立哈夫曼树，生成哈夫曼编码表，最后根据编码表压缩数据。在解压数据时，根据哈夫曼树的结构和编码表进行反向解码。