简单来说,我正在尝试从一个规范的哈夫曼列表中生成哈夫曼编码。基本上,以下两个循环应该运行,并生成二进制字符串。代码如下:
for (int i = 1; i <= 17; i++) {
for (int j = 0; j < input.length; j++) {
if (input[j] == i) {
result.put(allocateCode(i, j), j); //update a hashmap
huffCode += (1 << (17 - i)); //Update the huffman code
}
}
}
基本上,代码应该查找所有长度为1的代码,并为每个代码生成一个哈夫曼编码。例如,长度为1的应该按顺序为:0、1;长度为3的则应为100、101、110。
allocateCode
函数仅返回一个显示结果的字符串。第一次运行产生了以下结果:Huffman code for code 2 is: 0 (0) length was: 1
Huffman code for code 6 is: 10 (2) length was: 2
Huffman code for code 0 is: 1100 (12) length was: 4
Huffman code for code 3 is: 1101 (13) length was: 4
Huffman code for code 4 is: 1110 (14) length was: 4
Huffman code for code 7 is: 11110 (30) length was: 5
Huffman code for code 1 is: 111110 (62) length was: 6
Huffman code for code 5 is: 111111 (63) length was: 6
这是正确的,已生成正确的哈夫曼编码。但是,对于第二个长度数组的运行,会产生以下结果:
Huffman code for code 1 is: 0 (0) length was: 1
Huffman code for code 4 is: 1 (1) length was: 1
Huffman code for code 8 is: 100 (4) length was: 3
Huffman code for code 9 is: 100 (4) length was: 3
Huffman code for code 13 is: 101 (5) length was: 3
Huffman code for code 16 is: 1011000 (88) length was: 7
Huffman code for code 10 is: 10110001 (177) length was: 8
Huffman code for code 2 is: 101100011 (355) length was: 9
Huffman code for code 3 is: 101100011 (355) length was: 9
Huffman code for code 0 is: 1011001000 (712) length was: 10
Huffman code for code 5 is: 1011001000 (712) length was: 10
Huffman code for code 6 is: 1011001001 (713) length was: 10
Huffman code for code 7 is: 10110010011 (1427) length was: 11
Huffman code for code 14 is: 10110010011 (1427) length was: 11
Huffman code for code 17 is: 10110010100 (1428) length was: 11
Huffman code for code 19 is: 10110010100 (1428) length was: 11
Huffman code for code 18 is: 101100101010000 (22864) length was: 15
如您所见,同一代码被多次生成,例如代码8和9,以及代码2和3。
我认为问题在于嵌套循环中,但我无法弄清楚为什么它可以完美地运行一次,而另一次失败了。
我可能只是漏掉了一些明显的东西,但我看不出来。
如果有任何建议,将不胜感激。
谢谢
更新:
回顾我的代码后,似乎我在最初读取数据时实际上犯了一个小错误,因此我的哈夫曼编码是不正确的!!
1011000
是 4144111 还是 581。 - Peter Lawrey