Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Interesting, but it is all spanish to me ... What are "fractional bits"?


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.


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/




Consider applying for YC's Winter 2027 batch! Applications are open till November 2.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: