Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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.



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


If doesn't correspond cleanly. I can see why you draw the link, because LZ compression will replace words with symbols but BPE is a non-contextual entropy encoding while LZ is contextual and adaptive and that makes it very different. I think BPE actually has more in common with Huffman encoding.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: