- #1

jarekduda

- 82

- 5

Huffman coding (e.g. A -> 010) is fast but approximates probabilities with powers of 1/2, while e.g. symbol of probability 0.99 carries only ~0.014 bits of information. This inaccuracy was repaired by arithmetic coding, but it is an order magnitude slower (more costly).

Above compromise has been recently ended with ANS coding, which is both fast(cheap) and accurate:

wiki: https://en.wikipedia.org/wiki/Asymmetric_Numeral_Systems

benchmarks: https://sites.google.com/site/powturbo/entropy-coder

It is used in compressors since 2014, like the currently default Apple LZFSE or great and free Facebook Zstd - it is 2-5x faster than gzip and provides much better compression:

https://github.com/facebook/zstd/

7-zip version: https://mcmilk.de/projects/7-Zip-zstd/

https://dl.dropboxusercontent.com/u/12405967/ZSTD.png

Above compromise has been recently ended with ANS coding, which is both fast(cheap) and accurate:

wiki: https://en.wikipedia.org/wiki/Asymmetric_Numeral_Systems

benchmarks: https://sites.google.com/site/powturbo/entropy-coder

It is used in compressors since 2014, like the currently default Apple LZFSE or great and free Facebook Zstd - it is 2-5x faster than gzip and provides much better compression:

https://github.com/facebook/zstd/

7-zip version: https://mcmilk.de/projects/7-Zip-zstd/

https://dl.dropboxusercontent.com/u/12405967/ZSTD.png

Last edited by a moderator: