4

长话短说，我正在尝试从规范的霍夫曼列表中生成霍夫曼代码。本质上，应该运行以下两个循环，并生成一个二进制字符串。代码是：

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。

我认为我的问题在于嵌套循环，但是我无法弄清楚为什么它在一次运行中完美运行，而在另一次运行中失败。

我可能只是遗漏了一些明显的东西，但我看不到它。

任何建议将不胜感激。

谢谢

更新

回顾我的代码后，我似乎在首先读取数据时犯了一个小错误，因此我得到了不正确的霍夫曼代码！

4

1 回答 1

1

第二个示例中的前两个代码的长度均为 1，在前两个代码之后没有其他可能的代码。所有前缀模式都已用完。

您的代码应保留可用剩余代码的计数以检测错误输入。只需减少每个代码的计数，每次向上移动到下一个长度时将计数加倍，比当前长度多一倍。（即使没有该长度的代码，也要确保加倍，例如，如果您从长度为 3 的代码移动到长度为 5 的代码，即使没有长度为 4 的代码，也要加倍计数。）从两个开始计数对于长度为一的代码。

如果该计数变为负数，则您有一个错误，您可以停在那里。无法将代码分配给该组长度。

如果在过程结束时计数不为零，那么您的代码不完整。根据您的应用程序，这可能是也可能不是错误。这意味着代码不是最优的，并且可以使用更少的位来对这些符号进行编码。

于 2013-05-12T17:02:50.517 回答