Les algorithmes de compression sans perte réduisent-ils l'entropie?

35

Selon Wikipedia :

L'entropie de Shannon mesure les informations contenues dans un message par opposition à la partie du message qui est déterminée (ou prévisible). Des exemples de ces derniers incluent la redondance dans la structure du langage ou les propriétés statistiques relatives aux fréquences d'occurrence de paires de lettres ou de mots, de triplets, etc.

L'entropie est donc une mesure de la quantité d'informations contenues dans un message. Les codeurs entropiques sont utilisés pour compresser sans perte un tel message au nombre minimal de bits nécessaire pour le représenter (entropie). Pour moi, cela ressemble à un encodeur d'entropie parfait serait tout ce qui est nécessaire pour compresser sans perte un message autant que possible.

Cependant, de nombreux algorithmes de compression utilisent des étapes avant le codage entropique pour réduire supposément l'entropie du message.

Selon Wikipedia allemand

Entropiekodierer werden häufig mit anderen Kodierern kombiniert. Dabei dienen vorgeschaltete Verfahren dazu, Entropie de la recherche des données.

En anglais:

Les codeurs entropiques sont fréquemment combinés avec d'autres codeurs. Les étapes précédentes servent à réduire l'entropie des données.

C'est-à-dire que bzip2 utilise la transformation Burrows-Wheeler-Transform suivie par une transformation Move-To-Front-Transform avant d'appliquer le codage entropique (codage de Huffman dans ce cas).

Ces étapes réduisent-elles réellement l'entropie du message, ce qui impliquerait une réduction de la quantité d'informations contenues dans le message? Cela me semble contradictoire, car cela signifierait que des informations ont été perdues lors de la compression, empêchant ainsi une décompression sans perte. Ou ne font-ils que transformer le message pour améliorer l'efficacité de l'algorithme de codage par entropie? Ou bien l'entropie ne correspond-elle pas directement à la quantité d'informations dans le message?

robert
la source
1
Pourrait être un moyen d' estimer l'entropie cependant.
pipe le

Réponses:

39

De nombreuses descriptions occasionnelles d'entropie prêtent à confusion, car l'entropie n'est pas aussi nette et ordonnée qu'une mesure parfois présentée. En particulier, la définition standard de l'entropie de Shannon stipule qu'elle ne s'applique que, comme le dit Wikipedia, "les informations dues à des événements indépendants sont additives".

En d'autres termes, les événements indépendants doivent être statistiquement indépendants. Si ce n'est pas le cas, vous devez trouver une représentation des données définissant les événements de manière à les rendre réellement indépendants. Sinon, vous surestimerez l'entropie.

En d'autres termes, l'entropie de Shannon ne s'applique qu'aux distributions de probabilité vraies et non aux processus aléatoires en général. Pour des exemples concrets de processus qui ne correspondent pas aux hypothèses de l'entropie de Shannon, considérons ...

Processus de Markov

Un processus de Markov génère une série d'événements dans lesquels l'événement le plus récent est échantillonné à partir d'une distribution qui dépend d'un ou de plusieurs événements précédents. Il est évident qu'un grand nombre de phénomènes du monde réel sont mieux modélisés sous forme de processus de Markov que sous forme de distributions de probabilité discrètes et indépendantes. Par exemple: le texte que vous lisez en ce moment!

Le taux d'entropie de Shannon calculé naïvement d'un processus de Markov sera toujours supérieur ou égal au taux d'entropie réel du processus. Pour obtenir la véritable entropie du processus, vous devez prendre en compte la dépendance statistique entre les événements. Dans des cas simples, la formule qui ressemble à ceci :

H(S)=ipij pi(j)logpi(j)

Cela peut aussi être représenté comme suit :

H(Y)=ijμiPijlogPij

En citant à nouveau Wikipédia, voici " est la distribution asymptotique de la chaîne", c’est-à-dire la probabilité globale qu’un événement donné se produise sur un long horizon.μi

C'est une manière compliquée de dire que même lorsque vous pouvez calculer la probabilité globale d'un événement donné, certaines séquences d'événements sont plus susceptibles que d'autres d'être générées par un processus de Markov. Ainsi, par exemple, les trois chaînes de mots anglais suivantes sont de moins en moins probables:

  • Ils ont couru à l'arbre
  • L'arbre a couru à eux
  • Arbre qu'ils couraient

Mais l'entropie de Shannon évaluera les trois chaînes comme étant également probables. L'entropie du processus de Markov prend en compte la différence et attribue par conséquent un taux d'entropie inférieur au processus.

