présentation
Lorsqu'on analyse deux fichiers contenant chacun un million de chiffres, l'un généré aléatoirement et l'autre étant les premiers chiffres de pi, on constate que les deux fichiers sont statistiquement identiques. Cependant, il est possible de compresser le fichier contenant les chiffres de pi en utilisant un programme court, alors que le fichier aléatoire ne peut pas être compressé.
compression et entropie
La compression est divisée en deux types : la compression statistique et la compression par processus. La compression statistique repose sur la fréquence d'apparition des symboles, tandis que la compression par processus repose sur la simplicité du processus de génération des symboles. L'entropie est une mesure de la quantité d'information contenue dans un signal, et elle est liée à la compression.
entropie et codage
L'entropie peut être calculée en utilisant la formule de Shannon, qui est dérivée à partir du principe de codage optimal. La longueur idéale d'un mot de code pour un symbole de probabilité p est de -log2(p) bits. Cela signifie que les symboles fréquents ont des mots de code courts, tandis que les symboles rares ont des mots de code longs.
implications et limites
La distinction entre les deux types de compression a des implications importantes pour la compréhension de la complexité et de la randomité. La compression par processus peut être utilisée pour détecter la présence d'un processus simple sous-jacent à un signal apparemment aléatoire. Cependant, il est important de noter que la compression par processus ne peut pas être appliquée à tous les signaux, et que la limite de la compression est déterminée par l'entropie du signal.
import math
def shannon_entropy(probabilities):
return -sum(p * math.log2(p) for p in probabilities)Ce code calcule l'entropie de Shannon pour une distribution de probabilités donnée.
