Huffman Codes

Question 1

Are Huffman trees unique for a given frequency table? Is it possible to generate a different tree from this same table of frequencies that is also optimal?

Answer 1

No, the right and left subtrees are arbitrary. For ex, we can switch a and b below

   (1)
/      \   a        b

Question 2

Huffman Algorithm, runtime, and improvenment

Answer 2

T(n) = T(n-1) + 2*findmin

We have to find the minimum freq at each level for all letters, so this ends up being an N^2 algorithm.

However, employing a min heap, which is build in O(n) using Floyd’s method, and also gives us the minimum frequency with fix-up of O(logn). Then, the overall method becomes O(nlogn).

Details (not mandatory)

Huffman(S):
if |S| = 2:
return a tree with root and two leaves
ELSE:
(u, v) = find two min frequency chars in S
S = S - (u, v)
S = S + new char W which is fu + fv
T’ = Huffman(S)
T = T’ with leaf ω removed and replaced with interior node +two children, u and v; label left branch 0, right branch 1return T

Question 3

Fixed length vs Variable length encoding

Answer 3

Fixed length is wasteful and there’s no even frequency distribution

Variable-length encoding is better and avoids ambiguity by using prefix-free variable-length encoding.

Question 4

Read Huffman proof of correctness