Algorithmes de compression de données sans perte. Principes de compression des informations Types de compression graphique, vidéo et audio

Des dizaines d'archiveurs sont populaires sur Internet aujourd'hui, et dans la description de chaque programme, vous pouvez constater que son algorithme est le meilleur... J'ai décidé de prendre plusieurs archiveurs populaires sur Internet, à savoir : WinRar, WinUha, WinZip, KGB archiver, 7Z et testez-les en conditions de « combat » ».

Une petite préface... La comparaison n’est peut-être pas très objective. La comparaison des avivateurs a été effectuée sur l'ordinateur domestique le plus courant, la moyenne d'aujourd'hui. De plus, différents types de données n'ont pas été pris en compte : la comparaison de compression a été effectuée sur un document « Word » classique, dont beaucoup de ceux qui étudient ou travaillent avec eux peuvent accumuler une quantité énorme. Eh bien, il est logique qu'il soit conseillé de regrouper les informations que vous utilisez rarement dans une archive et parfois de les extraire. Et il est beaucoup plus facile de transférer un tel fichier : il sera copié sur une clé USB plus rapidement qu'un tas de petits fichiers, et il sera téléchargé plus rapidement sur Internet...

Tableau comparatif des compressions

Pour une petite expérience, un fichier RTF relativement volumineux a été récupéré - environ 3,5 Mo et compressé avec différents archiveurs. Nous ne prenons pas encore en compte le temps de fonctionnement, les fonctionnalités des programmes seront discutées plus en détail, mais nous allons maintenant nous contenter du niveau de compression.

Programme	Format	Ratio de compression	Taille, Ko	Combien de fois la taille du fichier a-t-elle diminué ? ?
Archiveur du KGB 2	.kgb	maximum	141411	22,99
WinRar	.rar	maximum	190546	17,07
WinUha	.uha	maximum	214294	15,17
7Z	.7z	maximum	218511	14,88
WinZip	.fermeture éclair	maximum	299108	10,87
Fichier original	.rtf	Sans compression	3252107	1

Comme le montre la petite plaque, le taux de compression le plus élevé est obtenu avec le programme KGB Archiver 2 - la taille du fichier d'origine a diminué de 23 fois ! Ceux. si vous avez plusieurs gigaoctets de documentation diverses sur votre disque dur que vous n'utilisez pas et que vous souhaitez supprimer (mais vous ne pouvez pas vous débarrasser du sentiment que cela pourrait être utile) - ne serait-il pas plus facile de le compresser avec un tel un programme et écrivez-le sur le disque...

Mais à propos de tous les pièges dans l'ordre...

Archiveur du KGB 2

En général, ce n'est pas un mauvais archiveur ; selon les développeurs, leur algorithme de compression est l'un des « plus puissants ». Il est difficile d'être en désaccord...

Seule la vitesse de compression laisse à désirer. Par exemple, le fichier de l'exemple (environ 3 Mo) a été compressé par le programme pendant environ 3 minutes ! Il n’est pas difficile d’estimer qu’elle compressera un disque CD pendant une demi-journée, voire plus.

Mais ce n’est pas particulièrement surprenant. Décompresser un fichier prend autant de temps que le compresser ! Ceux. Si vous avez passé une demi-journée à compresser certains de vos documents, vous passerez le même temps à les sortir des archives.

Résultat: le programme peut être utilisé pour de petites quantités d'informations, en particulier lorsque la taille minimale du fichier source est importante (par exemple, le fichier doit être placé sur une disquette ou sur un petit lecteur flash). Mais encore une fois, il est impossible de deviner à l'avance la taille du fichier compressé, et vous risquez de perdre du temps en compression...

WinRar

Le célèbre programme de l'espace post-soviétique est installé sur la plupart des ordinateurs. Probablement, si elle n'avait pas montré d'aussi bons résultats, elle n'aurait pas eu autant de fans. Ci-dessous une capture d'écran montrant les paramètres de compression, rien de spécial, sauf que le niveau de compression a été réglé au maximum.

