java哈夫曼编码译码

哈夫曼编码是一种用于数据压缩的算法，可以将一个字符串压缩为更短的二进制串。Java中实现哈夫曼编码的基本思路如下：

1. 统计字符串中每个字符出现的频率，并将其存储到一个HashMap中。

2. 根据每个字符的出现频率构建哈夫曼树，即将频率低的字符作为叶子节点，频率高的字符作为父节点，构建一个树形结构。可以使用优先队列来实现。

3. 对哈夫曼树进行编码，即给每个字符赋予一个唯一的二进制编码。从根节点开始遍历哈夫曼树，对于每个左子树节点赋值0，右子树节点赋值1，直到所有叶子节点都被编码。

4. 将原始字符串按照哈夫曼编码进行压缩，即将每个字符替换为其对应的二进制编码。压缩后的二进制串可存储到文件中。

5. 对压缩后的二进制串进行解码，即将二进制串按照哈夫曼编码重新转换为原始字符串。

下面是Java实现哈夫曼编码和解码的示例代码：

import java.util.*;

public class HuffmanCoding {
    private Map<Character, String> codeTable = new HashMap<>();

    private class HuffmanNode implements Comparable<HuffmanNode> {
        char c;
        int freq;
        HuffmanNode left, right;

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

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

        public int compareTo(HuffmanNode other) {
            return freq - other.freq;
        }
    }

    public void encode(String s) {
        Map<Character, Integer> freqTable = new HashMap<>();

        for (char c : s.toCharArray()) {
            freqTable.put(c, freqTable.getOrDefault(c, 0) + 1);
        }

        PriorityQueue<HuffmanNode> pq = new PriorityQueue<>();
        for (char c : freqTable.keySet()) {
            pq.offer(new HuffmanNode(c, freqTable.get(c)));
        }

        while (pq.size() > 1) {
            HuffmanNode node1 = pq.poll();
            HuffmanNode node2 = pq.poll();

            HuffmanNode parent = new HuffmanNode('\0', node1.freq + node2.freq);
            parent.left = node1;
            parent.right = node2;

            pq.offer(parent);
        }

        HuffmanNode root = pq.poll();
        buildCodeTable(root, "");
        String encoded = "";
        for (char c : s.toCharArray()) {
            encoded += codeTable.get(c);
        }
        System.out.println("Encoded string: " + encoded);
    }

    public void decode(String s, HuffmanNode root) {
        HuffmanNode node = root;
        String decoded = "";
        for (char c : s.toCharArray()) {
            if (c == '0') {
                node = node.left;
            } else {
                node = node.right;
            }

            if (node.isLeaf()) {
                decoded += node.c;
                node = root;
            }
        }
        System.out.println("Decoded string: " + decoded);
    }

    private void buildCodeTable(HuffmanNode node, String code) {
        if (node != null) {
            if (node.isLeaf()) {
                codeTable.put(node.c, code);
            } else {
                buildCodeTable(node.left, code + "0");
                buildCodeTable(node.right, code + "1");
            }
        }
    }

    public static void main(String[] args) {
        String s = "hello world";
        HuffmanCoding hc = new HuffmanCoding();
        hc.encode(s);

        // reconstruct the tree from the code table
        HuffmanCoding.HuffmanNode root = hc.new HuffmanNode('\0', 0);
        for (char c : hc.codeTable.keySet()) {
            String code = hc.codeTable.get(c);
            HuffmanCoding.HuffmanNode node = root;
            for (char bit : code.toCharArray()) {
                if (bit == '0') {
                    if (node.left == null) {
                        node.left = hc.new HuffmanNode('\0', 0);
                    }
                    node = node.left;
                } else {
                    if (node.right == null) {
                        node.right = hc.new HuffmanNode('\0', 0);
                    }
                    node = node.right;
                }
            }
            node.c = c;
        }

        hc.decode("001010001101111011110000101100111100101100", root);
    }
}