On the Maximum Size of a Prefix Code

Výsledky výskumu našich pracovníkov Viliama Hromadu a Otokara Grošeka boli prijaté do prestížneho časopisu IEEE Transactions on Information Theory. Tento časopis mal v roku 2021 Impact factor na hodnote 2.978.

Peter Horák, Viliam Hromada, Otokar Grošek: On the Maximum Size of a Prefix Code

Abstrakt: 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.

Celý článok nájdete na stránkach vydavateľstva IEEE.