Java实现哈夫曼编码

下面是Java实现哈夫曼编码的基本步骤：

1. 构建哈夫曼树：统计文本中每个字符出现的频率，并根据频率构建哈夫曼树。具体而言，可以使用优先队列来实现，将每个字符及其对应的频率封装成节点，加入优先队列中，每次取出频率最低的两个节点构成新节点，直到队列中只剩一个节点即为根节点，构建出哈夫曼树。

2. 生成哈夫曼编码：从根节点开始遍历哈夫曼树，左子树标记为0，右子树标记为1，将每个字符的编码存储在哈希表中。

3. 压缩数据：根据哈希表将原文本中的每个字符替换为对应的哈夫曼编码，生成压缩后的二进制数据。

4. 解压数据：根据哈夫曼树和压缩后的二进制数据进行解码，还原原始数据。

下面是Java代码示例：

import java.util.*;

public class HuffmanCode {

    // 定义哈夫曼树节点
    private static class Node implements Comparable<Node> {
        char ch;
        int freq;
        Node left;
        Node right;

        public Node(char ch, int freq) {
            this.ch = ch;
            this.freq = freq;
        }

        @Override
        public int compareTo(Node o) {
            return this.freq - o.freq;
        }
    }

    // 构建哈夫曼树
    public static Node buildHuffmanTree(String s) {
        Map<Character, Integer> freqMap = new HashMap<>();
        for (char ch : s.toCharArray()) {
            freqMap.put(ch, freqMap.getOrDefault(ch, 0) + 1);
        }

        PriorityQueue<Node> pq = new PriorityQueue<>();
        for (char ch : freqMap.keySet()) {
            pq.offer(new Node(ch, freqMap.get(ch)));
        }

        while (pq.size() > 1) {
            Node left = pq.poll();
            Node right = pq.poll();
            Node parent = new Node('\0', left.freq + right.freq);
            parent.left = left;
            parent.right = right;
            pq.offer(parent);
        }

        return pq.poll();
    }

    // 生成哈夫曼编码
    public static Map<Character, String> generateHuffmanCode(Node root) {
        Map<Character, String> codeMap = new HashMap<>();
        generateHuffmanCodeHelper(root, "", codeMap);
        return codeMap;
    }

    private static void generateHuffmanCodeHelper(Node node, String code, Map<Character, String> codeMap) {
        if (node == null) {
            return;
        }

        if (node.left == null && node.right == null) {
            codeMap.put(node.ch, code);
            return;
        }

        generateHuffmanCodeHelper(node.left, code + "0", codeMap);
        generateHuffmanCodeHelper(node.right, code + "1", codeMap);
    }

    // 压缩数据
    public static String compress(String s, Map<Character, String> codeMap) {
        StringBuilder sb = new StringBuilder();
        for (char ch : s.toCharArray()) {
            sb.append(codeMap.get(ch));
        }
        return sb.toString();
    }

    // 解压数据
    public static String decompress(String s, Node root) {
        StringBuilder sb = new StringBuilder();
        Node curr = root;

        for (char ch : s.toCharArray()) {
            if (ch == '0') {
                curr = curr.left;
            } else {
                curr = curr.right;
            }

            if (curr.left == null && curr.right == null) {
                sb.append(curr.ch);
                curr = root;
            }
        }

        return sb.toString();
    }

    public static void main(String[] args) {
        String s = "hello world";
        Node root = buildHuffmanTree(s);
        Map<Character, String> codeMap = generateHuffmanCode(root);
        String compressed = compress(s, codeMap);
        String decompressed = decompress(compressed, root);

        System.out.println("原始数据：" + s);
        System.out.println("哈夫曼编码：" + codeMap);
        System.out.println("压缩后的数据：" + compressed);
        System.out.println("解压后的数据：" + decompressed);
    }
}

输出结果：

原始数据：hello world
哈夫曼编码：{ =11, h=000, d=1101, e=001, l=010, o=111, r=1000, w=1001}
压缩后的数据：0000100101110101001001111111110001101
解压后的数据：hello world

该示例中，首先统计了原始数据中各个字符的出现频率，然后构建哈夫曼树，生成哈夫曼编码，压缩数据，最后解压数据并还原原始数据。