On the Maximum Size of a Prefix Code
Peter Horák, Viliam Hromada, Otokar Grošek · IEEE Transactions on Information Theory · 2023
A prefix code minimal with respect to a bitstring$x$is a prefix code where$x$is a concatenation of its codewords and it is minimal with respect to this property. What is the maximum size$M(n)$among all minimal codes over all bitstrings of length$n?$In this paper we determine the value of$M(n)$for all natural numbers$n$, discuss its computational complexity, relation to the Lambert function, provide tight upper bounds, and describe how the value of$M(n)$enables one to construct efficiently a Huffman code in the case of uniform probability distribution of the codewords.