It depends if you have static or adaptive coder. Static is much cheaper, uses the same probabilities for the entire data block (e.g. 30 kB), probabilities are

It depends if you have static or adaptive coder. Static is much cheaper, uses the same probabilities for the entire data block (e.g. 30 kB), probabilities are stored in the header - practically all Huffman and tANS compressors (however, there are considered exceptions: https://en.wikipedia.org/wiki/Adaptive_Huffman_coding https://en.wikipedia.org/wiki/Adaptive_Huffman_coding ). Adaptive can start with e.g. uniform probability (no need to store in header) and learns on the way - it is more costly but gives better compression, used with arithmetic coding or rANS. See https://fgiesen.wordpress.com/2015/05/26/models-for-adaptive-arithmetic-coding/ https://fgiesen.wordpress.com/2015/05/26/models-for-adaptive... https://fgiesen.wordpress.com/2015/12/21/rans-in-practice/ https://fgiesen.wordpress.com/2015/12/21/rans-in-practice/