Relation de Entropy à Lossless Taux de compression

Question

De théorème de codage de Shannon Source nous savons que l'entropie d'une chaîne compressée est délimitée par l'entropie de la chaîne d'origine comme ceci:

H(X) <= L < H(X) + 1/N 

où H (X) est l'entropie de la chaîne de source, N est la longueur de la chaîne de source, et L est la longueur attendue de la chaîne compressée.

Cela signifie nécessairement qu'il ya une limite à la compression sans perte.

Ce que je voudrais savoir est:

• Peut-on relier directement l'entropie à un certain taux de compression attendu?

• Peut-on utiliser l'entropie pour trouver une limite supérieure pour le taux de compression?

Answer 1

Vous ne pouvez pas relier directement l'entropie à taux de compression sans connaître la longueur de la chaîne source, mais vous pouvez voir la limite théorique au taux de compression maximal en résolvant la plus petite valeur possible de L. Vous pouvez utiliser cette limite comme une mesure d'efficacité de vos algorithmes de compression, même si une mauvaise mesure ne signifie pas qu'un meilleur algorithme a été découvert ou existe.

Alors, oui. Vous pouvez utiliser l'entropie pour trouver le taux de compression sans perte maximum théorique, mais non, vous ne pouvez pas l'utiliser pour déterminer votre taux de compression prévu pour tout algorithme de compression donné.

Answer 2

Le théorème de Shannon est définie en termes de données aléatoires et des probabilités. De même, le entropie d'une chaîne est uniquement définie pour les chaînes aléatoires - l'entropie est une propriété de la distribution, et non des chaînes elles-mêmes. Ainsi, nous pouvons reformuler le théorème de Shannon officieusement:

  

Si vous sélectionnez au hasard une chaîne à partir d'une distribution de probabilité donnée, le meilleur taux de compression moyen que nous pouvons obtenir pour la chaîne est donnée par le taux d'entropie de la distribution de probabilité.

Étant donné une chaîne aléatoire, je peux facilement écrire un algorithme de compression qui compresse cette chaîne vers le bas dans 1 bit, mais mon algorithme nécessairement augmenter la longueur de quelques autres cordes. Mon algorithme de compression fonctionne comme suit:

1. Si la chaîne d'entrée est égale à une chaîne aléatoire pré-choisie , la sortie est le "0" string 1 bit
2. Dans le cas contraire, la sortie est la N + 1 bits chaîne de « 1 » suivi de la chaîne d'entrée

L'algorithme de décompression correspondant est:

1. Si l'entrée est "0", la sortie est notre précédente chaîne aléatoire pré-choisie
2. Dans le cas contraire, la sortie est tout, sauf pour le premier bit d'entrée

La clé ici est que nous ne pouvons pas écrire un algorithme qui, pour toutes les chaînes d'une distribution donnée, les compresse tous à un taux élevé en moyenne. Il y a juste trop de chaînes.

Si nous avons une distribution de probabilité de chaînes, on peut calculer le taux d'entropie de la distribution, puis se choisir au hasard une chaîne selon la répartition et tenter de le compresser en utilisant tout algorithme , la taille relative de la chaîne compressée sera, en moyenne, jamais inférieur au taux d'entropie. Voici ce que dit le théorème de Shannon.

Answer 3

Oui. Taux d'entropie de la langue anglaise est souvent citée comme 1,5 bits par caractère (donner ou prendre). codages classiques utilisent 8 bits par caractère. Ainsi, un texte au maximum comprimé doit être de 1,5 / 8 (~ 19%) la taille de l'original. Les résultats réels pour une version texte de la fierté de Jane Austin et Préjugés. orig = 701K, bzip2 = 178K, pour ~ 25%

Answer 4

Oui! Je pense que cet article pourrait vous orienter dans la bonne direction.

ETA On dirait que vous devez être membre de l'IEEE pour lire le journal réelle. Si quelqu'un pouvait trouver une ressource accessible au public (ou expliquer les mathématiques ici), ce serait beaucoup mieux bien sûr!