Codage entropique

En théorie de l'information , un codage entropique (ou codage entropique ) est une méthode de compression de données sans perte qui tente d'approcher la limite inférieure énoncée par le théorème de codage de source de Shannon , qui stipule que toute méthode de compression de données sans perte doit avoir une longueur de code attendue supérieure ou égale à l' entropie de la source.

Plus précisément, le théorème de codage de source stipule que pour toute distribution de source, la longueur de code attendue satisfait , où est la fonction spécifiant le nombre de symboles dans un mot de code, est la fonction de codage, est le nombre de symboles utilisés pour produire les codes de sortie et est la probabilité du symbole source. Un codage entropique tente d'approcher cette borne inférieure.

Deux des techniques de codage entropique les plus courantes sont le codage de Huffman et le codage arithmétique . Si les caractéristiques entropiques approximatives d'un flux de données sont connues à l'avance (notamment pour la compression de signal ), un code statique plus simple peut s'avérer utile. Ces codes statiques comprennent les codes universels (tels que le codage gamma d'Elias ou le codage de Fibonacci ) et les codes de Golomb (tels que le codage unaire ou le codage de Rice ).

Depuis 2014, les compresseurs de données utilisent la famille de techniques de codage entropique des systèmes numériques asymétriques (ANS), qui permet de combiner le taux de compression du codage arithmétique avec un coût de traitement similaire à celui du codage de Huffman . Les systèmes ANS ont été adoptés par les compresseurs développés par Facebook ( Zstandard ), Apple ( LZFSE ) et Google (Draco), entre autres.

Le codage entropique exploite le fait que certains symboles apparaissent plus fréquemment que d'autres. Lorsque les probabilités des symboles sont inégales, certains résultats sont plus prévisibles, et cette prévisibilité peut être utilisée pour représenter les données avec moins de bits. Inversement, lorsque tous les symboles sont équiprobables, chaque symbole véhicule la quantité maximale d'information possible et aucune compression n'est possible.

When compression is not possible: A stream of independent fair coin flips, where heads and tails each occur with probability 0.5, has an entropy of 1 bit per symbol, exactly the cost of storing one binary digit. Since every symbol already takes the minimum possible space, there is no redundancy to exploit, and no entropy coding method can make the data any smaller on average. The same principle applies to larger alphabets: independent ternary symbols (0, 1, 2) each with probability 1/3 have an entropy of about 1.585 bits per symbol, the maximum for a three-symbol alphabet, and are likewise incompressible.

When compression is possible: If the same binary source instead produces 1s with probability 0.9 and 0s with probability 0.1, the entropy drops to about 0.469 bits per symbol. This is well below the 1-bit storage cost, because the predominance of 1s makes each symbol partially predictable. An entropy coder such as arithmetic coding can exploit this predictability to achieve a compression ratio of roughly 2.1:1 by assigning shorter codes to the more common symbol.

Practical example: English text has an alphabet of roughly 27 characters (26 letters plus a space). If all characters occurred equally often, each would require about 4.75 bits. However, because letter frequencies are highly unequal ('e' occurs far more often than 'z') and letters are not independent ('u' almost always follows 'q'), the true entropy of English has been estimated at roughly 1.0 to 1.5 bits per character. This large gap is what makes English text highly compressible.

Besides using entropy coding as a way to compress digital data, an entropy encoder can also be used to measure the amount of similarity between streams of data and already existing classes of data. This is done by generating an entropy coder/compressor for each class of data; unknown data is then classified by feeding the uncompressed data to each compressor and seeing which compressor yields the highest compression. The coder with the best compression is probably the coder trained on the data that was most similar to the unknown data. This approach is grounded in the concept of normalized compression distance, a parameter-free, universal similarity metric based on compression that approximates the uncomputable normalized information distance.