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

Question

What is an optimal Huffman code for the following characters whose frequencies are the first 8 Fibonacci numbers: a : 1, b : 1, c : 2, d : 3, e : 5, f : 8, g : 13, h : 21? Generalize the case to find an optimal code when the frequencies are the first n Fibonacci numbers.

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

我应该在哪里寻找拼凑来回答问题？

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 在 (3,n))/(sumof(fib(i)) 其中 i 在(1,n))

以上可化简为直接公式。