File Entropy.h

↰ Parent directory (ADS/compression)

The empirical entropies against which the compressors of this folder are measured.

Definition (ADS/compression/Entropy.h)

Detailed Description

The entropy of order 0 of a distribution is :math:` H_0 = sum_sigma P[ sigma ] log_2 ( 1 / P[ sigma ] ) ` bits per symbol, and that of a string s takes :math:` P[ sigma ] = n_sigma / |s| , the frequency of :math: sigma ` in s; it bounds from below the average length of a prefix-free code (Shannon), and the code of Huffman stays within one bit of it, :math:` H_0 le L_H < H_0 + 1 ` [see File CanonicalHuffman.h], while the arithmetic code of s takes at most :math:` 2 + |s| H_0 ` bits [see File ArithmeticCoding.h]. The entropy of order k of s is :math:` H_k( s ) = frac{1}{|s|} sum_{w in Sigma^k} |w_s| H_0( w_s ) , where :math: w_s ` is the string of the symbols that follow the occurrences of w in s, in their order; :math:` H_k le H_0 , and it is the measure reached by the models of context [see :ref:`file_ADS_compression_PPM.h] and by the compressors built on the Burrows-Wheeler transform [see File BurrowsWheeler.h]. Each function takes :math:` O( |s| log |s| ) ` time.

The contracts [see File Contract.h]: the frequencies are not negative and not all 0. The functions are defined in Entropy.tpp.

  1. Ferragina, Pearls of Algorithm Engineering, Cambridge University Press, 2023, chapters 12 and 14

    1. Shannon, A mathematical theory of communication, Bell System Technical Journal 27(3), 379-423, 1948, doi:10.1002/j.1538-7305.1948.tb01338.x

  1. Manzini, An analysis of the Burrows-Wheeler transform, Journal of the ACM 48(3), 407-430, 2001, doi:10.1145/382780.382782

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions