Re:AWS switch from gzip to zstd – about 30% reduction in com...
by shargs on Saturday August 20, 2022 @08:56AM
(#32531734)
For what it's worth, shameless plug, I've written a whole series on how FSE works: https://shargs.github.io/data-compression/2022/07/28/entropy...
Re:AWS switch from gzip to zstd – about 30% reduction in com...
by Dylan16807 on Saturday August 20, 2022 @03:19AM
(#32529981)
It's not that crazy if you separate it into two parts.
A) Use arithmetic coding to encode symbols as fractions instead of using an integer number of bits for each symbol. https://en.wikipedia.org/wiki/Arithmetic_coding http://www.ws.binghamton.edu/fowler/fowler%20personal%20page...
B) Shuffle the bits around so that you can use faster math and lookup tables instead of directly operating on fractions.
>FSE, short for Finite State Entropy, is an entropy codec based on ANS. FSE encoding/decoding involves a state that is carried over between symbols, so decoding must be done in the opposite direction as encoding. Therefore, all FSE bitstreams are read from end to beginning. Note that the order of the bits in the stream is not reversed, we just read the elements in the reverse order they are written.
https://en.wikipedia.org/wiki/Asymmetric_numeral_systems