Optimal Huffman Code for Fibonacci numbers

问题:

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.

This is one of the assignment problems I have. I'm not asking for a straight answer, just for some resources.

Where should I look to put the pieces together to answer the questions?

回答1:

Read - http://en.wikipedia.org/wiki/Huffman_coding - In particular, pay attention to the phrase "A binary tree is generated from left to right taking the two least probable symbols and putting them together to form another equivalent symbol having a probability that equals the sum of the two symbols. The process is repeated until there is just one symbol".

How does the above relate to the fibonacci series?

回答2:

Huffman coding algorithm takes two least frequency nodes and connects them to form a parent which has frequency equal sum of child nodes. In random frequency of symbols we need to compute the least two nodes to combine every time but in case of fibonacci sequence of frequecy the sequence in fibonacci series is same as sequence in huffman coding.

example: - a : 1, b : 1, c : 2, d : 3, e : 5, f : 8, g : 13, h : 21

it will form a left skewed or right skewed tree where the coding of each symbol can be derived using simple formula

if n is no of symbols

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

. . . last = 1

so for above example

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

b = (6)*0 + 1 = 0000001

c = (5)*0 + 1 = 000001

.......

I hope u r getting the pattern

interesting thing is calculation of average bit length

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

the above can simplified to direct formula.