Les taux d'entropie dépendent du modèle

Si vous effectuez un zoom arrière, voici la vue d'ensemble: le taux d'entropie d'une séquence d'événements donnée provenant d'une source inconnue dépend du modèle. Vous affecterez un taux d'entropie différent à une série d'événements en fonction de la manière dont vous modélisez le processus qui les a générés.

Et très souvent, votre modèle de processus ne sera pas tout à fait correct. Ce n'est pas un problème simple ou facile à résoudre. En fait, en général, il est impossible d'attribuer un taux d'entropie véritable à une séquence d'événements suffisamment longue et complexe si vous ne connaissez pas le véritable processus sous-jacent. Ceci est un résultat central de la théorie algorithmique de l'information .

En pratique, cela signifie que, étant donné une source inconnue de séquences d'événements, différents modèles donneront différentes entropies, et il est impossible de savoir laquelle est correcte à long terme - bien que celui qui attribue la plus faible entropie soit probablement le meilleur.

senderle
la source
2
Merci beaucoup! Cela explique parfaitement quelle était l'erreur dans mon raisonnement.
robert
Votre réponse serait encore meilleure si elle utilisait des décompresseurs de données, d’images et audio comme exemples de processus modélisés. Par exemple, dans la compression de données LZ, le modèle suppose une machine (décodeur) prenant en entrée des commandes telles que (D, L): "copie dans la sortie L de symboles contigus à partir du décalage D par rapport à la position de sortie actuelle" ou copier le symbole c dans la position de sortie actuelle ». Le codeur LZ transforme son flux de symboles d'entrée en langage de commande du décodeur, et le flux de symboles de commande a une entropie (et une longueur) différente de celle du flux codé. D'autres types de compression ont des machines différentes.
piiperi
@ Piiperi, cela semble utile. Je ne connais cependant aucun de ces détails. (J'arrive à la question du point de vue de l'apprentissage automatique.)
Senderle
@senderle je voulais élargir le chapitre "Les taux d'entropie dépendent du modèle" avec des exemples de processus concrets. Vous parlez d'un processus qui génère des événements. Les composants de traitement des compresseurs de données, d'images, d'images, d'audio, etc. peuvent être vus comme tels. Un codeur d'entropie pur est la dernière étape d'un pipeline de compression de données. Aucune des étapes du pipeline ne réduit réellement "l'entropie". Au lieu de cela, chacun d'eux crée des instructions pour un ordinateur capable de reproduire le flux de symboles d'origine. Et chaque flux d'instructions a une entropie différente et souvent une longueur différente (c'est-à-dire plus courte).
piiperi
12

Non, si l'algorithme est sans perte, aucune étape de la séquence de compression ne peut réduire son entropie - sinon, il ne pourrait pas être décompressé / décodé. Cependant, l'entropie supplémentaire peut être stockée dans des informations "hors bande", telles que la liste à gérer pour décoder la transformation de type "move-to-front".

Luke Schwartzkopff
la source
Les étapes supplémentaires utilisées dans les algorithmes de compression avant le codage entropique sont-elles simplement utilisées pour permettre au codeur entropique de se rapprocher de l'entropie? Un codeur d'entropie ne se rapproche-t-il pas d'entropie lorsqu'il est appliqué à un message arbitraire?
robert
En effet, ce n’est pas le cas (enfin, cela dépend du sens exact de «proche»).
Grimmy
Les étapes supplémentaires permettent au codeur d'entropie de maintenir l'entropie du message d'origine tout en réduisant les informations superflues plus efficacement que si elles devaient être appliquées seules. Que vous appliquiez le pré-traitement ou non, l'entropie sera préservée, mais la compression sera moins efficace (vous obtiendrez un encodage moins efficace).
Luke Schwartzkopff le
Non, la transformation avec déplacement ne génère pas de liste séparée qui doit être transférée au décodeur. À moins que vous ne parliez de la liste initiale.
user253751
Aah, tu as raison, ce n'était pas le meilleur exemple :)
Luke Schwartzkopff
6

Ils réduisent l' entropie apparente inhérente à la structure du message d'origine. Autrement dit, ils adaptent le message pour tirer parti des atouts des prochaines étapes de la compression.

Un exemple simple serait de remplacer le nom dans les balises de fin de xml par un symbole spécial. Vous pouvez parfaitement recréer le fichier XML d'origine à partir de cela, mais le compresseur n'a pas à inclure le nom complet à nouveau à cet endroit.