Étonnamment, WinRar a compressé le fichier en quelques secondes et sa taille a été réduite de 17 fois. un résultat très intéressant, étant donné que le temps consacré au traitement est négligeable. Et le temps de décompression du fichier est encore moindre !

Résultat: Un excellent programme qui montre certains des meilleurs résultats. Lors des paramètres de compression, vous pouvez également spécifier la taille maximale de l'archive et le programme la divisera en plusieurs parties. C'est très pratique pour transférer un fichier d'un ordinateur à un autre sur une clé USB ou un disque CD/DVD, lorsque vous ne pouvez pas écrire l'intégralité du fichier sur...

WinUha

Un archiviste relativement jeune. On ne peut pas le qualifier de très populaire, mais de nombreux utilisateurs qui travaillent souvent avec des archives s'y intéressent. Et ce n’est pas un hasard, car selon les développeurs de l’archiveur, son algorithme de compression est plus puissant que celui de RAR et 7Z.

Dans notre petite expérience, je ne dirais pas qu'il en est ainsi. Il est possible que sur d'autres données, les résultats soient bien meilleurs...

À propos, lors de l'installation, sélectionnez l'anglais ; en russe, le programme affiche « cryakozabry ».

Résultat: un bon programme avec un algorithme de compression intéressant. Le temps de traitement et de création d'une archive est bien sûr plus long que celui de WinRar, mais pour certains types de données, vous pouvez obtenir un taux de compression légèrement plus élevé. Même si, personnellement, je n’insisterais pas beaucoup sur ce point…

7Z

Un archiveur gratuit très populaire. Beaucoup soutiennent que le taux de compression dans 7z est encore meilleur que dans WinRar. C'est tout à fait possible, mais lorsqu'il est compressé avec le niveau « Ultra » sur la plupart des fichiers, il perd face à WinRar.

Résultat: une bonne alternative à WinRar. Taux de compression tout à fait comparable, bonne prise en charge de la langue russe, intégration pratique dans le menu contextuel de l'Explorateur.

WinZip

Légendaire, l'un des archiveurs les plus populaires de tous les temps. Sur Internet, les archives les plus courantes sont probablement « ZIP ». Et ce n'est pas un hasard : malgré le taux de compression pas si élevé, la vitesse de fonctionnement est tout simplement incroyable. Par exemple, Windows ouvre ces archives sous forme de dossiers normaux !

De plus, il ne faut pas oublier que ce format d'archiveur et de compression est bien plus ancien que ses nouveaux concurrents. Et tout le monde ne dispose pas désormais d'ordinateurs puissants qui leur permettront de travailler rapidement avec de nouveaux formats. Et le format Zip est supporté par tous les archiveurs modernes !

La plupart des utilisateurs savent que la compression est parfois utilisée pour réduire la taille des fichiers source afin de les rendre plus pratiques à stocker ou à envoyer, par exemple par courrier électronique. Cependant, pour une raison quelconque, dans ce cas, l'association se produit uniquement avec les applications d'archivage et les autres techniques de compression de données ne sont pas prises en compte. Nous examinerons ensuite ce qui détermine le degré de compression des fichiers, en utilisant l'exemple de plusieurs des situations les plus courantes.

Qu’entend-on par taux de compression de fichier ?

Commençons par des questions théoriques. Quel est le taux de compression d'un fichier ? Basé sur les interprétations les plus simples de ce terme, cela signifie le rapport entre la taille de l'objet final (compressé) et le volume initial. Cependant, une telle explication peut s'appliquer en grande partie exclusivement aux données d'archives, puisqu'elle ne répond pas du tout à certains problèmes liés au changement de format multimédia, où la compression est également très courante. En général, on ne peut pas dire que le degré de compression des fichiers dépend uniquement d'une caractéristique particulière. Dans ce cas, le type d'objet, les programmes utilisés pour compresser les données et la vitesse du processus de compression jouent un rôle. Ensuite, nous discuterons brièvement de certains aspects importants qui peuvent affecter le résultat final de la réduction de la taille des données sources.

Le degré de compression des fichiers dépend uniquement du type de fichier : est-ce vraiment vrai ?

