algorithm - 斐波那契数的最佳霍夫曼代码

Question

以下字符的最佳霍夫曼码是什么，其频率是前 8 个斐波那契数：a：1，b：1，c：2，d：3，e：5，f：8，g：13，h：21 ? 当频率是前 n 个斐波那契数时，概括该情况以找到最佳代码。

这是我遇到的作业问题之一。我不是要求一个直接的答案，只是为了一些资源。

我应该在哪里寻找将各个部分组合在一起来回答问题？

Answer 1

霍夫曼编码算法取两个频率最低的节点，将它们连接起来形成一个父节点，其子节点的频率之和相等。在符号的随机频率中，我们每次都需要计算要组合的至少两个节点，但在斐波那契频率序列的情况下，斐波那契数列中的序列与霍夫曼编码中的序列相同。

示例：-a：1，b：1，c：2，d：3，e：5，f：8，g：13，h：21

它将形成一个左倾斜或右倾斜的树，其中每个符号的编码都可以使用简单的公式得出

如果 n 不是符号

a = (n-2)*0 + 0

b = (n-2)*0 + 1

c = (n-3)*0 + 1

d = (n-4)*0 + 1

e = (n-5)*0 + 1

. . . 最后 = 1

所以对于上面的例子

a = (n-2)*0 + 0 = (6)*0 + 0 = 0000000

b = (6)*0 + 1 = 0000001

c = (5)*0 + 1 = 000001

…………

我希望你能得到模式

有趣的是平均位长的计算

avg = ((n-1)*2 + sumof((n-i+1)*fib(i)) 其中 i in (3,n))/(sumof(fib(i)) 其中 i in (1, n))

以上可以简化为直接公式。

Answer 2

阅读 - http://en.wikipedia.org/wiki/Huffman_coding - 特别注意短语“从左到右生成二叉树，取两个最不可能的符号并将它们放在一起形成另一个具有概率等于两个符号之和。重复该过程，直到只有一个符号“。

以上与斐波那契数列有何关系？