哈夫曼编码java

哈夫曼编码是一种常见的压缩算法，可以将一个字符串或文件转换为一个较小的二进制编码。以下是使用Java实现哈夫曼编码的示例代码：

import java.util.*;

public class HuffmanCoding {

    private static class Node implements Comparable<Node> {
        int frequency;
        char character;
        Node left, right;

        public Node(char character, int frequency, Node left, Node right) {
            this.character = character;
            this.frequency = frequency;
            this.left = left;
            this.right = right;
        }

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

        @Override
        public int compareTo(Node node) {
            return frequency - node.frequency;
        }
    }

    private static Map<Character, String> encode(String text) {
        // 统计字符频率
        Map<Character, Integer> frequencyMap = new HashMap<>();
        for (char c : text.toCharArray()) {
            frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
        }

        // 构建哈夫曼树
        Queue<Node> queue = new PriorityQueue<>();
        for (char c : frequencyMap.keySet()) {
            queue.add(new Node(c, frequencyMap.get(c), null, null));
        }
        while (queue.size() > 1) {
            Node left = queue.poll();
            Node right = queue.poll();
            queue.add(new Node('\0', left.frequency + right.frequency, left, right));
        }
        Node root = queue.poll();

        // 构建编码表
        Map<Character, String> encodingMap = new HashMap<>();
        buildEncodingMap(root, "", encodingMap);

        // 编码文本
        Map<Character, String> encodedText = new HashMap<>();
        for (char c : text.toCharArray()) {
            encodedText.put(c, encodingMap.get(c));
        }

        return encodedText;
    }

    private static void buildEncodingMap(Node node, String code, Map<Character, String> map) {
        if (node.isLeaf()) {
            map.put(node.character, code);
        } else {
            buildEncodingMap(node.left, code + "0", map);
            buildEncodingMap(node.right, code + "1", map);
        }
    }

    public static void main(String[] args) {
        String text = "hello world";
        Map<Character, String> encodingMap = encode(text);
        System.out.println("Encoding Map: " + encodingMap);
        StringBuilder encodedText = new StringBuilder();
        for (char c : text.toCharArray()) {
            encodedText.append(encodingMap.get(c));
        }
        System.out.println("Encoded Text: " + encodedText);
    }
}

在上面的示例中，我们首先统计了给定文本中每个字符的频率。然后，我们使用优先队列（最小堆）构建哈夫曼树，其中每个节点都包含一个字符、其频率以及左右子节点。接下来，我们使用递归方式构建编码表，其中每个字符都映射到一个二进制编码。最后，我们使用编码表将原始文本转换为二进制编码。