Re: Re: [Lzip-bug] lzip vs. zstd

[wrotycz]

> The theoretical basis of zstd[2] seems more complicated than that of LZMA

Well, it's new, from 2013/14, but it's actually not complicated, simpler and easier to understand and implement than arithmetic coding. In simple terms it is 'bit back arithmetic coding'.

Zstd, and I guess LZFSE, are table version, called tANS, of regular ANS, and its implementation called rANS; r - for range I guess, or to refer to range coding.

From what I tried, arithmetic/range coding is more complex, and slower than (r)ANS.

Original papers date back to 2009/2013

Asymmetric numeral systems; by original inventor - Jaroslaw Duda

arxiv.org/abs/0902.0271

Asymmetric numeral systems: entropy coding combining speed of Huffman coding with compression rate of arithmetic coding

arxiv.org/abs/1311.2540

but I found the best, and most palatable explanation by Robert Bamler

Understanding Entropy Coding With Asymmetric Numeral Systems (ANS): a Statistician's Perspective

arxiv.org/abs/2201.01741

Data Compression With Deep Probabilistic Models

https://robamler.github.io/teaching/compress21/

https://robamler.github.io/teaching/compress22/

https://robamler.github.io/teaching/compress23/

All the best