Comment mesurer pratiquement l'entropie d'un fichier?

9

J'essaie de mesurer maintenant beaucoup d'informations non redondantes (réelles) que contient mon fichier. Certains appellent cela la quantité d'entropie.

Bien sûr, il existe le journal standard p (x) {p (x)}, mais je pense que Shannon ne le considérait que du point de vue de la transmission via un canal. Par conséquent, la formule nécessite une taille de bloc (disons en bits, 8 généralement). Pour un fichier volumineux, ce calcul est assez inutile, ignorant les corrélations de courte à longue distance entre les symboles.

Il existe des méthodes d'arbre binaire et de Ziv-Lempel, mais elles semblent de nature très académique.

La compressibilité est également considérée comme une mesure de l'entropie, mais il ne semble pas y avoir de limite inférieure quant au degré de compression. Pour mon fichier hiss.wav,

  • hiss.wav d'origine = 5,2 Mo
  • entropie via la formule de Shannon = 4,6 Mo
  • hiss.zip = 4,6 Mo
  • sifflement.7z = 4,2 Mo
  • hiss.wav.fp8 = 3,3 Mo

Existe-t-il une méthode raisonnablement praticable pour mesurer la quantité d'entropie qui existe dans hiss.wav?

entropy Paul Uszak
la source
1
Je ne comprends pas ce que vous entendez par «très académique».
David Richerby
Ardent mort. J'aurais pensé qu'avec l'ampleur des dollars consacrés à la recherche à l'échelle mondiale pour maximiser la transmission et le stockage des données, il y aurait une manière plus développée d'estimer la quantité de trucs dont vous vous occupez réellement. Je ne l'aurais pas pensé au-delà des domaines de possibilité qu'il y aurait un utilitaire de fichier que vous passez sur certaines données qui génère l'estimation entropique théorique. À quoi jouent les fabricants de télécommunications et de disques?
Paul Uszak

Réponses:

9

L'entropie est une caractéristique d'une variable aléatoire . Un fichier donné a une entropie nulle, car il est constant. L'entropie est logique dans de nombreuses situations où il n'y a pas de canal, et vous pouvez l'appliquer à un ensemble aléatoire de fichiers WAV, par exemple, généré à partir d'une source donnée. Dans ce cas, votre est l' intégralité du fichier WAV.X

NNHNHN+o(N)gzip

En raison de ce résultat de Lempel et Ziv, l'entropie d'une source peut être approximée en compressant une longue séquence d'échantillons à l'aide de l'algorithme Lempel – Ziv. Cela n'évalue pas l'entropie des échantillons spécifiques, ce qui n'est pas un concept bien défini (une séquence constante a une entropie nulle), mais plutôt l'entropie de la source qui la génère.

Un concept connexe est l' entropie algorithmique , également connue sous le nom de complexité de Kolmogorov . Il s'agit de la longueur du programme le plus court générant votre fichier. Cette quantité a du sens pour un fichier individuel. Dans le cas d'un fichier généré par une source aléatoire, le théorème de Lempel-Ziv montre que l'entropie algorithmique d'un fichier est limitée, avec une forte probabilité, par son entropie de Shannon. Malheureusement, l'entropie algorithmique n'est pas calculable, il s'agit donc davantage d'un concept théorique.

Pour compléter l'image, je suggère de lire l'article de Shannon sur la prédiction et l'entropie de l'anglais imprimé pour une approche différente de l'estimation de l'entropie d'une source.

Yuval Filmus
la source
J'ai. Et le papier Schurmann & Grassberger. Sur la base de leurs entropies estimées pour l'anglais, il semble que la meilleure estimation d'entropie que nous puissions obtenir est via la compression avec une variante PAQ8 comme fp8. Il y a et mes résultats se marient assez bien pour la prose shakespearienne.
Paul Uszak
Le problème semble être cependant que j'aurais pensé qu'il devait y avoir une valeur théorique limite pour l'entropie d'une source. La détermination par compression ne reflète que l'efficacité de l'algorithme de compression. Empiriquement, votre gzip est bon, mais 7z est meilleur. Et fp8 est beaucoup mieux comme le montre ma question. Puis-je trouver que hiss.wav ne contient que 10 octets d'entropie totale lorsque j'utilise fp12000 dans un avenir lointain?
Paul Uszak
L'entropie n'est pas la propriété d'un fichier; chaque fichier individuel n'a aucune entropie. L'entropie est plutôt une propriété d'une source aléatoire. Une mesure du caractère aléatoire qui convient à des fichiers spécifiques est la complexité de Kolmogorov (également connue sous le nom d'entropie algorithmique), mais malheureusement cette mesure n'est pas calculable.
Yuval Filmus
Lorsque vous compressez un fichier pour estimer l'entropie d'une source, vous utilisez un théorème qui garantit que le taux de compression des données générées par la source s'approche de l'entropie de la source. Cependant, les utilitaires de compression réels n'appliquent pas l'algorithme vanilla Lempel – Ziv, mais plutôt une version plus pratique de celui-ci. Si vous voulez estimer l'entropie, vous devriez peut-être réimplémenter l'algorithme avec cet objectif à l'esprit.
Yuval Filmus
J'ai supprimé une discussion non constructive; les commentaires ne sont pas pour de longues discussions, sauf pour améliorer le poste à portée de main. Si vous souhaitez discuter honnêtement des questions d'entropie, veuillez créer une salle de chat. N'oubliez pas de le garder civil.
Raphael