Oui, en effet, le type de données compressées a un impact assez important sur la réduction de la taille finale du fichier, et tous les formats ne peuvent pas être soumis à de telles procédures. Cela peut être expliqué à l'aide de l'exemple de fichiers audio, qui sont initialement déjà compressés en eux-mêmes.

Lorsqu’on essaie de regrouper de telles données dans une archive, il est presque impossible d’obtenir une réduction significative de leur taille. Il en va de même pour le format WAV. Cependant, si vous ne compressez pas, mais transcodez de WAV en MP3, la taille peut être réduite d'un facteur dix ou plus. De nombreux utilisateurs sont immédiatement rebutés par le fait que le degré de compression des fichiers dépend du format initial et final. Ce n'est pas tout à fait vrai, car l'algorithme de recodage utilisé joue également un rôle important, qui sera discuté séparément. Pour l'instant, concentrons-nous sur l'utilisation des archiveurs.

Qu'est-ce qui détermine le degré de compression des fichiers lors de leur intégration dans une archive ?

Pour comprendre dans un premier temps l'essence de ce type de compression, pour faciliter l'explication, nous utiliserons comme exemple l'archiveur WinRAR le plus courant. Nous n'aborderons pas les types de données compressées, mais nous concentrerons sur les outils de l'application elle-même.

Pour commencer, vous devez faire attention au format final de l'archive, ainsi qu'à la méthode de packaging utilisée. Il est clair que dans ce cas, le degré de compression des fichiers par le programme d'archivage dépend de la technique privilégiée. Avec la méthode à grande vitesse, la compression sera minime, mais avec le taux de compression maximum, la taille sera réduite de manière plus significative et plus de temps sera nécessaire.

Si l'on considère les formats de fichiers par rapport aux archiveurs, les documents texte de n'importe quel format peuvent être distingués des plus compressibles.

Certains fichiers exécutables au format EXE sont relativement bien compressés (en utilisant la méthode de compression standard, vous pouvez réduire la taille de plus de moitié). Les plus incompressibles, comme déjà mentionné, sont les objets multimédias. Et, bien qu'il soit au moins possible de réduire la taille des images, de telles actions ne fonctionnent pas avec l'audio et la vidéo sans modifier le format initial, et les archiveurs n'y sont absolument pour rien.

Types de compression graphique, vidéo et audio

En matière de multimédia, il existe deux principaux types de compression : avec et sans perte. Et dans ce cas, le degré de compression des fichiers dépend précisément de la technologie de compression utilisée.

Dans le premier cas, la compression est maximale, dans le second elle peut varier, ce qui est influencé par l'ensemble des codecs utilisés et le format final du conteneur. Ainsi, par exemple, le même fichier AVI peut être un conteneur contenant des types de données complètement différents et avec différents degrés de compression. Pour cette raison, des problèmes de lecture vidéo sur les lecteurs domestiques peuvent parfois survenir.

En général, si nous parlons spécifiquement de multimédia, vous devez ici clairement comprendre qu'il est presque impossible d'obtenir la réduction maximale de la taille du fichier source de n'importe quel format sans perte significative de qualité, malgré les technologies de suppression du contenu redondant (par exemple exemple, pour le graphisme ou la vidéo cela ne fonctionne que dans le cas de scènes non modifiables). Dans le cas de l'audio, le débit est réduit et certaines fréquences sont supprimées. L’utilisateur moyen ne sentira peut-être pas la différence, mais un professionnel à l’oreille attentive dira immédiatement ce qui manque.

Les programmes les plus courants pour toutes les occasions

Voyons un peu de quoi dépend le degré de compression des fichiers. Il convient maintenant de dire quelques mots sur les logiciels utilisés. Parmi les archiveurs, les plus courants sont WinRAR, WinZIP et 7-Zip.

Quant à la compression multimédia, dans le cas le plus simple, vous pouvez utiliser des applications de conversion spéciales qui fonctionnent sur le principe du transcodage du matériel source dans un autre format afin de réduire la taille du fichier.

Bref résumé

