Sub-linear Decoding of Huffman Codes Almost In-Place

We present a succinct data structure storing the Huffman encoding that permits sublineardecoding in the number of transmitted bits. The size of the extra storage except forthe storage of the symbols in the alphabet for the new data structure is O(l log N) bits, wherel is the longest Huffman code and N is the number of symbols in the alphabet. We presenta solution that typically decodes texts of sizes ranging from a few hundreds up to 68 000with only one third to one fifth of the...