Combien de fois un fichier peut-il être compressé ?

Question

J'ai pensé à la compression, et il semble qu'il devrait y avoir une sorte de limite à la compression qui pourrait être appliquée, sinon ce serait un seul octet.

Ma question est donc la suivante : combien de fois puis-je compresser un fichier avant.. :

• Il n'y a pas plus petit ?
• Le fichier est corrompu ?

Ces deux points sont-ils identiques ou différents ?

Où apparaît le point de rendement décroissant ?

Comment trouver ces points ?

Je ne parle pas d'un algorithme spécifique ou d'un fichier particulier, juste en général.

Answer 1

Pour la compression sans perte, la seule façon de savoir combien de fois vous pouvez gagner en recompressant un fichier est d'essayer. Cela va dépendre de l'algorithme de compression et du fichier que vous comprimez.

Deux fichiers ne peuvent jamais être compressés à la même sortie, donc vous ne pouvez pas descendre à un octet. Comment un octet pourrait-il représenter tous les fichiers vers lesquels vous pourriez décompresser ?

La raison pour laquelle la deuxième compression fonctionne parfois est qu'un algorithme de compression ne peut pas effectuer une compression parfaite omnisciente. Il y a un compromis entre le travail qu'il doit faire et le temps qu'il prend pour le faire. Votre fichier est en train de passer de toutes les données à une combinaison de données sur vos données et des données elles-mêmes.

Exemple

Prenons l'exemple du codage en longueur (probablement la compression utile la plus simple).

04 04 04 04 43 43 43 43 51 52 11 octets

Cette série d'octets pourrait être comprimée comme suit :

[4] 04 [4] 43 [-2] 51 52 7 octets (je mets les méta-données entre parenthèses)

Où le nombre positif entre parenthèses est un compte de répétition et le nombre négatif entre parenthèses est une commande pour émettre les caractères -n suivants au fur et à mesure qu'ils sont trouvés.

Dans ce cas, nous pouvons essayer une autre compression :

[3] 04 [-4] 43 fe 51 52 7 octets (fe est votre -2 vu comme données de complément à deux)

Nous n'avons rien gagné, et nous allons commencer à grandir à la prochaine itération :

[-7] 03 04 fc 43 fe 51 52 8 octets

La croissance sera d'un octet par itération pendant un certain temps, mais elle sera en fait pire. Un octet ne peut contenir que des nombres négatifs jusqu'à -128. Nous commencerons à croître de deux octets lorsque le fichier dépassera 128 octets de longueur. La croissance va encore s'aggraver au fur et à mesure que le fichier s'agrandit.

Il y a un vent contraire qui souffle sur le programme de compression : les métadonnées. Et aussi, pour réel les compresseurs, l'en-tête étant collé au début du fichier. Cela signifie qu'à terme, le fichier commencera à grossir à chaque compression supplémentaire.

---

La RLE est un point de départ. Si vous voulez en savoir plus, consultez LZ77 (qui retourne dans le fichier pour trouver des motifs) et LZ78 (qui construit un dictionnaire). Les compresseurs comme zip essaient souvent plusieurs algorithmes et utilisent le meilleur.

Voici quelques cas auxquels je pense où la compression multiple a fonctionné.

1. J'ai travaillé pour un magazine Amiga qui était livré avec un disque. Naturellement, nous avons emballé le disque jusqu'au bout. L'un des outils que nous utilisions nous permettait d'empaqueter un exécutable de telle sorte que lorsqu'il était exécuté, il se décompressait et s'exécutait tout seul. Comme l'algorithme de décompression devait se trouver dans chaque exécutable, il devait être petit et simple. Nous obtenions souvent des gains supplémentaires en compressant deux fois. La décompression était effectuée en RAM. Comme la lecture d'une disquette était lente, nous obtenions souvent un gain de vitesse supplémentaire !
2. Microsoft supportait la compression RLE sur les fichiers bmp. De même, de nombreux traitements de texte effectuent le codage RLE. Les fichiers RLE sont presque toujours compressibles de manière significative par un meilleur compresseur.
3. Beaucoup de jeux sur lesquels j'ai travaillé utilisaient un petit décompresseur LZ77 rapide. Si vous comprimez un grand rectangle de pixels (surtout s'il a beaucoup de couleur de fond, ou s'il s'agit d'une animation), vous pouvez très souvent le comprimer deux fois avec de bons résultats. (La raison ? Vous n'avez qu'un nombre limité de bits pour spécifier la distance de retour et la longueur, donc un seul grand motif répété est codé en plusieurs morceaux, et ces morceaux sont hautement compressibles).

Answer 2