En résumé, on peut noter que le degré de compression des fichiers par l'archiveur dépend de plusieurs facteurs, et le plus souvent du type de données compressées, du logiciel utilisé et (généralement les algorithmes de Huffman et Lempel-Ziv, travaillant en binôme, sont utilisés). Dans le cas des contenus multimédias, la situation est quasiment la même, mais la position dominante est occupée par la conversion de format de l'un à l'autre.

ARCHIVERS

Compression des informations est le processus de transformation des informations stockées dans un fichier en réduisant la redondance des données. Le but de ce procédé est de réduire le volume occupé par les données.

Fichier d'archive est un fichier spécialement créé contenant un ou plusieurs fichiers sous forme compressée.

Ratio de compression: K c = V c / V o *100 %

Kc- ratio de compression, Vc– volume du fichier compressé, Vo– taille initiale du fichier.

Le taux de compression dépend :

1) le programme utilisé - archiveur,

2) méthode de compression,

3) type de fichier source : texte, graphique, vidéo, son, etc.

Les programmes qui regroupent et décompressent des fichiers sont appelés archiveurs. Les plus courants sont : ARJ, ZIP, RAR. L'extension des fichiers d'archive correspond au nom de l'archiveur utilisé pour les créer.

Les archiveurs vous permettent de créer des fichiers d'archives auto-extractibles, c'est-à-dire Pour les décompresser, vous n'avez pas besoin de lancer le programme d'archivage, car ils contiennent eux-mêmes un programme de déballage. Ces archives sont appelées archives SFX
(auto-extractible). L'extension de ces fichiers est *.EXE.

Principes de compression des informations

Il y a des caractères répétés dans n'importe quel texte. Il est possible de spécifier un caractère et le nombre de répétitions. L'efficacité de cet algorithme est encore plus élevée lorsqu'il est appliqué aux fichiers graphiques. Si vous regardez le moniteur, vous pouvez voir de nombreux points répétitifs de la même couleur. Le format de fichier graphique PCX est basé sur ce principe de compression des informations. Les archiveurs modernes mettent en évidence non seulement les caractères répétitifs, mais également les chaînes de caractères et les mots individuels.

Si le texte n'utilise pas tous les caractères de l'alphabet PC, alors pour les coder, vous pouvez utiliser un octet, 8 bits ou un nombre plus petit. Ce principe est utilisé dans l'appareil télégraphique, où seules les majuscules russes sont utilisées : 5 bits suffisent pour les représenter, ce qui permet d'écrire trois caractères sur deux octets.

3. Le principe suivant utilise le modèle selon lequel les lettres apparaissent dans le texte avec des fréquences différentes. Par exemple, dans ce texte, l'espace est le caractère le plus courant ; les symboles « a » et « et » sont très courants. Ces caractères apparaissant fréquemment peuvent être représentés sous la forme d'une courte séquence de bits, tandis que d'autres caractères peuvent être codés sous la forme d'une séquence plus longue. Par exemple:

4. Physiquement, le PC alloue de l'espace pour placer les fichiers sur le disque en clusters - par blocs de 4 Ko. Il est impossible d'en souligner moins. Par exemple, si un fichier a une taille de 8 193 octets (8 Ko et 1 octet), il occupera physiquement 16 Ko ou 16 384 octets. La combinaison d'un groupe de fichiers en un seul vous permet d'économiser sur ces restes. Cela permet de réaliser de grosses économies lors de l'emballage de petits fichiers.

Au total, lors du placement des fichiers séparément, 6 Ko ne sont pas utilisés, soit 100 % du contenu des fichiers. Dans le second cas, 2 Ko, soit 33 %, restent inutilisés.

Zip de l'archiveur

Emballage des fichiers pkzip [clés]<имя архива>[chemins de fichiers]

Clés: -rp archiver avec des sous-répertoires tout en conservant la structure

S P.W.D. protection par mot de passe d'archive (PWD)

A ajouter des fichiers à archiver

M déplacer les fichiers vers l'archive

V afficher le contenu des archives

Si tous les fichiers d'un répertoire sont en cours d'archivage, il est alors nécessaire de spécifier le masque *.*

Déballage des fichiers pkunzip [commutateurs]<имя архива>[noms de fichiers]

Clés : -d décompression avec sous-répertoires tout en préservant la structure

