Java实现Canonical Huffman Code参考代码输出非前缀码异常求助

问题描述 #

实现规范哈夫曼编码时，运行的Java代码仅在官方示例输入下可输出正确结果，其余输入场景下生成的编码不满足前缀码要求，结果错误。

测试用例 #

输入

char[] chararr = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
int[] freq = {119, 173, 186, 134, 134, 8, 220, 216, 145, 10};

错误输出

1:0
2:1
3:10
4:11
6:100
7:101
8:110
0:1110
5:11110
9:11111

该输出存在明显前缀冲突，例如2:1是3:10、4:11等编码的前缀，不符合前缀码的基本要求。

问题原因 #

错误出在根据字符频率计算编码长度的前置步骤，核心问题有两点：

• 哈夫曼树构建阶段节点排序规则缺失：优先队列比较器仅按频率排序，频率相同的节点无固定次级排序规则，导致生成的叶节点编码长度序列不符合规范哈夫曼的长度约束。
• 编码赋值前的符号排序逻辑错误：规范哈夫曼要求符号先按编码长度升序排列，长度相同的符号需按字符字典序升序排列，原代码缺失该排序逻辑，直接按原频率顺序排列符号，导致编码赋值时出现前缀重叠。

修复方案 #

1. 修正哈夫曼树节点排序逻辑 #

调整优先队列的比较器逻辑，当两个节点频率相同时，按节点存储的最小字符字典序排序，保证哈夫曼树生成的编码长度稳定且符合要求。

2. 修正编码赋值前的符号排序规则 #

收集所有符号及其对应编码长度后，先按编码长度升序排序，长度相同则按字符字典序升序排序，再执行规范编码的赋值操作。

修复后该测试用例的正确输出（无任何前缀冲突） #

6:00
7:01
1:10
2:11
3:000
4:001
8:010
0:011
5:11110
9:11111

内容的提问来源于stack exchange，提问作者beginner