How to avoid having to store extra information about padding (for byte size alignment) with Huffman coding When storing the encoded Huffman bit stream in bytes, in general, either


the final byte gets padded or
a pseudo end-of-file symbol gets used


In the former case, the number of bits padded needs to be stored somewhere, requiring another 3 bits. In the latter, you will lose some efficiency due to the additional pseudo symbol.

So how can I avoid the extra cost of a pseudo symbol, and also avoiding the need to store/transmit extra bits to hold the number of pad bits?



N.B. On the one hand, I'm interested in compressing short strings, so saving 3 bits on average can shave off another 1% or so of the data.

But more importantly, getting rid of the need to send the padding info (which is only known after compressing the whole string) before the encoded data means I can more easily perform the algorithm in a streaming fashion. This is not really necessary for short strings, where everything may be kept in memory, but sometimes my strings actually do get much longer, and I don't want to have to keep that in memory (considering there are hundreds of simultaneous encodings going on).
There's a way that neither needs to store the number of padded bits, nor - in most real life scenarios *) - add a pseudo symbol.

The idea is this: The maximum padding is 7 bits, so if after the last encoded symbol, we pad with the first bits of a symbol that is encoded as 8 or more bits, the decoder will stop in the middle of decoding when the bit stream finishes, so no extraneous symbol gets decoded.

For this to work, the total byte length of the Huffman encoded data needs to be known when decoding.

*) If there is no existing symbol of length 8 or longer, then an end-of-file pseudo-symbol needs to be created. This should be added with the least possible frequency, in order not to make the encoding of real symbols grow in length, if possible. The length of the end-of-file symbol does not matter. If it is shorter than 8 bits, it can just be repeated multiple times to pad the last byte, and if longer than 8 bits, only the first bits necessary to pad the final byte will be used.