Mot de passe d'archive SPWD (PWD)

Archiveur arj

arj<команда>[clés]<имя архива>[noms de fichiers]

Pour l'archiveur arj, un fichier effectue à la fois les opérations de décompression et de compression.

Équipes : un archivage

e décompression sans préserver la structure des répertoires

X déballer en préservant la structure

l visualisation du contenu des archives

m déplacer les fichiers vers les archives

d supprimer des fichiers des archives

Clés : -r emballage avec des sous-répertoires tout en préservant la structure

V décomposition de l'archive en volumes avec un volume de vol (si précisé)

la taille des disquettes standards (360, 720, 1200, 1440) est indiquée en kilo-octets, la taille des disquettes non standard est indiquée en octets

V est indiqué lors du décompression d'une archive multivolume

g P.W.D. mot de passe d'archive ( P.W.D.)

Emballage de fichiers

Déballage des fichiers

L'un des types de programmes système les plus courants sont les programmes conçus pour l'archivage, le conditionnement de fichiers en compressant les informations qui y sont stockées.

La compression des informations est le processus de transformation des informations stockées dans un fichier, ce qui réduit leur redondance et, par conséquent, nécessite moins de mémoire pour le stockage.

La compression des informations dans les fichiers est réalisée en éliminant la redondance de diverses manières, par exemple en simplifiant les codes, en éliminant les bits constants ou en représentant des caractères répétés ou une séquence répétitive de caractères en termes de facteur de répétition et de caractères correspondants. Divers algorithmes pour une telle compression d'informations sont utilisés.

Un ou plusieurs fichiers peuvent être compressés, qui, sous forme compressée, sont placés dans ce qu'on appelle fichier d'archive, ou archiver.

Un fichier d'archive est un fichier spécialement organisé contenant un ou plusieurs fichiers sous forme compressée ou non compressée et des informations de service sur les noms de fichiers, la date et l'heure de leur création ou modification, leurs tailles, etc.

Le but du regroupement de fichiers est généralement d'assurer un placement plus compact des informations sur le disque, réduisant ainsi le temps et, par conséquent, le coût de transmission des informations sur les canaux de communication des réseaux informatiques. De plus, le regroupement d'un groupe de fichiers dans un seul fichier d'archive simplifie considérablement leur transfert d'un ordinateur à un autre, réduit le temps de copie des fichiers sur des disques, vous permet de protéger les informations contre tout accès non autorisé et contribue à vous protéger contre les infections par des virus informatiques.

Sous ratio de compression comprendre le rapport entre les tailles du fichier compressé et de l'original, exprimé en pourcentage.

Ratio de compression dépend du programme de compression utilisé, de la méthode de compression et du type de fichier source. Les meilleurs fichiers compressés sont les images graphiques, les fichiers texte, les fichiers de données dont le taux de compression peut atteindre 5 à 40 %, les fichiers de programmes exécutables et de modules de chargement sont moins compressés - 60 à 90 %. Les fichiers d'archives ne sont presque pas compressés. Les programmes d'archivage diffèrent par les méthodes de compression qu'ils utilisent, ce qui affecte par conséquent le taux de compression.

Archivage (packaging) - placement (téléchargement) des fichiers sources dans un fichier d'archive sous forme compressée ou non compressée.

La décompression (décompression) est le processus de restauration des fichiers d'une archive exactement tels qu'ils étaient avant d'être chargés dans l'archive. Lors du déballage, les fichiers sont extraits de l'archive et placés sur le disque ou dans la RAM.

Les programmes qui regroupent et décompressent des fichiers sont appelés programmes d'archivage.

Les fichiers d'archives volumineux peuvent être placés sur plusieurs disques (volumes). De telles archives sont appelées multi-volumes. Un volume fait partie intégrante d'une archive multivolume. En créant une archive à partir de plusieurs parties, vous pouvez enregistrer ses parties sur plusieurs supports.

Principaux types de programmes d'archivage

