霍夫曼编码树的最大高度
Maximum height of a huffman coding tree
假设所有字节都被接受，用霍夫曼编码算法生成的树的最大高度是多少。
我很好奇，因为当我试图压缩我随机生成的文件时，我以某种方式设法获得了 9 位的路径。这意味着我实质上扩大了文件的大小。虽然程序中可能存在我不知道的问题。
如果您所说的“所有字节”是指所有 256 个可能的字节值作为您的符号集，答案是最大深度以及最长代码的长度为 255。
虽然要得到这个需要非常大的符号频率。以最小的总计数执行此操作的序列是卢卡斯数，第零个卢卡斯数 2 分成两个 1。所以：
1, 1, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, ...
其中以 4 开头的项是前两项的总和，就像斐波那契数列一样。该序列中 256 个符号的最后一项是：
121020968315000050139390193037122554865361969834971243
约1053.
至于你所有可能字节的随机数据，一般情况下你不能压缩它。但是，如果您得到一个长度为 9 位的代码，那么这意味着该代码至少与为所有符号分配 8 位一样好。因此，您没有扩充文件，而是将其保持相同大小或将其缩小一点或更多。然而，这并没有考虑到您还必须发送代码本身，以便另一端的解码器可以解码。这将不仅仅是杀死你得到的任何一点压缩。
假设所有字节都被接受，用霍夫曼编码算法生成的树的最大高度是多少。
我很好奇，因为当我试图压缩我随机生成的文件时，我以某种方式设法获得了 9 位的路径。这意味着我实质上扩大了文件的大小。虽然程序中可能存在我不知道的问题。
如果您所说的“所有字节”是指所有 256 个可能的字节值作为您的符号集，答案是最大深度以及最长代码的长度为 255。
虽然要得到这个需要非常大的符号频率。以最小的总计数执行此操作的序列是卢卡斯数，第零个卢卡斯数 2 分成两个 1。所以：
1, 1, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, ...
其中以 4 开头的项是前两项的总和，就像斐波那契数列一样。该序列中 256 个符号的最后一项是：
121020968315000050139390193037122554865361969834971243
约1053.
至于你所有可能字节的随机数据，一般情况下你不能压缩它。但是，如果您得到一个长度为 9 位的代码，那么这意味着该代码至少与为所有符号分配 8 位一样好。因此，您没有扩充文件，而是将其保持相同大小或将其缩小一点或更多。然而，这并没有考虑到您还必须发送代码本身，以便另一端的解码器可以解码。这将不仅仅是杀死你得到的任何一点压缩。