Is Huffman or arithmetic-encoded data read bit-by-bit when decompressed?

Question

Huffman and arithmetic-encoded data is used in many different compression programs for entropy encoding. They create a new encoding for symbols to be compressed that may not align to byte boundary. This means that when the data has to be decompressed, it must be read bit by bit. However, that seems to be very very slow process.

How is Huffman and arithmetic-encoded data decompression usually sped up? Do we create some sort of table as with CRC calculations, that enables us to read in data per byte and then decode the symbols or is it always really read in a per-bit basis?

Answer 1

Efficient Huffman decoders use tables. You can see an example in zlib's inflate, which uses two levels of tables to reduce the time needed to construct the tables.

Constraints can be placed on arithmetic codes to also permit them to use tables, and this is often done for speed, with only a small impact on compression.