Actuellement, plusieurs dizaines de programmes d'archivage sont utilisés, qui diffèrent par la liste des fonctions et des paramètres de fonctionnement, mais les meilleurs d'entre eux ont à peu près les mêmes caractéristiques. Parmi les programmes les plus populaires figurent : Zip (et sa modification WinZip), WinRAR, Arj (et ses variétés), G-Zip, 7-Zip.

Les programmes d'archives vous permettent également de créer des archives qui ne nécessitent aucun programme pour extraire les fichiers, car les fichiers d'archives eux-mêmes peuvent contenir un programme de décompression. De tels fichiers d'archives sont appelés auto-extractibles. Un fichier d'archive auto-extractible est un module amorçable et exécutable capable de décompresser indépendamment les fichiers qu'il contient sans utiliser de programme d'archivage.

Archives auto-extractibles j'ai le nom Archives SFX(auto-extractible). Les archives de ce type sont généralement créées au format de fichier EXE.

De nombreux programmes d'archivage décompressent les fichiers en les déversant sur le disque, mais il existe également ceux qui sont conçus pour créer un module exécutable (programme) packagé. À la suite d'un tel packaging, un fichier programme est créé avec le même nom et la même extension, qui, une fois chargé dans la RAM, s'auto-extrait et s'exécute immédiatement. Dans le même temps, il est également possible de reconvertir le fichier programme au format décompressé. Ces archiveurs incluent les programmes Upx, PKLITE, LZEXE.

Le programme EXPAND, qui fait partie des utilitaires du système d'exploitation Windows, est utilisé pour décompresser les fichiers des produits logiciels fournis par Microsoft.

Façons de gérer le programme d'archivage

Le programme d'archivage est contrôlé de l'une des manières suivantes :

• - à l'aide de la ligne de commande, dans laquelle une commande de lancement est générée contenant le nom du programme archiveur, la commande de contrôle et ses clés de configuration, ainsi que les noms des fichiers archive et source ;
• - en utilisant un shell intégré et des panneaux de dialogue qui apparaissent après le démarrage du programme et permettent le contrôle à l'aide de menus et de touches de fonction, ce qui crée des conditions de travail plus confortables pour l'utilisateur ;
• - à l'aide du menu contextuel de l'Explorateur du système d'exploitation Windows.

Première partie - historique.

Introduction

Les algorithmes de compression de données existants peuvent être divisés en deux grandes classes : avec et sans perte. Les algorithmes avec perte sont couramment utilisés pour la compression d’images et d’audio. Ces algorithmes permettent d'obtenir des taux de compression élevés grâce à une perte de qualité sélective. Cependant, par définition, il est impossible de récupérer les données originales à partir du résultat compressé.
Les algorithmes de compression sans perte sont utilisés pour réduire la taille des données et fonctionnent de telle manière qu'il est possible de restaurer les données exactement telles qu'elles étaient avant la compression. Ils sont utilisés dans les communications, les archiveurs et certains algorithmes de compression d'informations audio et graphiques. Ensuite, nous considérerons uniquement les algorithmes de compression sans perte.
Le principe de base des algorithmes de compression repose sur le fait que dans tout fichier contenant des données non aléatoires, les informations sont partiellement répétées. À l'aide de modèles mathématiques statistiques, vous pouvez déterminer la probabilité de répétition d'une certaine combinaison de symboles. Vous pouvez ensuite créer des codes pour les phrases sélectionnées et attribuer les codes les plus courts aux phrases les plus fréquemment répétées. Pour cela, diverses techniques sont utilisées, par exemple : le codage entropique, le codage par répétition et la compression par dictionnaire. Avec leur aide, un caractère de 8 bits ou une chaîne entière peut être remplacé par quelques bits seulement, éliminant ainsi les informations inutiles.

Histoire

Hiérarchie des algorithmes :

