logoalt Hacker News

duskwuffyesterday at 8:46 PM1 replyview on HN

A common design in compressors is to use LZ as a first step, but to then represent the constant data and/or offset-length pairs from LZ using an entropy coder.

Deflate (as used in gzip) uses a Huffman coder. LZMA (as used by xz) uses a predictive range coder. Zstandard can use either Huffman or FSE. Some high-speed compressors like LZ4 skip the entropy coding stage entirely at the expense of compression ratio.

Bzip2 is an interesting aversion of this pattern - it uses the Burrows-Wheeler transform as a first pass instead of LZ. Unfortunately, this is one of the major reasons why it's so slow.


Replies

sgsjchsyesterday at 11:36 PM

The first LZ-step pretty much directly maps to BPE tokenization in LLMs.

show 1 reply