Un exemple plus concret est la compression png. Son compresseur d'entropie est DEFLATE, une combinaison de Lempel-Ziff et Huffman. Cela signifie que cela fonctionne mieux avec des valeurs et des modèles qui se répètent souvent. La plupart des pixels adjacents ont tendance à être des couleurs similaires. Chaque ligne se voit donc attribuer un filtre qui convertit les valeurs de pixels d'origine en un codage différentiel. De cette façon, les valeurs qui finissent par être codées par DEFLATE sont généralement proches de 0. Dans le cas extrême, un dégradé régulier de toutes les valeurs différentes devient une valeur unique dans la ligne que la partie LZ ou DEFLATE permet de résoudre très rapidement.

monstre à cliquet
la source
Cela signifie-t-il que l'entropie apparente est différente du contenu informationnel réel d'un message? Comment cela est-il lié à l'entropie réelle du message?
robert
par "entropie apparente", je parle de l'entropie que l'encodage d'entropie peut compresser. Différents encodeurs auront différents modèles qu’ils recherchent. Huffman fait mieux lorsque les mêmes symboles sont souvent réutilisés, lempel-ziff réussit mieux lorsque des morceaux sont répétés, etc.
Freaket Freak
Mais les algorithmes de Lempel-Ziv ne sont pas des algorithmes de codage entropique, non? Ce que je ne comprends pas, c'est pourquoi ils sont utilisés avant les codeurs entropiques, par exemple dans LZMA, alors que le codeur entropique pouvait soi-disant déjà compresser le message au minimum.
robert
1
@kutschkem Est-ce que cela signifie que l'entropie n'est pas une mesure absolue du contenu de l'information d'un message, mais est relative à ce qui est défini comme un symbole (par exemple, un seul caractère est considéré comme un symbole et 1 bit est considéré comme un symbole)? Je pense que cela expliquerait où mes hypothèses étaient fausses.
robert
1
@robert ... Il y a cependant un compromis: il s'agit des informations "hors bande" que Luke mentionne dans sa réponse, qui sont généralement ajoutées par ces étapes (des tables de consultation pour pouvoir décoder les informations codées). Il n’a donc aucun sens de définir le contenu entier comme un seul symbole et de le coder comme 0 car il faut quelque part stocker les informations que ce 0 code.
kutschkem
6

Les codeurs entropiques ne compressent pas le message au nombre minimal de bits nécessaire pour le représenter. Je sais que c'est tentant de penser cela, mais ce n'est pas ce qu'ils font. Ils ne sont pas magiques et ils ne peuvent pas atteindre cet objectif.

Au lieu de cela, ils font quelque chose d'un peu moins magique - mais toujours utile. Supposons pour le moment que nous sachions que chaque caractère du message a été choisi indépendamment d'une distribution. Il serait alors possible de construire un algorithme de compression sans perte qui comprime les messages de manière optimale. Ces algorithmes sont appelés encodeurs entropiques.

Maintenant, les vrais messages n'ont généralement pas cette propriété d'indépendance. Par exemple, si vous voyez un Q, il est probable que la lettre suivante soit un U. Et ainsi de suite. Il est toujours possible d'appliquer un algorithme de codeur d'entropie à un message réel, où chaque caractère n'est pas choisi indépendamment du reste. L'algorithme sera toujours sans perte, il pourra toujours être utilisé pour la compression et, dans la pratique, il raccourcira souvent la longueur du message. Cependant, cela ne le raccourcit pas à la longueur minimale possible. Il ne compresse pas le message en quelque chose dont la longueur est égale à l'entropie du message; ça le compresse moins que ça.

Une fois que vous avez compris cette propriété des codeurs entropiques, le paradoxe s’évapore.

En général, aucune étape sans perte ne réduit jamais l'entropie du message. Toutefois, le message pourrait être présenté sous une forme où un autre algorithme de compression serait plus efficace. Il pourrait donc être utile (en moyenne) en pratique.

DW
la source
2

Le mot "Entropie" est souvent utilisé de manière un peu vague, pour faire référence à deux choses différentes:

  • La "quantité totale d'informations" dans un message ou un système

  • L'information "densité", ou à quel point l'information est emballée.

La citation d'OP de l'entrée de Wikipedia dans https://en.wikipedia.org/wiki/Entropy_(information_theory) fait référence à la première:

Shannon's entropy measures the information contained in a message

