java实现哈夫曼编码

哈夫曼编码是一种可变长度编码，用于将消息压缩。在 Java 中实现哈夫曼编码可以分为以下几个步骤：

1. 统计每个字符出现的次数。
2. 构建哈夫曼树。
3. 生成哈夫曼编码表。
4. 将消息使用哈夫曼编码表进行编码。
5. 将编码后的消息写入文件。

下面是一个简单的 Java 实现：

import java.util.*;

public class HuffmanEncoder {
    private Map<Character, Integer> charFreqs;
    private HuffmanNode root;

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

        public HuffmanNode(char ch, int freq, HuffmanNode left, HuffmanNode right) {
            this.ch = ch;
            this.freq = freq;
            this.left = left;
            this.right = right;
        }

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

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

    public HuffmanEncoder(String message) {
        charFreqs = new HashMap<>();
        for (char c : message.toCharArray()) {
            charFreqs.put(c, charFreqs.getOrDefault(c, 0) + 1);
        }
        root = buildHuffmanTree();
    }

    private HuffmanNode buildHuffmanTree() {
        PriorityQueue<HuffmanNode> pq = new PriorityQueue<>();
        for (char c : charFreqs.keySet()) {
            pq.add(new HuffmanNode(c, charFreqs.get(c), null, null));
        }
        while (pq.size() > 1) {
            HuffmanNode left = pq.poll();
            HuffmanNode right = pq.poll();
            pq.add(new HuffmanNode('\0', left.freq + right.freq, left, right));
        }
        return pq.poll();
    }

    private void buildCodeTable(Map<Character, String> table, HuffmanNode node, String code) {
        if (node.isLeaf()) {
            table.put(node.ch, code);
        } else {
            buildCodeTable(table, node.left, code + "0");
            buildCodeTable(table, node.right, code + "1");
        }
    }

    public Map<Character, String> getCodeTable() {
        Map<Character, String> codeTable = new HashMap<>();
        buildCodeTable(codeTable, root, "");
        return codeTable;
    }

    public String encode(String message) {
        StringBuilder sb = new StringBuilder();
        Map<Character, String> codeTable = getCodeTable();
        for (char c : message.toCharArray()) {
            sb.append(codeTable.get(c));
        }
        return sb.toString();
    }

    public void writeEncodedMessageToFile(String fileName, String encodedMessage) {
        try (BitOutputStream out = new BitOutputStream(fileName)) {
            for (char bit : encodedMessage.toCharArray()) {
                out.write(bit - '0');
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

使用示例：

String message = "hello world";
HuffmanEncoder encoder = new HuffmanEncoder(message);
String encodedMessage = encoder.encode(message);
encoder.writeEncodedMessageToFile("encoded.bin", encodedMessage);

这个示例将消息 "hello world" 进行哈夫曼编码，并将编码后的消息写入文件 "encoded.bin" 中。