Re:How are zlib, gzip and Zip related? (2013)
by ralfd on Saturday June 18, 2016 @02:17PM
(#11929876)
Interesting, but it is all spanish to me ... What are "fractional bits"?
[ Parent
| on HN ]
Re:How are zlib, gzip and Zip related? (2013)
by eln1 on Saturday June 18, 2016 @04:22PM
(#11930444)
Generally, a symbol of probability p contains lg(1/p) bits of information: 1 bit if p=1/2, 2 bits if p=1/4 etc.
In Huffman you directly assign a concrete bit sequence to every symbol - it is perfect if their probabilities are powers of 1/2, but generally is not true: requires approximations, leading to a suboptimal compression ratio.
Accurate entropy coders like arithmetic/range coding or ANS family can directly work on symbols of general probabilities: containing a non-integer number of bits. It has to finally produce complete bits - their fractional number is handled by the state of the coder - kind of a buffer containing a fractional number of bits. Complete bits are produced as soon as they accumulate.
Re:How are zlib, gzip and Zip related? (2013)
by niftich on Saturday June 18, 2016 @02:23PM
(#11929902)
This blog post [1] and its predecessor explaining Huffman Codes [2] was a very helpful guide for me.
[1] https://hbfs.wordpress.com/2011/11/01/fractional-bits-part-i... [2] https://hbfs.wordpress.com/2011/05/17/huffman-codes/