用java实现哈夫曼编码

哈夫曼编码是一种可变长度编码，它可以将出现频率高的字符用短的编码表示，而出现频率低的字符用长的编码表示，从而达到压缩数据的目的。在Java中实现哈夫曼编码可以遵循以下步骤：

1. 定义一个节点类（Node）来表示哈夫曼树的节点，包括字符、出现频率和左右子节点。

class Node {
    char ch;
    int freq;
    Node left, right;

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

2. 统计字符串中每个字符的出现频率，并将其存储在一个Map中。

Map<Character, Integer> freqMap = new HashMap<>();
for (int i = 0; i < str.length(); i++) {
    char ch = str.charAt(i);
    freqMap.put(ch, freqMap.getOrDefault(ch, 0) + 1);
}

3. 构建哈夫曼树，首先将所有节点按照出现频率排序，然后取出最小的两个节点，将它们合并成一个新的节点，并将新节点插入到原来的节点列表中，重复这个过程直到只剩下一个节点，即根节点。

List<Node> nodes = new ArrayList<>();
for (Map.Entry<Character, Integer> entry : freqMap.entrySet()) {
    nodes.add(new Node(entry.getKey(), entry.getValue(), null, null));
}
while (nodes.size() > 1) {
    Collections.sort(nodes, Comparator.comparingInt(o -> o.freq));
    Node left = nodes.remove(0);
    Node right = nodes.remove(0);
    Node parent = new Node('\0', left.freq + right.freq, left, right);
    nodes.add(parent);
}

4. 构建哈夫曼编码表，从根节点开始遍历哈夫曼树，并记录下每个字符对应的编码，当遍历到叶子节点时，将编码存储到编码表中。

Map<Character, String> codeMap = new HashMap<>();
StringBuilder codeBuilder = new StringBuilder();
buildCodeMap(root, codeBuilder, codeMap);

private static void buildCodeMap(Node node, StringBuilder codeBuilder, Map<Character, String> codeMap) {
    if (node == null) {
        return;
    }
    if (node.left == null && node.right == null) {
        codeMap.put(node.ch, codeBuilder.toString());
    } else {
        buildCodeMap(node.left, codeBuilder.append('0'), codeMap);
        codeBuilder.setLength(codeBuilder.length() - 1);
        buildCodeMap(node.right, codeBuilder.append('1'), codeMap);
        codeBuilder.setLength(codeBuilder.length() - 1);
    }
}

5. 将字符串编码，按照编码表将每个字符转换成对应的二进制编码。

StringBuilder encodedBuilder = new StringBuilder();
for (int i = 0; i < str.length(); i++) {
    char ch = str.charAt(i);
    encodedBuilder.append(codeMap.get(ch));
}
String encoded = encodedBuilder.toString();

完整的代码如下：

import java.util.*;

public class Huffman {
    static class Node {
        char ch;
        int freq;
        Node left, right;

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

    public static void main(String[] args) {
        String str = "hello world!";
        Map<Character, Integer> freqMap = new HashMap<>();
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            freqMap.put(ch, freqMap.getOrDefault(ch, 0) + 1);
        }

        List<Node> nodes = new ArrayList<>();
        for (Map.Entry<Character, Integer> entry : freqMap.entrySet()) {
            nodes.add(new Node(entry.getKey(), entry.getValue(), null, null));
        }
        while (nodes.size() > 1) {
            Collections.sort(nodes, Comparator.comparingInt(o -> o.freq));
            Node left = nodes.remove(0);
            Node right = nodes.remove(0);
            Node parent = new Node('\0', left.freq + right.freq, left, right);
            nodes.add(parent);
        }

        Node root = nodes.get(0);
        Map<Character, String> codeMap = new HashMap<>();
        StringBuilder codeBuilder = new StringBuilder();
        buildCodeMap(root, codeBuilder, codeMap);

        StringBuilder encodedBuilder = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            encodedBuilder.append(codeMap.get(ch));
        }
        String encoded = encodedBuilder.toString();

        System.out.println("Original string: " + str);
        System.out.println("Encoded string: " + encoded);
    }

    private static void buildCodeMap(Node node, StringBuilder codeBuilder, Map<Character, String> codeMap) {
        if (node == null) {
            return;
        }
        if (node.left == null && node.right == null) {
            codeMap.put(node.ch, codeBuilder.toString());
        } else {
            buildCodeMap(node.left, codeBuilder.append('0'), codeMap);
            codeBuilder.setLength(codeBuilder.length() - 1);
            buildCodeMap(node.right, codeBuilder.append('1'), codeMap);
            codeBuilder.setLength(codeBuilder.length() - 1);
        }
    }
}