In huffman Compress, i don't know why no code will be longer than 16 bits, when all frequencies are scaled to fit within one byte

Question

"Each code is a short integer because it can be proven that when all frequencies are scaled to fit within one byte, no code will be longer than 16 bits"

Does it mean that the depth of Huffman tree is 16? If it is true, how to calculate depth of full binary tree? If it isn't, What's the meaning of it?

Answer 1

Your excerpt is not complete somehow. The depth also depends on the number of symbols you are coding. If, for example, you are coding 100,000 different symbols, each of which occurs just once (where 1 fits quite easily in a byte), then you will need more than 16 bits per symbol. The depth of that tree will be 17.

What they are referring to is a worst-case set of frequencies that maximizes the code length that would result from the Huffman algorithm. That worst case set is a variant of the Fibonacci sequence.