I made a Huffman algorithm for data compression: it takes the content of a file as an input and outputs a compressed string. More important, it generates optimal prefix codes (made of 0 and 1) for every possible character, that is to say for every number between 0 and 255.
While the size of a code cannot exceed 256, it is possible to encode every character with a code of size 8 at most.
However, it is impossible that the algorithm generates a code of size 256 because then the codes wouldn't be optimal. It will give to the most likely chars, codes of size < 8 and it will give codes of size > 8 to the others (intuitively).
My question thus is, how can we get an upper bound of the maximum size a code can have, better than 256? I don't see how to approach the problem.
PS: the upper bound I'm looking for doesn't depend on the probability distribution. It has to be an upper bound for every possible probability distribution. As I said, I doubt that there is a probability distribution for which there is a code of size 256, so there has to be an upper bound.
I think I found the solution: For an alphabet of size $n$, the longest possible code is of size $n-1$, so here the answer is 255. So I was actually wrong in my intuition. You just need to arrange the weights so that each one is at least twice as much as the precedent and you get a Huffman tree which outputs a code of maximal size.