Comment fonctionne la compression de fichiers?

J'ai donc réalisé aujourd'hui que je tenais la compression de fichiers pour acquise. La possibilité de regrouper quelques fichiers en un seul, et de les faire sortir plus petits que n'importe lequel d'entre eux, est quelque chose que j'accepte comme un fait, mais comment cela fonctionne-t-il réellement?

J'ai une connaissance limitée de celui-ci qui comprend quelque chose à voir avec le remplacement de toutes les entrées en double par des pointeurs, pour rétrécir de cette façon, mais au-delà, je suis assez désemparé!

Comme je suis toujours ouvert à de nouvelles connaissances, comme j'imagine que la plupart d'entre nous sont ici, j'ai pensé demander. Ainsi, SuperUser, comment compression réellement fonctionne?

Compression sans perte

La compression sans perte est l'endroit où aucune donnée n'est perdue. Tout ce qui est entré peut être parfaitement récupéré. Cela fonctionne bien pour les fichiers texte ou binaires où la plus petite erreur sera remarquée.

La compression de fichiers fonctionne en prenant le fichier et en recherchant des modèles, et en traduisant ces modèles en quelque chose d'autre qui prend moins de place.

Par exemple, "AAAAAAAA" pourrait être transformé en "8A".

Certes, ce n'est pas comme cela que ça fonctionne exactement, car alors vous avez le problème si "8A" était dans le texte en clair. Vous décompressez le fichier et ce serait faux. Un bon point de départ est Wikipedia ou l' algorithme de compression de données LZW .

Il y a simplement un code pseudo pour cela copié ci-dessous:

STRING = get input character
WHILE there are still input characters DO
    CHARACTER = get input character
    IF STRING+CHARACTER is in the string table then
        STRING = STRING+character
    ELSE
        output the code for STRING
        add STRING+CHARACTER to the string table
        STRING = CHARACTER
    END of IF
END of WHILE
output the code for STRING

Toute compression utilise un dictionnaire de recherche qui est utilisé pour compresser et décompresser le fichier. Plus le dictionnaire est gros, plus vous pouvez le compresser, bien que vous tombiez sur la loi des rendements décroissants .

Il convient également de noter que la compression ne produit pas toujours un fichier plus petit. Dans certaines situations (avec de petits fichiers ou lors de la compression de données aléatoires ), vous n'obtiendrez pas un fichier plus petit après la compression. Il y a eu quelques défis amusants concernant la capacité de compresser des données aléatoires.

"La compression avec perte

Ce qui précède concerne principalement la compression sans perte . D'autres types de compression utilisés dans les applications vidéo / audio telles que MP3, JPG et h.264 sont des exemples de compression avec perte .

La compression avec perte fonctionne en supprimant les données les moins susceptibles d'être remarquées. En audio, cela représente environ 30 000 Hrz et moins de 100 Hrz, ainsi que diverses autres choses. Dans l'image (statique), il supprime diverses choses et fusionne les pixels, ainsi que la suppression des données.

La compression avec perte est une forme de codage par transformation . Il fait la moyenne des données pour réduire la taille globale. Par exemple, un bloc de 10 pixels dans une image, toutes les couleurs légèrement différentes peuvent être fusionnées en une seule couleur et ainsi compressées.

Dans la compression vidéo, des instructions seront souvent placées pour ne redessiner que les pixels qui ont changé depuis la dernière image ou image clé .

La compression fonctionne en trouvant des modèles dans les données, puis en remplaçant ces modèles par des modèles spéciaux plus petits. La décompression est l'inverse: trouvez les modèles spéciaux et remplacez-les par les modèles plus grands qu'ils représentent. Il est important de savoir quels modèles sont probables; par exemple, les motifs trouvés dans le texte peuvent être très différents de ceux trouvés dans les images. Certaines techniques de compression sont avec perte; ils ne garantissent pas que l'extension récupérera exactement l'entrée. Cela convient généralement aux données analogiques, telles que la musique et les images, si la perte est suffisamment faible. Mais les données telles que le texte doivent être compressées avec des techniques sans perte.

Il est important de réaliser qu'il est impossible de compresser, sans perte, des données aléatoires ne serait-ce que d'un seul bit. Considérons un fichier avec N bits de données binaires. Il y a 2 ^ N fichiers possibles. Si vous compressez l'un de ces fichiers par un seul bit, de sorte que le fichier compressé ait une taille de N-1 bits, il n'y a que 2 ^ (N-1) représentations compressées possibles. En d'autres termes, chaque fichier compressé possible doit représenter plus d'un fichier non compressé possible. Sans représentation compressée unique, l'algorithme de décompression ne peut garantir une décompression sans perte.