2
$\begingroup$

When storing the encoded Huffman bit stream in bytes, in general, either

  1. the final byte gets padded or
  2. 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).

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "For this to work, the total byte length of the Huffman encoded data needs to be known when decoding." In other words, you can save bits from the encoding if you can assume that an external oracle provides the extra bits. That may work in practice (as long as you don't need to concatenate two or more compressed streams) but it's not a valid information-theoretic argument. $\endgroup$ – rici Nov 17 '18 at 21:21
  • $\begingroup$ @rici It's not always easy to decide to which stack exchange community to put a question - in this case to stackoverflow or here. It's also true however that many algorithms in computer science rely on the number of items (e.g. items to sort) to be known. In practice, this "oracle" does indeed almost always exist, because e.g. the file size is known, or network streams are "framed" to make the size known beforehand. This includes chunking as used by HTTP to transfer data of (initially) unknown length. $\endgroup$ – Eugene Beresovsky Nov 18 '18 at 23:33
  • $\begingroup$ In the case of chunked http transfers, I don't think anyone would suggest that the transmission size does not include the bytes encoding the length, any more than anyone would suggest that the size of a mime multipart transmission does not include the length of the delimiters. Perhaps non-chunked transmission would be a better example. But as I said earlier, the use of "implicit" length indicators breaks down as soon as you need to put together a series of compressed objects in a single container (eg. Tar or Zip files). I wasn't complaining about your posting this Q here, by the way. $\endgroup$ – rici Nov 19 '18 at 0:07
  • $\begingroup$ ... sorry if I left you with that impression. $\endgroup$ – rici Nov 19 '18 at 0:08
  • $\begingroup$ @rici No worries, you didn't close-vote this q, so... I used chunking as an extreme example to show that the size can be known before the last byte is read even in cases where streaming is involved. When data is not streamed, the length is almost always known. Tar and zip files store the file lengths explicitly. But the deflate compression method indeed uses end-of-block markers and allows concatenation of multiple blocks (although iinm this is (was?) not supported e.g. by .Net's GZipStream / DeflateStream). So there's both in practice. $\endgroup$ – Eugene Beresovsky Nov 19 '18 at 1:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.