Bien que la compression des données se soit généralisée avec Internet et après l'invention des algorithmes de Lempel et de Ziv (algorithmes LZ), plusieurs exemples antérieurs de compression peuvent être cités. Morse, lorsqu'il a inventé son code en 1838, a judicieusement attribué les lettres les plus fréquemment utilisées dans la langue anglaise, « e » et « t », les séquences les plus courtes (respectivement point et tiret). Peu de temps après l'avènement des ordinateurs centraux en 1949, l'algorithme de Shannon-Fano a été inventé, qui attribuait des codes aux caractères d'un bloc de données en fonction de la probabilité de leur apparition dans le bloc. La probabilité qu'un caractère apparaisse dans un bloc était inversement proportionnelle à la longueur du code, ce qui permettait de compresser la représentation des données.
David Huffman était élève dans la classe de Robert Fano et a choisi comme cours la recherche d'une méthode améliorée de codage des données binaires. En conséquence, il a réussi à améliorer l'algorithme de Shannon-Fano.
Les premières versions des algorithmes de Shannon-Fano et Huffman utilisaient des codes prédéfinis. Plus tard, ils ont commencé à utiliser des codes créés dynamiquement à partir de données destinées à la compression. En 1977, Lempel et Ziv publient leur algorithme LZ77, basé sur l'utilisation d'un dictionnaire créé dynamiquement (également appelé « fenêtre glissante »). En 1978, ils ont publié l'algorithme LZ78, qui analyse d'abord les données et crée un dictionnaire, au lieu de le créer dynamiquement.

Questions de droits

Les algorithmes LZ77 et LZ78 ont acquis une grande popularité et ont provoqué une vague d'améliorations, parmi lesquelles DEFLATE, LZMA et LZX ont survécu jusqu'à ce jour. La plupart des algorithmes populaires sont basés sur LZ77, car l'algorithme LZW dérivé de LZ78 a été breveté par Unisys en 1984, après quoi ils ont commencé à troller tout le monde, y compris même les cas d'utilisation d'images GIF. À cette époque, une variante de l'algorithme LZW appelée LZC était utilisée sous UNIX et, en raison de problèmes de droits, son utilisation a dû être progressivement abandonnée. La préférence a été donnée à l'algorithme DEFLATE (gzip) et à la transformée de Burrows-Wheeler, BWT (bzip2). Ce qui était pour le mieux, puisque ces algorithmes surpassent presque toujours LZW en compression.
En 2003, le brevet avait expiré, mais le train était déjà parti et l'algorithme LZW n'était peut-être conservé que dans les fichiers GIF. Les algorithmes basés sur LZ77 sont dominants.
Il y a eu une autre bataille de brevets en 1993 lorsque Stac Electronics a découvert que l'algorithme LZS qu'il avait développé était utilisé par Microsoft dans un programme de compression de disque fourni avec MS-DOS 6.0. Stac Electronics a intenté une action en justice et a réussi à gagner le procès, ce qui lui a valu plus de 100 millions de dollars.

La montée du Deflate

Les grandes entreprises ont utilisé des algorithmes de compression pour stocker des quantités toujours croissantes de données, mais le véritable essor des algorithmes est survenu avec la naissance d’Internet à la fin des années 1980. La capacité des canaux était extrêmement étroite. Pour compresser les données transmises sur le réseau, les formats ZIP, GIF et PNG ont été inventés.
Tom Henderson a inventé et lancé le premier archiveur à succès commercial, ARC, en 1985 (System Enhancement Associates). ARC était populaire parmi les utilisateurs du BBS parce que... il fut l'un des premiers à pouvoir compresser plusieurs fichiers dans une archive, et ses sources étaient également ouvertes. ARC a utilisé un algorithme LZW modifié.
Phil Katz, inspiré par la popularité d'ARC, a publié le programme PKARC au format shareware, dans lequel il a amélioré les algorithmes de compression en les réécrivant en langage Assembly. Cependant, Henderson a été jugé et reconnu coupable. PKARC a copié ARC si ouvertement qu'il a même parfois répété des fautes de frappe dans les commentaires du code source.
Mais Phil Katz n'était pas perdu et, en 1989, il modifia considérablement l'archiveur et publia PKZIP. Après avoir été attaqué pour son brevet sur l'algorithme LZW, il a remplacé l'algorithme de base par un nouveau appelé IMPLODE. Le format a été remplacé à nouveau en 1993 avec la sortie de PKZIP 2.0, et DEFLATE est devenu le remplaçant. Parmi les nouvelles fonctionnalités figurait la fonction de division des archives en volumes. Cette version est encore largement utilisée, malgré son âge avancé.
Le format d'image GIF (Graphics Interchange Format) a été créé par CompuServe en 1987. Comme vous le savez, le format prend en charge la compression d'image sans perte et est limité à une palette de 256 couleurs. Malgré tous les efforts d'Unisys, celui-ci n'a pas réussi à arrêter la propagation de ce format. Il est toujours populaire aujourd’hui, notamment grâce à son support d’animation.
Légèrement troublé par des problèmes de brevets, CompuServe a lancé le format Portable Network Graphics (PNG) en 1994. Comme ZIP, il utilisait le nouvel algorithme DEFLATE. Bien que DEFLATE ait été breveté par Katz, celui-ci n'a fait aucune réclamation.
C’est aujourd’hui l’algorithme de compression le plus populaire. En plus de PNG et ZIP, il est utilisé dans gzip, HTTP, SSL et d'autres technologies de transfert de données.

