Why Huffman code in reverse order？

[huhu0823]

I'm very interested in compression.Huffman coding can be performed sequentially，I can't understand why huffman code is executed in reverse order in the code.

[Cyan4973]

FSE needs to encode and decode in reverse directions.
There are multiple conventions possible, this implementation selects to write the compressed bitstream forward, and read backward.
This results in a bitstream format, which is built around the assumption of forward writing, and backward reading.

For simplicity, the Huffman implementation in this repository employs the same bitstream.
Since the compressed bitstream will be read backward, but we still want the decoded symbols to be written forward, it follows that they must be written in the compressed bitstream in reverse order.

Obviously, other conventions could have been used. And it's also possible to read + write huffman forward, which is probably easier to follow. This would "just" require another bitstream implementation.

[huhu0823]

FSE needs to encode and decode in reverse directions. There are multiple conventions possible, this implementation selects to write the compressed bitstream forward, and read backward. This results in a bitstream format, which is built around the assumption of forward writing, and backward reading.

For simplicity, the Huffman implementation in this repository employs the same bitstream. Since the compressed bitstream will be read backward, but we still want the decoded symbols to be written forward, it follows that they must be written in the compressed bitstream in reverse order.

Obviously, other conventions could have been used. And it's also possible to read + write huffman forward, which is probably easier to follow. This would "just" require another bitstream implementation.

Thank you for your reply！Your answer made me suddenly understand.

[jdmarshall]

This is essentially the same limitation of ANS - in order to work with fractional bits per encoded byte, you end up treating the data like a stack. You push things on at the writer, and pop them off at the reader. Last in, first out.

From the tutorials I've seen, some ANS implementations chose to reverse a block of data as step 1 and then process it so the reader is simpler.