En général, la limite est d'une compression. Certains algorithmes permettent d'obtenir un taux de compression plus élevé, et l'utilisation d'un mauvais algorithme suivi d'un bon algorithme entraînera souvent des améliorations. Mais utiliser le bon algorithme en premier lieu est la chose à faire.

Il existe une limite théorique à la compression d'un ensemble donné de données. Pour en savoir plus à ce sujet, vous devrez étudier théorie de l'information .

Answer 3

En général, pour la plupart des algorithmes, il n'est pas utile de compresser plus d'une fois. Il y a cependant un cas particulier.

Si vous avez un grand nombre de fichiers en double, le format zip va les zipper indépendamment les uns des autres, et vous pouvez ensuite zipper le premier fichier zip pour supprimer les informations zip en double. Plus précisément, pour 7 fichiers Excel identiques d'une taille de 108 Ko, la compression avec 7-zip donne une archive de 120 Ko. Un nouveau zippage permet d'obtenir une archive de 18 Ko. Au-delà, on obtient des rendements décroissants.

Answer 4

Supposons que nous avons un fichier de N bits de long, et que nous voulons le compresser sans perte, de sorte que nous puissions récupérer le fichier original. Il existe 2^N fichiers possibles de N bits de long, et notre algorithme de compression doit donc transformer l'un de ces fichiers en l'un des 2^N autres possibles. Cependant, nous ne pouvons pas exprimer 2^N fichiers différents en moins de N bits.

Par conséquent, si nous pouvons prendre certains fichiers et les compresser, nous devons avoir certains fichiers qui s'allongent sous la compression, pour équilibrer ceux qui raccourcissent.

Cela signifie qu'un algorithme de compression ne peut comprimer que certains fichiers, et qu'il doit en fait en allonger certains. Cela signifie qu'en moyenne, la compression d'un fichier aléatoire ne peut pas le raccourcir, mais peut l'allonger.

Les algorithmes de compression pratiques fonctionnent parce que nous n'utilisons généralement pas de fichiers aléatoires. La plupart des fichiers que nous utilisons ont une certaine structure ou d'autres propriétés, qu'il s'agisse de texte, d'exécutables de programmes ou d'images significatives. En utilisant un bon algorithme de compression, nous pouvons raccourcir considérablement les fichiers des types que nous utilisons normalement.

Cependant, le fichier compressé n'est pas l'un de ces types. Si l'algorithme de compression est bon, la plupart des structures et des redondances ont été éliminées, et ce qui reste ressemble beaucoup à du hasard.

Aucun algorithme de compression, comme nous l'avons vu, ne peut compresser efficacement un fichier aléatoire, et cela s'applique également à un fichier d'apparence aléatoire. Par conséquent, essayer de recompresser un fichier compressé ne le raccourcira pas de manière significative, et pourrait même l'allonger un peu.

Ainsi, le nombre normal de fois qu'un algorithme de compression peut être exécuté avec profit est de un.

La corruption ne se produit que lorsque nous parlons de compression avec perte. Par exemple, vous ne pouvez pas nécessairement récupérer une image avec précision à partir d'un fichier JPEG. Cela signifie qu'un compresseur JPEG peut raccourcir de manière fiable un fichier image, mais uniquement au prix de l'impossibilité de le récupérer exactement. Nous sommes souvent prêts à faire cela pour les images, mais pas pour le texte, et surtout pas pour les fichiers exécutables.

Dans ce cas, il n'y a pas d'étape à laquelle la corruption commence. Elle commence lorsque vous commencez à la compresser, et s'aggrave au fur et à mesure que vous la compressez. C'est pourquoi les bons programmes de traitement d'images vous permettent de spécifier le niveau de compression souhaité lorsque vous créez un JPEG : vous pouvez ainsi équilibrer la qualité de l'image et la taille du fichier. Vous trouvez le point d'arrêt en considérant le coût de la taille du fichier (qui est plus important pour les connexions Internet que pour le stockage, en général) par rapport au coût de la réduction de la qualité. Il n'y a pas de bonne réponse évidente.

Answer 5

En général, une seule compression suffit si l'algorithme est bon.
_{En fait, compresser plusieurs fois pourrait conduire à une augmentation de la taille}

Vos deux points sont différents.

• Compression effectuée à plusieurs reprises et réalisation aucune amélioration de la réduction de la taille
  est une condition théorique attendue
• Compression répétée causant la corruption
  est probablement une erreur dans l'implémentation (ou peut-être l'algorithme lui-même).

Examinons maintenant quelques exceptions ou variations,

• Cryptage peut être appliqué de manière répétée sans réduction de taille
  (en fait, il arrive que la taille augmente) dans le but de renforcer la sécurité
• Fichiers image, vidéo ou audio de plus en plus compressé
  perdront des données (être effectivement "corrompu" dans un sens)