数据结构-贪心算法（哈夫曼编码）_贪心算法哈夫曼编码的实现

哈夫曼编码（Huffman Coding）是一种用于无损数据压缩的编码技术。哈夫曼编码算法基于字符出现的频率来构建最优前缀码。经常出现的字符使用较短的码，不常出现的字符使用较长的码，从而实现数据的有效压缩。

哈夫曼编码的Java实现通常涉及以下几个步骤：

1. 统计每个字符的出现频率。
2. 创建一个优先队列（通常是最小堆）来存储所有字符及其频率，并按频率排序。
3. 构建哈夫曼树，过程是重复从优先队列中取出两个最小元素，创建一个新的内部节点作为它们的父节点，该父节点的频率是两个孩子频率的总和。然后将这个父节点放回优先队列中。重复这个过程直到队列中只剩下一个节点，这个节点就是哈夫曼树的根节点。
4. 对哈夫曼树进行遍历，并为每个字符分配一个唯一的二进制码。

以下是哈夫曼编码的一个Java实现：

import java.util.PriorityQueue;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

public class HuffmanCoding {
    
    // 哈夫曼树节点类
    static class Node {
        char ch;
        int frequency;
        Node left = null, right = null;

        Node(char ch, int frequency) {
            this.ch = ch;
            this.frequency = frequency;
        }

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

    // 比较器，用于比较哈夫曼树节点的频率
    static class NodeComparator implements Comparator<Node> {
        public int compare(Node x, Node y) {
            return x.frequency - y.frequency;
        }
    }

    // 创建哈夫曼树
    public static Node buildHuffmanTree(String text) {
        // 统计字符频率并存储在map中
        Map<Character, Integer> frequencyMap = new HashMap<>();
        for (char c : text.toCharArray()) {
            frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
        }

        // 创建优先队列
        PriorityQueue<Node> pq = new PriorityQueue<>(new NodeComparator());
        for (Map.Entry<Character, Integer> entry : frequencyMap.entrySet()) {
            pq.add(new Node(entry.getKey(), entry.getValue()));
        }

        // 合并节点直到只剩一个节点（根节点）
        while (pq.size() > 1) {
            Node left = pq.poll();
            Node right = pq.poll();
            int sum = left.frequency + right.frequency;
            pq.add(new Node('\0', sum, left, right));
        }

        // 返回根节点
        return pq.poll();
    }

    // 为每个字符生成哈夫曼编码
    public static void encode(Node root, String str, Map<Character, String> huffmanCode) {
        if (root == null) return;

        // 叶节点
        if (root.left == null && root.right == null) {
            huffmanCode.put(root.ch, str.length() > 0 ? str : "1");
        }

        // 遍历左子树
        encode(root.left, str + "0", huffmanCode);
        // 遍历右子树
        encode(root.right, str + "1", huffmanCode);
    }

    public static void main(String[] args) {
        String text = "Huffman coding is a data compression algorithm.";

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

        // 创建一个空的哈夫曼编码表
        Map<Character, String> huffmanCode = new HashMap<>();
        encode(root, "", huffmanCode);

        // 打印生成的哈夫曼编码
        System.out.println("Huffman Codes: " + huffmanCode);

        // 打印编码后的字符串
        StringBuilder sb = new StringBuilder();
        for (char c : text.toCharArray()) {
            sb.append(huffmanCode.get(c));
        }
        System.out.println("Encoded Text: " + sb);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

在这个Java程序中：

• 定义了一个Node内部类来表示哈夫曼树的节点，包含字符、频率及左右子节点。
• NodeComparator类用来在优先队列中比较节点的频率。
• buildHuffmanTree方法用于构建哈夫曼树，将字符和频率封装成节点放入优先队列，然后不断合并直到只剩下根节点。
• encode方法用于为哈夫曼树的每个叶节点生成相应的编码，并将其存储在huffmanCode字典中。
• 在main方法中，我们构建哈夫曼树，生成哈夫曼编码，并将原始文本转换为由01组成的编码字符串。

哈夫曼编码算法能够高效地进行无损压缩，它在诸如文件压缩、数据传输等领域有着广泛的应用。