News for hackers. Stuff that matters.
Re:Modern LZ Compression (2019) by user-the-name on Tuesday August 17, 2021 @08:23PM (#28216350)
"Modern", but uses Huffman coding? No LZ implementation aiming for high compression in the last decade has used Huffman.
Re:Modern LZ Compression (2019) by hexxagone on Tuesday August 17, 2021 @09:39PM (#28216841)
You mean like zstd and brotli ? Is there any new LZ codec not using Huffman ?
Re:Modern LZ Compression (2019) by retrac on Tuesday August 17, 2021 @10:11PM (#28217083)
It was my understanding Zstd used neither Huffman or AC but something else: https://en.wikipedia.org/wiki/Asymmetric_numeral_systems

Edit: It uses a variety of entropy encodings for different data structures, Huffman is one of them. My apologies for the confusing initial comment.

Re:Modern LZ Compression (2019) by chriswarbo on Tuesday August 17, 2021 @08:51PM (#28216547)
> For our goal of a high compression LZ variant, we will want to Huffman code our symbols (zstd actually uses FSE, a variant of arithmetic coding to do this, but we will cover that in a future post).
Re:Modern LZ Compression (2019) by user-the-name on Tuesday August 17, 2021 @08:57PM (#28216583)
But why? Why spend that much effort introducing a method that is basically entirely outdated at this point, and is also fairly complicated?
Re:Modern LZ Compression (2019) by hexxagone on Tuesday August 17, 2021 @09:43PM (#28216873)
Huffmann is rather simple and hard to beat in decompression speed.
Re:Modern LZ Compression (2019) by vardump on Wednesday August 18, 2021 @05:24AM (#28219127)
For high entropy data (=somewhat random data), FSE is quite comparable to Huffman in compression speed.

For low entropy (lots of high probability symbols, like zeroes), Huffman is about 2-3x faster. But on the flipside, FSE achieves markedly higher compression ratio.

I think FSE is worth the speed tradeoff vs Huffman in most cases.

Re:Modern LZ Compression (2019) by hexxagone on Wednesday August 18, 2021 @11:49AM (#28222972)
"FSE achieves markedly higher compression ratio". I do not thin it is true, FSE/ANS achieves slightly better ratios in general. Zstd uses both Huffman (for large alphabets) and FSE (for small alphabets).
Re:Modern LZ Compression (2019) by user-the-name on Wednesday August 18, 2021 @06:15AM (#28219363)
Arithmetic coding is much, much simpler. And decompression speed is not a limiting factor in most applications of data compression like this.
Re:Modern LZ Compression (2019) by hexxagone on Wednesday August 18, 2021 @11:56AM (#28223079)
"Arithmetic coding is much, much simpler." Let us agree to disagree. "And decompression speed is not a limiting factor in most applications of data compression like this". It depends on the application. Zstd and Brotli are certainly aiming at the fastest decompression speed possible.
Re:Modern LZ Compression (2019) by user-the-name on Wednesday August 18, 2021 @02:07PM (#28224942)
Arithmetic coding can be implemented in as little as maybe ten lines of code. It is far simpler than Huffman coding.
Re:Modern LZ Compression (2019) by hexxagone on Wednesday August 18, 2021 @08:27PM (#28228945)
The Huffman encoding loop is 2 lines and decoding loop is 4 lines of branchless code. Do you have an example of branchless arithmetic encoder or decoder ?