Space-efficient Huffman codes revisited
Szymon Grabowski, Dominik Köppl · Information Processing Letters · 2022
A canonical Huffman code is an optimal prefix-free compression code whose codewords enumerated in the lexicographical order form a list of binary words in non-decreasing lengths. Gagie et al. (2015) gave a representation of this coding capable of encoding and decoding a symbol in constant worst-case time. It uses σlgℓmax+o(σ)+O(ℓmax2) bits of space, where σ and ℓmax are the alphabet size and maximum codeword length, respectively. We refine their representation to reduce the space complexity to σlgℓmax(1+o(1)) bits while preserving the constant encode and decode times. Our algorithmic idea can be applied to any canonical code.