Une première possibilité de compactage est de limiter la redondance des informations, sans se préoccuper de leur origine, c'est-à-dire en considérant tous les signifiants élémentaires (bits, octets, mots...) comme a priori statistiquement indépendants.
Par nature indépendante des données à traiter (images, sons, textes, fichiers exécutables), la compression des fichiers binaires est impérativement une transformation entièrement réversible. Les algorithmes de compression/décompression utilisés se doivent d'être non dégradants pour garantir l'intégrité des informations traitées. À ce titre, on peut considérer qu'ils relèvent simplement d'un codage particulier d'un fichier.
Ces codages optimisés sont d'ailleurs de plus en plus souvent appelés à être utilisés directement par les systèmes d'exploitation, au niveau le plus bas. Dans certains cas, leur mise en œuvre peut même amener une amélioration des performances : la durée de la lecture sur disque varie proportionnellement avec le taux de compression, et les traitements de décompactage peuvent se révéler moins longs que le gain obtenu. Leur intervention est alors totalement transparente pour les utilisateurs et l'ensemble des applications.
| La compression des
fichiers binaires ne tient pas compte de la nature des
données. C'est une opération qui doit être entièrement réversible, et on ne dispose d'aucune information préalable de redondance. |
L'origine des techniques de codage compressif est étroitement liée à l'optimisation des voies de communications télégraphiques et téléphoniques, notamment dans le cadre d'exploitations militaires. Les études les plus importantes ont été développées durant la deuxième guerre mondiale et les années suivantes, en particulier par Shannon. Le contexte particulier explique sans doute pourquoi les problèmes de compression et de cryptage sont étroitement liés dans la littérature...
Les codages dits “ à longueur variable ” (VLC variable length coding) utilisent les fréquences d'apparition des éléments du message pour attribuer aux plus fréquents des codes courts, et aux plus rares des codes longs. Les fréquences d'apparition peuvent, dans certains cas, être connues à l'avance (communications structurées à vocabulaire limité), mais elles doivent généraleemnt faire l'objet d'une analyse au cours du traitement. Dans de nombreux cas, il est nécessaire d'établir une table correspondant au message à compresser, et donc d'effectuer un traitement en deux passes (analyse, puis compression proprement dite). Outre la nécessité de relire deux fois les données, cette méthode ne permet pas la compression en temps réel. Pour éviter cette difficulté, on évalue quelquefois les redondances sur une partie du fichier, qui joue alors le rôle d'échantillon représentatif. Cependant, cette méthode est souvent peu précise, la représentativité de l'échantillon n'étant généralement pas mesurée. Les équipements modernes de communication (télécopieurs, modems) utilisent plutôt une analyse en temps réel sur des paquets de données de taille réduite.
Le code Shannon-Fano a été le premier algorithme statistique à connaître un succès important. Il a cependant rapidement été concurrencé par la méthode de Huffman, plus adaptée aux modes de traitement informatiques [Huffman, 1952].
À partir d'un étude statistique portant sur la fréquence des éléments signifiants présents dans les données originales, l'algorithme de Huffman attribue à chacun de ces éléments un code binaire dont la taille est d'autant plus réduite que le code est fréquent. Sauf dans le cas de textes aux caractéristiques rédactionnelles précises, dans une langue donnée (la fréquence des différentes lettres peut alors être estimée a priori), l'application de cette méthode suppose une première lecture des données, préalable au codage proprement dit, ayant pour buts une analyse statistique et la constitution d'une table de codage. La table de correspondance du codage ainsi établie devra être transmise pour le décodage (un exemple de traitement Huffman est proposé en annexe).
Les performances de cet algorithme dépendent des caractéristiques des données à compacter, mais il est possible de connaître le taux de compressibilité sans avoir à effectuer le compactage, uniquement à partir de l'analyse statistique. Les performances peuvent aussi être améliorées en changeant la taille des motifs dont on limite la redondance, et éventuellement en scindant les fichiers à coder. Le gain de compression moyen cité par Mark Nelson [Nelson, 1993, p. 389 et suivantes] est de 31 %, et les opérations de compactage et décompactage se révèlent très lentes.
Le codage de Huffman est utilisé, généralement associé à un ou plusieurs autres procédés, dans diverses situations de compression. On peut citer notamment les divers formats utilisés en télécopie et en transmission de données sur ligne téléphonique (protocoles MNP), ainsi que le Photo CD de Kodak pour les hautes définitions, ou encore les procédés MPEG.
| Le codage de Huffman est fondé sur une analyse des fréquences des signes dans les données à traiter. Actuellement, il est rarement utilisé seul, mais en revanche il est souvent associé à d'autres processus pour optimiser le codage final (télécopie, Photo CD, etc.). |
Les codages par dictionnaires sont également fondés sur l'analyse des répétitions dans les données à traiter. Cependant, il ne s'agit plus ici de rechercher des occurences de signifiants considérés comme élémentaires (généralement des octets), mais de “ mots ” (groupes d'octets) de longueur variable. Les mots répétés prennent place dans un dictionnaire, et chacun d'eux est remplacé, dans les données compréssées, par sa seule adresse dans le dictionnaire.
Si on considère que le dictionnaire français comporte environ 2 000 mots de 6 lettres, il est possible de les coder sur 11 bits, au lieu des 30 nécessaires au minimum selon un codage alphanumérique théorique (5 bits pour un alphabet de moins de 32 caractères), et des 48 bits nécessaires pour un mode ASCII. En renouvelant ce procédé sur les mots de différentes longueurs, on peut coder les textes en émettant pour chaque mot sa longueur suivie de son adresse dans le dictionnaire. Cet exemple montre bien qu'il est largement possible d'optimiser les codages classiques. Le procédé exposé est cependant trop simpliste pour satisfaire une gamme étendue de besoins (nécessité de s'accorder sur un dictionnaire, absence de traitement des termes non prévus, etc.) ; il est cependant quelquefois utilisé dans le cas d'univers de communications limités à un vocabulaire réduit et dotés d'un dictionnaire prédéfini connu du destinataire, et ne devant donc pas être transmis.
Pour pallier ces difficultés, et produire un procédé capable de s'adapter à une grande variété de besoins, il est nécessaire de définir un dictionnaire spécifique aux données à traiter. Cette méthode a cependant pour inconvénients de nécessiter deux lectures du fichier à traiter (la première pour constituer le dictionnaire, et la deuxième pour coder effectivement les données) et d'imposer la conservation d'un dictionnaire, qui peut devenir très lourd, en tête du fichier produit.
Abraham Lempel et Jacob Ziv ont publié en 1977 et 1978 des algorithmes de compression d'usage général (indépendant de la nature des données codées) fondés sur la construction d'un dictionnaire dynamique qui n'a pas à être sauvé en tant que tel, puisqu'il est reproduit automatiquement par le décompacteur en fonction des données du fichier comprimé [Ziv, 1977], [Ziv, 1978].
Les algorithmes de compression et décompression LZ ont des fonctionnement symétriques : leur principe est fondé sur l'indexation de chaînes dans un dictionnaire qui, dans les deux cas, est construit durant le traitement.
Le dictionnaire est défini comme un tableau de chaînes de tailles variables, repérées par leur adresse ; la taille du tableau est également variable, limitée par le mode de codage des adresses.
Cette méthode, plus performante que celles utilisées auparavant, souffre cependant de quelques difficultés. Sa programmation est assez complexe (gestion de pointeurs “ glissants ” sur des fenêtres, gestion de tableaux de longueur variable composés d'objets de longueur variable), et le programme peut conduire à des délais de traitement longs, notamment en compression. Le traitement s'effectuant sur une fenêtre, c'est sa taille qui détermine les performances du dispositif : lors du codage, les chaînes du tampon de lecture sont comparées à toutes les positions dans la fenêtre, et une taille réduite conduit à ne pas prendre en compte des chaînes répétées au delà de cette distance ; en revanche, une taille plus importante impose des traitements considérables, en multipliant le nombre de comparaisons nécessaires. De plus, s'il n'y a pas de correspondance, les caractères doivent être transmis individuellement, avec une longueur de séquence à zéro, ce qui peut conduire à une augmentation de la taille des données.
Principe de fonctionnement de LZ77
En 1978, Lempel et Ziv ont publié une nouvelle version de leur algorithme [Ziv, 1978], abandonnant le concept de fenêtre glissante. Le dictionnaire se construit dynamiquement, tout au long du traitement. Chaque signe transmis par le codeur comprend un index dans le dictionnaire, ainsi que le caractère suivant à coder. La longueur de la chaîne n'a plus à être transmise, puisqu'elle est conservée dans le dictionnaire ; la concaténation de la chaîne répétée avec le caractère suivant est également placée dans le dictionnaire, et devient ainsi disponible pour la totalité du codage ultérieur. Cette nouvelle version permet de dépasser les limites de LZ77, et améliore largement les performances, surtout sur les fichiers longs. Cependant, une nouvelle difficulté apparaît : la taille du dictionnaire est limitée par le mode de codage de ses index (souvent sur 16 bits, soit 65 536 entrées), et il est donc nécessaire de gérer l'évènement “ dictionnaire plein ”. Une possibilité est de laisser le dictionnaire en l'état, et de simplement l'utiliser, mais cela conduit à une détérioration des performances dans le cas de longs fichiers, qui peuvent présenter de grands changements dans la nature des données ; une autre solution est de supprimer le dictionnaire existant, et d'en reconstruire un autre, mais, dans le cas de données homogènes, cela peut conduire à une détérioration des performances. La solution généralement retenue est d'analyser le taux de compression obtenu avec le dictionnaire existant, et de le reconstruire seulement si on constate une détérioration.
Terry Welch (le “ W ” de LZW) a publié en 1984 de nouvelles améliorations [Welch, 1984]. Contrairement au dictionnaire de LZ78, qui ne contient au départ qu'une chaîne vide repérée par l'index “ 0 ”, celui de LZW comprend au départ les codes ASCII, repérés de 0 à 255 ; tous les symboles peuvent ainsi être directements codés selon le dictionnaire, permettant ainsi d'éviter la détérioration des performances pour les fichiers ne présentant que peu de répétitions. De plus, Welch a également défini les principes de communication entre codeur et décodeur : le caractère autoadaptatif du procédé est amélioré par la possibilité d'adapter dynamiquement les paramètres au cours du codage, les modifications étant communiquées au décodeur selon un codage spécifique. Il s'agit par exemple de l'augmentation de la taille des adresses, de la purge partielle ou totale du dictionnaire, de la création temporaire d'un autre dictionnaire, et plus généralement de tout changement de technique de compression en cours de traitement.
La plupart des compacteurs du marché utilisant LZ et ses variantes (Arj, Pkzip...) exploitent conjointement un algorithme statistique limité (issu de Huffman ou de Shannon-Fano), mais en évitant l'analyse préalable de l'ensemble du fichier, trop pénalisante en termes de vitesse d'exécution. Dans la plupart des cas, l'analyse est limitée à une fenêtre, dont la taille varie en fonction des mesures de représentativité statistique des résultats obtenus. D'autres variantes prévoient d'effectuer le compactage par “ paquets ” de taille fixe, ce qui permet des codages statistiques faciles, tout en ménageant des possibilités d'accès direct et de traitement “ au vol ” (modems).
Le plus cité des algorithmes LZ, le LZW (perfectionnements divers apportés par Welch en 84) est sans doute aussi le moins utilisé, car il a fait l'objet d'un brevet déposé par Unisys pour une exploitation directe par le système Unix. Dans la plupart des cas, les algorithmes mis en œuvre par les logiciels actuels sont des évolutions de LZ77 ou LZ78, exploitant quelques uns des principes mis en place par Welch, comme le codage des caractères ASCII ou l'adaptation de taille des dictionnaires.
Les codages Lempel Ziv sont à ce jour ceux qui permettent les meilleurs taux de compactage non destructif sur la plupart des fichiers. Les possibilités de paramétrage et d'association à d'autres techniques (statistiques notamment) offrent une infinité de variations permettant d'optimiser le rapport entre taux de compression et vitesse de traitement. Les taux obtenus sur un jeu d'essai [Marseau, 1992] mettent en évidence des compressions deux fois plus efficaces que celle de Huffman. Les tests effectués par Mark Nelson [Nelson, 1993] montrent des gains de compression moyens compris entre 45 et 50 % pour les différentes variantes.
De très nombreux programmes de tous types utilisent les algorithmes LZ. Outre les utilitaires spécialisés (Arc, Pkzip, Lharc, Arj), on peut citer les logiciels de sauvegarde (QIC-122 pour les sauvegardes à bandes, PC Backup, Norton Backup, MS Backup, Sytos), les protocoles de transmission haute vitesse par modem (V42bis), ainsi que diverses implémentations intégrées aux systèmes d'exploitation (Compress sous Unix, Dblspace de DOS 6). L'ensemble des compacteurs “ temps réel ” (Dblspace, Stacker...) utilisent ces techniques. Les variantes mises en œuvre sont souvent issues de LZ 77, qui se révèle plus performant sur les fichiers courts (le dictionnaire, et donc l'efficacité de LZ 78 et des versions postérieures croissent avec la taille du fichier) ; en outre, il a l'avantage d'être dans le domaine public.
| Les algorithmes Lempel Ziv sont les processus génériques les plus efficaces actuellement. Il existe d'innombrables variantes de ces algorithmes, dont le LZW, qui est sans doute le plus connu, mais aussi le moins utilisé, car il est protégé par brevet. Les processus de compactage et de décompactage sont symétriques, et procèdent à la construction d'un dictionnaire durant le traitement du fichier. |
| Sommaire |
 Suite |