algorithm - 霍夫曼编码 : shortest and longest code for Fibonacci frequencies

Question

对于具有斐波那契频率的 n 个字符，最短代码和最长霍夫曼代码的长度是多少？

据我了解 - 如果我们构建一棵树，它看起来就像一个分支，每个节点的长度为 1，从根部到最低的叶子都悬空。当我们从 n-2 个数字中创建第一个节点时，该节点的频率将为 F[n]-1，并且 F[n]>F[n]-1>F[n-1]。 (F[n-1] 是剩余最少的，F[n] 将是第二少剩余的)，通过归纳，这将适用于所有频率。

我们创建的树显然是一棵不平衡的树，我认为这不是好树。

如果这是创建树的最佳方式，那么最长的创建方式的长度是多少？如果不是最优路径，那么最短路径的长度是多少？

我是计算机科学的新手，非常希望得到很好的解释。

Answer 1

最短的代码长度为 1，最长的代码长度为 n-1。将有两个长度为n-1的符号，1..n-2中每个长度有一个符号。

只有一棵最优树，仅此而已。它不平衡没有什么不好的。事实上，必须使用最少的位数对具有这些频率的符号进行编码。

我不知道你说的“最短”或“最长”是什么意思。