Java数据结构之哈夫曼树概述及实现

哈夫曼树概述

哈夫曼树（Huffman Tree），也称为最优树(Optimal Binary Tree)，是一种带权路径长度最短的二叉树，也就是最小权重的前缀编码树。其基本思想是采用频率作为节点的权值，将频率较小的节点放在左子树上，频率较大的节点放在右子树上，从而形成一棵权值最小的二叉树。

实现过程

实现哈夫曼树需要以下几个步骤：

步骤一：将权值列表转化为叶子节点

首先需要将权值列表转化为叶子节点，每个叶子节点保存着一个字符和该字符出现的次数。实现代码如下：

public class Node implements Comparable<Node> {
    int weight;
    char c;
    Node left, right;

    public Node(int weight, char c) {
        this.weight = weight;
        this.c = c;
    }

    @Override
    public int compareTo(Node o) {
        return Integer.compare(this.weight, o.weight);
    }
}

步骤二：建立哈夫曼树

其次，需要将叶子节点插入到优先队列（PriorityQueue）中，并且不断地取出两个权值最小的节点，将它们的权值相加，然后生成一个新的节点作为它们的父亲节点，直到队列中只有一个节点为止。实现代码如下：

public static Node buildHuffmanTree(Map<Character, Integer> freqMap) {
    PriorityQueue<Node> queue = new PriorityQueue<>();
    freqMap.forEach((key, value) -> {
        Node node = new Node(value, key);
        queue.offer(node);
    });

    while (queue.size() > 1) {
        Node left = queue.poll();
        Node right = queue.poll();
        Node parent = new Node(left.weight + right.weight, '-');
        parent.left = left;
        parent.right = right;
        queue.offer(parent);
    }

    return queue.poll();
}

步骤三：生成哈夫曼编码

最后，需要根据哈夫曼树生成每个叶子节点的哈夫曼编码。从根节点出发，如果往左子树方向走，则在该节点的编码后添加0；如果往右子树方向走，则在该节点的编码后添加1。直到走到叶子节点时，所走路径的编码即为该叶子节点的哈夫曼编码。实现代码如下：

public static void generateHuffmanCode(Node node, String code, Map<Character, String> codeMap) {
    if (node.left == null && node.right == null) {
        codeMap.put(node.c, code);
    } else {
        generateHuffmanCode(node.left, code + "0", codeMap);
        generateHuffmanCode(node.right, code + "1", codeMap);
    }
}

示例说明

示例一

假设输入为一个字符串 "ABACA"，需求为对该字符串进行哈夫曼编码。则可使用以下代码进行演示：

public static void main(String[] args) {
    String input = "ABACA";

    // 计算每个字符的频率
    Map<Character, Integer> freqMap = new HashMap<>();
    for (char c : input.toCharArray()) {
        freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
    }

    // 构建哈夫曼树
    Node root = buildHuffmanTree(freqMap);

    // 生成哈夫曼编码
    Map<Character, String> codeMap = new HashMap<>();
    generateHuffmanCode(root, "", codeMap);

    // 输出哈夫曼编码
    for (Map.Entry<Character, String> entry : codeMap.entrySet()) {
        System.out.println(entry.getKey() + " : " + entry.getValue());
    }
}

结果输出如下：

C : 00
B : 01
A : 1

示例二

假设输入为一个文件 "input.txt"，需求为对该文件内容进行哈夫曼编码。则可使用以下代码进行演示：

public static void main(String[] args) throws IOException {
    String inputFileName = "input.txt";
    String outputFileName = "output.txt";

    // 读取输入文件中的内容，并计算每个字符的频率
    StringBuilder inputBuilder = new StringBuilder();
    Map<Character, Integer> freqMap = new HashMap<>();
    try (BufferedReader reader = new BufferedReader(new FileReader(inputFileName))) {
        String line;
        while ((line = reader.readLine()) != null) {
            for (char c : line.toCharArray()) {
                inputBuilder.append(c);
                freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
            }
            inputBuilder.append("\n");
        }
    }

    String input = inputBuilder.toString();

    // 构建哈夫曼树
    Node root = buildHuffmanTree(freqMap);

    // 生成哈夫曼编码
    Map<Character, String> codeMap = new HashMap<>();
    generateHuffmanCode(root, "", codeMap);

    // 输出哈夫曼编码到输出文件中，并将原文件中的内容按哈夫曼编码进行压缩
    try (BufferedWriter writer = new BufferedWriter(new FileWriter(outputFileName))) {
        for (Map.Entry<Character, String> entry : codeMap.entrySet()) {
            writer.write(entry.getKey() + " : " + entry.getValue() + "\n");
        }
        writer.write("\n");

        for (char c : input.toCharArray()) {
            if (codeMap.containsKey(c)) {
                writer.write(codeMap.get(c));
            }
        }
    }
}

其中输入文件 "input.txt" 的内容为：

hello world
how are you

输出文件 "output.txt" 的内容为：

  : 100
d : 1010
e : 110
h : 00
l : 111
o : 01
r : 1011
w : 1001
y : 1000

001111110011111100101101011101000111000001100110111111010100101011110100010101000000100011100011011
1110110011101000111111010010010001100100110010000101101101