Question Pourquoi la compression d'un fichier compressé ne réduit-elle pas sa taille?


Sur la base de l'idée qu'un fichier compressé est un nouveau fichier binaire, pourquoi ne puis-je pas réduire la taille d'un fichier Zip en le refermant encore et encore - jusqu'à un très petit fichier résultant?


4
2018-01-06 19:40


origine


En relation: Puis-je compresser à nouveau un fichier RAR pour réduire sa taille? - slhck


Réponses:


Sur la base de l’idée qu’un fichier compressé est un nouveau fichier binaire, pourquoi ne puis-je pas réduire sa taille en la refermant et en l’amenant successivement à un très petit fichier?

Parce que la compression fonctionne sur la base de la recherche de modèles et de la réduction des données similaires.

Par exemple, RLE (Run-length Encoding) est une méthode de compression simple où les données sont examinées et les exécutions de données similaires compressées comme suit:

AAABCEEEJFFYYYYYYYYYYOOAAAAGGGGGAAA

becomes

3ABC3EJ2F10YOO4A5G3A

Comme vous pouvez le constater, en remplaçant des données répétées par les seules données et en comptant le nombre de fois où elles se produisent, vous pouvez réduire cet exemple spécifique de 35 à 20 octets. Ce n'est pas un énorme réduction, mais il est encore 42% plus petit. De plus, il s’agit d’un petit exemple artificiel; des exemples plus grands et réels pourraient avoir une compression encore meilleure. (Le OO a été laissé seul parce que le remplacer par 2O ne sauverait rien.)

Les fichiers texte se compressent souvent très bien car ils ont tendance à être compressés. Par exemple, le mot la est très commun en anglais, vous pouvez donc supprimer chaque instance du mot avec un identifiant qui est juste un seul octet (ou même moins). Vous pouvez également compresser plus avec les pièces des mots qui sont similaires comme cAKE, bAKE, shAKE, undertAKE, etc.

Alors, pourquoi ne pas compresser un fichier qui est déjà compressé? Parce que quand vous avez fait la compression initiale, vous enlevé les motifs.

Regardez l'exemple RLE compressé. Comment pouvez-vous compresser cela plus loin? Il n'y a aucune exécution de données identiques à compresser. En fait, souvent, lorsque vous essayez de compresser un fichier qui est déjà compressé, vous pouvez vous retrouver avec un plus grand fichier. Par exemple, si vous avez forcé le recodage de l'exemple ci-dessus, vous pourriez vous retrouver avec quelque chose comme ceci:

131A1B1C131E1J121F11101Y2O141A151G131A

Maintenant, les données de compression (le nombre d'exécutions) sont elles-mêmes traitées comme des données, vous vous retrouvez donc avec un fichier plus volumineux que celui avec lequel vous avez commencé.

Ce que vous pourrait try est d'utiliser un algorithme de compression différent, car il est possible que la sortie d'un algorithme de compression soit probablement primordiale pour un algorithme différent, mais cela est généralement peu probable.

Bien sûr, tout est question de compression sans perte où les données décompressées doivent être exactement identiques aux données d'origine. Avec la compression avec perte, vous pouvez généralement supprimer plus de données, mais la qualité diminue. En outre, la compression avec perte utilise généralement une sorte de schéma basé sur des modèles (cela ne seulement éliminer les données), vous finirez donc par atteindre un point où il n’ya tout simplement aucun motif à trouver.


7
2018-01-06 20:01





Si tous les fichiers compressés après la compression réduisent à nouveau leur taille (ou si leur taille n'est pas supérieure à celle de leur parent), la taille deviendra nulle à un moment donné, ce qui ne peut être vrai. Si cela est vrai, nous n'avons presque pas besoin de stockage de fichiers.

Algorithmes de compression de données sans perte ne peut pas garantir la compression pour tous les ensembles de données d'entrée. En d’autres termes, pour tout algorithme de compression de données sans perte, il y aura un ensemble de données en entrée qui ne sera pas réduit lorsqu’il sera traité par l’algorithme et pour tout algorithme de compression sans perte qui aura au moins un fichier. fichier qu'il agrandit. Ceci est facilement prouvé avec les mathématiques élémentaires en utilisant un argument de comptage, comme suit:

  • Supposons que chaque fichier est représenté par une chaîne de bits de longueur quelconque.
  • Supposons qu'il existe un algorithme de compression qui transforme chaque fichier en un fichier de sortie qui ne dépasse pas le fichier d'origine, et qu'au moins un fichier sera compressé dans un fichier de sortie plus court que le fichier d'origine.
  • Soit M le plus petit nombre tel qu'il y ait un fichier F de longueur M bits qui comprime quelque chose de plus court. Soit N la longueur (en bits) de la version compressée de F.
  • Parce que N <M, chaque fichier de longueur N conserve sa taille pendant la compression. Il ya deuxN ces fichiers. Avec F, cela fait 2N+1 fichiers compressés dans l'un des 2N fichiers de longueur N.
  • Mais 2N est plus petit que 2N+1, donc par le principe du pigeonnier, il doit y avoir un fichier de longueur N qui est simultanément la sortie de la fonction de compression sur deux entrées différentes. Ce fichier ne peut pas être décompressé de manière fiable (lequel des deux originaux doit donner?), Ce qui contredit l’hypothèse selon laquelle l’algorithme était sans perte.
  • Nous devons donc conclure que notre hypothèse initiale (que la fonction de compression ne rend plus de fichier plus longue) est nécessairement fausse.

https://en.wikipedia.org/wiki/Lossless_compression#Limitations


2
2018-06-24 16:00





Un fichier qui a été compressé de manière optimale ne comportera aucun motif ou tout ce qui peut être réduit.

Imaginons un fichier simple contenant ceci.

AAAAAAAAAAAAAAAAAAAA
BBBBBBBBBBBBBBBBBBBB
CCCCCCCCCCCCCCCCCCCC

Si on le compresse on pourrait dire que c'est 20 A, newline, suivi de 20 B, newline, suivi de 20 C. Ou quelque chose comme 20xA\n20xB\n20xC\n. Une fois la première compression terminée, il n'y a plus de nouveau modèle à compresser. Chaque fois que l'information est unique.


1
2018-01-06 20:00





Je dirais que vous ne pouvez pas compresser arbitraire fichiers binaires dans une large mesure - pensez à des images JPEG, x264 vidéos et ainsi de suite. Surtout que tu veux reconstruire votre fichier d'origine exactement (c'est-à-dire bit par bit) vous avez besoin d'un compression sans perte.1

La raison de cette compression limitée est indiquée dans ce document. Article de Wikipedia sur Entropy  qui quantifie la valeur attendue de l'information contenue dans un message:

L'entropie limite efficacement les performances du plus fort sans perte.   (ou presque sans perte) compression possible, qui peut être réalisée en   la théorie en utilisant l'ensemble typique ou en pratique en utilisant Huffman,   Lempel-Ziv ou codage arithmétique. (...)


1La très forte «compression» des images JPEG n’est possible que parce que certaines informations sont ignorées (de manière à ce que l’œil humain ne puisse pas les reconnaître au premier coup d’œil; la compression avec perte).


1
2018-01-06 20:00



I'd say can't compress any binary file Ce n'est pas vrai, vous pouvez généralement compresser un peu les exectuables, donc UPX. - Synetech
@ Synetech: Vous avez absolument raison, c'était un piège de la langue. Je ne voulais pas tout, mais arbitre fichier (au sens de données aléatoires). - mpy
Ah bon, je vois. Oui, un fichier contenant des octets aléatoires est tout simplement terrible pour la compression. - Synetech