Malheureusement, Phil Katz n'a pas vécu assez longtemps pour voir le triomphe de DEFLATE ; il est mort d'alcoolisme en 2000 à l'âge de 37 ans. Citoyens – la consommation excessive d’alcool est dangereuse pour la santé ! Vous ne vivrez peut-être pas assez longtemps pour voir votre triomphe !

Archiveurs modernes

ZIP a régné en maître jusqu'au milieu des années 90, mais en 1993, un simple génie russe, Evgeniy Roshal, a mis au point son propre format et algorithme RAR. Ses dernières versions sont basées sur les algorithmes PPM et LZSS. Aujourd'hui, ZIP est peut-être le format le plus courant, RAR était jusqu'à récemment la norme pour la distribution de divers contenus illégaux via Internet (grâce à l'augmentation de la bande passante, les fichiers sont de plus en plus distribués sans archivage), et 7zip est utilisé comme format avec la meilleure compression. avec une durée de fonctionnement acceptable. Dans le monde UNIX, la combinaison tar + gzip est utilisée (gzip est un archiveur, et tar combine plusieurs fichiers en un seul, car gzip ne peut pas le faire).

Note traduction Personnellement, en plus de ceux répertoriés, je suis également tombé sur l'archiveur ARJ (Archivé par Robert Jung), qui était populaire dans les années 90 à l'époque du BBS. Il prenait en charge les archives multivolumes et, tout comme RAR, il était utilisé pour distribuer des jeux et d'autres logiciels. Il y avait aussi l'archiveur HA de Harri Hirvola, qui utilisait la compression HSC (je n'ai trouvé aucune explication claire - seulement « un modèle de contexte limité et un encodage arithmétique »), qui faisait du bon travail en compressant de longs fichiers texte.

En 1996, la version open source de l’algorithme BWT, bzip2, est apparue et a rapidement gagné en popularité. En 1999, le programme 7-zip est apparu au format 7z. En termes de compression, il rivalise avec RAR, son avantage est l'ouverture, ainsi que la possibilité de choisir entre les algorithmes bzip2, LZMA, LZMA2 et PPMd.
En 2002, un autre archiveur est apparu, PAQ. L'auteur Matt Mahone a utilisé une version améliorée de l'algorithme PPM en utilisant une technique appelée « mélange contextuel ». Il vous permet d'utiliser plusieurs modèles statistiques pour améliorer la prédiction de la fréquence des symboles.

L'avenir des algorithmes de compression

Bien sûr, Dieu le sait, mais apparemment, l'algorithme PAQ gagne en popularité en raison de son très bon taux de compression (bien qu'il soit très lent). Mais grâce à l’augmentation de la vitesse des ordinateurs, la vitesse devient moins critique.
D’autre part, l’algorithme LZMA de Lempel-Ziv – Markov représente un compromis entre vitesse et taux de compression et peut donner lieu à de nombreuses ramifications intéressantes.
Une autre technologie intéressante est la « substring énumération » ou CSE, encore peu utilisée dans les programmes.

Dans la partie suivante, nous examinerons l'aspect technique des algorithmes mentionnés et les principes de leur fonctionnement.