Java循环和位移

Question

简单来说，我正在尝试从一个规范的哈夫曼列表中生成哈夫曼编码。基本上，以下两个循环应该运行，并生成二进制字符串。代码如下：

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。

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

我可能只是漏掉了一些明显的东西，但我看不出来。

如果有任何建议，将不胜感激。

谢谢

更新：

回顾我的代码后，似乎我在最初读取数据时实际上犯了一个小错误，因此我的哈夫曼编码是不正确的!!

- Tony

---

你正在边进行更新代码。根据你已经看到的值，霍夫曼编码的变化是很正常的。你面临的另一个问题是无法确定你的值在哪里停止，例如 1011000 是 4144111 还是 581。 - Peter Lawrey

我不太确定你的意思，彼得？我必须承认，霍夫曼编码仍然让我有点困惑。你能详细解释一下吗？ - Tony

我假设你是提前生成哈夫曼编码，否则你的问题就没有意义。通常情况下，你会在处理每个符号时更新哈夫曼编码。这意味着一个表示一个符号的编码后来可能表示不同的符号。 - Peter Lawrey

我看到了。我有一种感觉，我一开始读入了错误的数据。我需要回去检查我的输入方法。谢谢Peter。 - Tony

顺便提一下，00和01与0和1不同。我猜你的前两个符号应该是这样的。 - Peter Lawrey

Answer 1

你第二个例子中的前两个编码都只有长度为一，这意味着在这两个编码之后没有其他可能的编码了。所有的前缀模式都已经被使用完了。

你的代码应该保持一个可用剩余编码的计数，以检测错误的输入。简单地对每个编码进行减少计数，并且每次你移动到比当前长度多一的下一个长度时，将计数加倍。（确保即使没有那个长度的编码也要加倍，例如，如果你从长度为3的编码移动到长度为5的编码，则对长度为4的编码进行加倍，即使没有长度为4的编码）。将长度为1的编码的计数从2开始。

如果计数变成负数，那么就会出现错误，你可以立即停止。对于那组长度，无法分配编码。

如果在过程结束时计数不为零，则你有一个不完整的编码。这可能或可能不是一个错误，这意味着这个编码不是最佳的，可以使用更少的位来编码这些符号。

- Mark Adler