Mais (au moins quand j'écris ceci) le même article commence par:

Information entropy is the average rate at which information is produced by a stochastic source of data.

Donc, on est un montant et on est un taux (similaire à la distance par rapport à la vitesse). Celles-ci sont parfois appelées propriétés "extensives" et "intensives" (voir https://en.wikipedia.org/wiki/Intensive_and_extensive_properties#Extensive_properties ).

Un exemple classique de cette distinction est le fameux signal de lanterne de Paul Revere: "un si par terre et deux par mer". 1 bit d'information totale (si nous ignorons le cas "aucun si je ne suis pas encore arrivé à North Church"). Si Paul ajoutait un autre jeu de lanternes à chaque fenêtre du bâtiment, ce serait «redondant»: plus d'information, donc même entropie «totale» ou «étendue»; mais beaucoup plus de longueur de message, d'entropie "intensive" tellement inférieure.

S'il commence de cette façon, mais qu'il n'utilise plus qu'un seul jeu de lanternes, il s'agit d'une "compression sans perte", comme dans la question de OP. L'entropie "extensive" est la même, mais l'entropie "intensive" est différente: comme le nombre de lanternes dans la deuxième fenêtre est fortement corrélé à celui que vous avez vu dans la première, le message redondant est plus prévisible, ou moins aléatoire, a donc beaucoup moins d'entropie intensive.

Il y a deux autres choses importantes à retenir:

  • Premièrement, nous ne connaissons généralement pas la "vraie" entropie d'un système dans l'un ou l'autre sens. Un témoin naïf ne sait pas si "3 lanternes" serait un message différent ou si les signaux dans une fenêtre différente sont redondants ou non. Si Paul prend l'habitude de rouler, nous pouvons compter et voir si les fenêtres se correspondent toujours. Mais peut-être n’avons-nous tout simplement pas regardé assez longtemps pour voir les rares exceptions (et probablement les plus importantes!).

  • Deuxièmement, la façon dont vous mesurez est importante. Essayez d’essayer d’estimer la quantité communiquée par chaque lettre de texte successive (c’est un taux, donc une entropie "intensive", aussi parfois appelée "entropie relative"):

    • Si vous remarquez simplement que les gens envoient du texte par unités de 8 bits, votre première "estimation" peut être de 8 bits par lettre.
    • Si vous comptez le nombre de lettres distinctes utilisées, vous devriez estimer log2 (26), soit 4,7 bits par lettre (un peu plus élevé si vous considérez des espaces, des majuscules, etc.).
    • Si vous considérez que "e" est un meilleur pari pour "lettre suivante" que pour "z", vous mesurerez la fréquence des lettres et vous situerez autour de 4.14 (voir http://people.seas.harvard.edu/~jones/cscie129/ papers / stanford_info_paper / entropy_of_english_9.htm ).
    • Si vous comptez des paires de lettres, vous obtiendrez des motifs tels que "qu", "th", etc., et vous obtiendrez 3,56.
    • Si vous comptez des séquences d'environ 5 lettres au maximum, vous obtiendrez des valeurs encore plus basses et, en prime, vous pourrez distinguer de manière assez fiable le langage humain dans lequel le texte se trouve).
    • Si vous êtes aussi dur et intelligent que NG Burton et JCR Licklider dans "Contraintes à longue portée dans la structure statistique de l'anglais imprimé" (American Journal of Psychology 68 (1955)), vous pouvez obtenir jusqu'à 10 séquences. 0000 lettres dans une rangée et trouver encore une autre valeur d'entropie.

Mais bien sûr, les messages peuvent (et ont) de nombreux modèles qui ne sont pas modélisés par de telles méthodes à n-grammes, de sorte que la "vraie" entropie est encore plus basse.

Si vous modélisez une source infinie théorique avec une distribution Zipfian parfaitement aléatoire, vous pouvez calculer l'entropie extensive et intensive dont elle dispose, ce qui s'avère ne dépendre que du nombre de jetons distincts possibles. Les graphiques de chaque type d'entropie correspondant à l'augmentation de ce nombre se trouvent dans [ http://www.derose.net/steve/writings/dissertation/Diss.0.html] . Les deux se comportent très différemment:

J'espère que cela aide ou est au moins intéressant ...

TextGeek
la source
1

Je soupçonne que le libellé de Wikipedia allemand est erroné. Les compresseurs augmentent l'entropie. C'est-à-dire non pas l'entropie globale, mais l'entropie par bit : la densité d'informations. Par exemple, un codage de longueur et un schéma de dictionnaire sont appliqués pour condenser les données. Maintenant, la même information est compressée dans moins de bits, de sorte que chaque bit transporte plus d'informations. Le codage de Huffman ultérieur fait un peu plus de la même chose; c'est juste une autre couche de compression.

Kaz
la source