- 定义 Huffman 树的节点结构：使用一个实现了
Comparable接口的内部类。 - 构建 Huffman 树：统计字符频率，创建优先队列（最小堆），并逐步构建树。
- 生成编码表：通过遍历 Huffman 树，为每个字符生成其对应的二进制编码。
- 编码过程：将输入字符串转换为 Huffman 编码后的二进制字符串。
- 解码过程：将 Huffman 编码的二进制字符串还原为原始字符串。
- 主函数演示：展示整个流程。
完整的 Java 代码
import java.util.*;
/**
* Huffman 编码的 Java 实现
*/
public class HuffmanCoding {
// Huffman 树的节点内部类
private static class HuffmanNode implements Comparable<HuffmanNode> {
char character; // 字符
int frequency; // 频率
HuffmanNode left; // 左子节点
HuffmanNode right; // 右子节点
// 构造函数（用于叶子节点）
public HuffmanNode(char character, int frequency) {
this.character = character;
this.frequency = frequency;
this.left = null;
this.right = null;
}
// 构造函数（用于内部节点）
public HuffmanNode(int frequency, HuffmanNode left, HuffmanNode right) {
this.character = '\0'; // 内部节点没有字符
this.frequency = frequency;
this.left = left;
this.right = right;
}
// 实现 Comparable 接口，以便在优先队列中进行排序
@Override
public int compareTo(HuffmanNode other) {
return this.frequency - other.frequency;
}
}
/**
* 构建 Huffman 树
* @param frequencyMap 字符频率映射表
* @return Huffman 树的根节点
*/
private static HuffmanNode buildHuffmanTree(Map<Character, Integer> frequencyMap) {
// 使用优先队列（最小堆）来存储节点，每次都能快速取出频率最小的节点
PriorityQueue<HuffmanNode> priorityQueue = new PriorityQueue<>();
// 1. 将所有字符节点（叶子节点）加入优先队列
for (Map.Entry<Character, Integer> entry : frequencyMap.entrySet()) {
priorityQueue.add(new HuffmanNode(entry.getKey(), entry.getValue()));
}
// 2. 循环处理，直到队列中只剩一个节点（即树的根节点）
while (priorityQueue.size() > 1) {
// 取出频率最小的两个节点
HuffmanNode left = priorityQueue.poll();
HuffmanNode right = priorityQueue.poll();
// 创建一个新的内部节点，其频率为两个子节点频率之和
// 内部节点的字符设为 '\0'，表示它不是叶子节点
HuffmanNode parent = new HuffmanNode(left.frequency + right.frequency, left, right);
// 将新节点加入优先队列
priorityQueue.add(parent);
}
// 3. 队列中剩下的最后一个节点就是 Huffman 树的根节点
return priorityQueue.poll();
}
/**
* 从 Huffman 树生成编码表
* @param root Huffman 树的根节点
* @param code 当前正在构建的编码
* @param encodingMap 存储最终编码结果的映射表
*/
private static void generateEncodingTable(HuffmanNode root, String code, Map<Character, String> encodingMap) {
// 递归终止条件：如果节点为空，则返回
if (root == null) {
return;
}
// 如果是叶子节点，则将字符和对应的编码存入映射表
if (root.left == null && root.right == null) {
encodingMap.put(root.character, code);
return;
}
// 递归处理左子树，编码追加 '0'
generateEncodingTable(root.left, code + "0", encodingMap);
// 递归处理右子树，编码追加 '1'
generateEncodingTable(root.right, code + "1", encodingMap);
}
/**
* 对输入字符串进行 Huffman 编码
* @param input 输入字符串
* @return 编码后的二进制字符串
*/
public static String encode(String input) {
// 1. 统计字符频率
Map<Character, Integer> frequencyMap = new HashMap<>();
for (char c : input.toCharArray()) {
frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
}
// 2. 构建 Huffman 树
HuffmanNode root = buildHuffmanTree(frequencyMap);
// 3. 生成编码表
Map<Character, String> encodingMap = new HashMap<>();
generateEncodingTable(root, "", encodingMap);
// 4. 使用编码表将输入字符串转换为二进制编码
StringBuilder encodedString = new StringBuilder();
for (char c : input.toCharArray()) {
encodedString.append(encodingMap.get(c));
}
return encodedString.toString();
}
/**
* 对 Huffman 编码的二进制字符串进行解码
* @param encodedString 编码后的二进制字符串
* @param root Huffman 树的根节点
* @return 解码后的原始字符串
*/
public static String decode(String encodedString, HuffmanNode root) {
StringBuilder decodedString = new StringBuilder();
HuffmanNode current = root;
// 5. 遍历二进制编码字符串，根据 '0' 和 '1' 在 Huffman 树中移动
for (int i = 0; i < encodedString.length(); i++) {
char bit = encodedString.charAt(i);
if (bit == '0') {
current = current.left;
} else { // bit == '1'
current = current.right;
}
// 如果到达了叶子节点，说明找到了一个字符
if (current.left == null && current.right == null) {
decodedString.append(current.character);
// 重置回根节点，以便查找下一个字符
current = root;
}
}
return decodedString.toString();
}
public static void main(String[] args) {
String originalString = "huffman coding is a data compression algorithm";
System.out.println("原始字符串: " + originalString);
System.out.println("------------------------------------");
// 1. 编码
String encodedString = encode(originalString);
System.out.println("Huffman 编码结果: " + encodedString);
// 为了演示解码，我们需要 Huffman 树的根节点
// 重新构建频率图和树（在实际应用中，这些信息需要被保存和传输）
Map<Character, Integer> frequencyMap = new HashMap<>();
for (char c : originalString.toCharArray()) {
frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
}
HuffmanNode root = buildHuffmanTree(frequencyMap);
// 2. 解码
String decodedString = decode(encodedString, root);
System.out.println("解码后字符串: " + decodedString);
System.out.println("------------------------------------");
System.out.println("编码和解码是否成功: " + originalString.equals(decodedString));
}
}
代码详解
HuffmanNode 类
这是 Huffman 树的基本单元。
（图片来源网络，侵删）
character: 存储字符，对于内部节点（非叶子节点），这个值为'\0'。frequency: 该节点代表的字符在原始文本中出现的频率。left,right: 指向左右子节点的引用。implements Comparable<HuffmanNode>: 这是为了让HuffmanNode对象可以存入PriorityQueue（优先队列）。compareTo方法根据frequency进行比较，确保频率最小的节点总是在队列的最前面。
buildHuffmanTree(Map<Character, Integer> frequencyMap) 方法
这是 Huffman 编码的核心步骤，用于构建树。
- 输入：一个字符到其频率的映射表。
- 步骤：
- 创建一个
PriorityQueue<HuffmanNode>，在 Java 中，PriorityQueue默认是最小堆。 - 遍历频率映射表,为每个字符创建一个
HuffmanNode（叶子节点），并加入优先队列。 - 开始循环：从队列中取出两个频率最小的节点
left和right。 - 创建一个新的内部节点
parent，其频率为left.frequency + right.frequency，left和right分别作为其左右子节点。 - 将
parent节点重新加入队列。 - 重复步骤 3-5，直到队列中只剩下一个节点，这个节点就是 Huffman 树的根节点。
- 创建一个
generateEncodingTable(...) 方法
这个方法通过深度优先遍历 Huffman 树来生成编码表。
- 输入：Huffman 树的根节点、当前正在构建的编码字符串、一个用于存储最终结果的
Map<Character, String>。 - 逻辑：
- 从根节点开始,向左走时在当前编码后追加
'0'，向右走时追加'1'。 - 当遍历到一个叶子节点（即
left和right都为null）时，说明找到了一个字符，将字符和从根节点到该叶子节点的路径（即编码）存入encodingMap。 - 这是一个典型的递归深度优先搜索。
- 从根节点开始,向左走时在当前编码后追加
encode(String input) 方法
这是提供给用户的编码接口。
- 它依次调用
buildHuffmanTree和generateEncodingTable来获取编码表。 - 然后遍历原始字符串的每个字符,从编码表中查找对应的二进制编码，并拼接成一个长字符串。
decode(String encodedString, HuffmanNode root) 方法
这是解码接口。
（图片来源网络，侵删）
- 输入：编码后的二进制字符串 和 Huffman 树的根节点。
- 逻辑：
- 从根节点开始,逐个读取二进制字符串中的
'0'或'1'。 - 遇到
'0'，就移动到当前节点的左子节点；遇到'1'，就移动到右子节点。 - 当移动到一个叶子节点时,就找到了一个字符，将其追加到结果字符串中，并重置当前节点为根节点，以便继续查找下一个字符。
- 重复此过程,直到二进制字符串被完全处理。
- 从根节点开始,逐个读取二进制字符串中的
main 方法
- 演示了如何使用上述方法。
- 首先对字符串进行编码,然后使用得到的编码结果和 Huffman 树的根节点进行解码，最后验证解码后的字符串是否与原始字符串一致。
运行结果示例
运行 main 方法，你可能会得到类似下面的输出（Huffman 树的结构可能略有不同，导致编码结果不完全一样，但解码结果必须一致）：
原始字符串: huffman coding is a data compression algorithm
------------------------------------
Huffman 编码结果: 011010110111111001010111010011111010110111100101110101111101101111110111100101011111010110111101001011110110111110010101111101011011110100111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111110010101111010110111101001111110101101111100101011110101101111010011111010110111
（图片来源网络，侵删）
