Introduction à l'archivage et à la compression
Notre usage quotidien du numérique nous entraîne à générer une quantité massive de données, rendant indispensable l’utilisation de techniques efficaces pour leur stockage et leur transmission. Parmi ces techniques, l’archivage et la compression des données occupent une place essentielle.
Ce cours introduit les concepts fondamentaux de l’archivage et de la compression, en soulignant leur importance et leur utilité dans le monde numérique d’aujourd’hui.
Qu’est-ce que l’archivage ?
L’archivage désigne le processus de collecte et de stockage de données de manière organisée pour une conservation à long terme.
En informatique, cela implique souvent la regroupement de plusieurs fichiers et/ou dossiers en un seul fichier, appelée archive. Ce regroupement permet ainsi d’en faciliter la gestion, le stockage ou le transfert.
Prenons l’exemple d’un étudiant qui souhaite envoyer par courriel le contenu du dossier dans lequel il a rangé ses documents de travail. Créer une archive de ce dossier va lui permettre de réunir tous les dossiers et fichiers dans un seul fichier qu’il pourra facilement joindre à un courrier électronique.
Avant archivage
Après archivage
Pour consulter et exploiter le contenu d’une archive, il est recommandé d’effectuer une opération de désarchivage, qui consiste à extraire le contenu d’une archive, la structure arborescente utilisée initialement pour classer les fichiers sera reconstituée.
Ainsi, le destinataire du mail de notre étudiant pris en exemple pourra extraire le contenu de l’archive reçue et il retrouvera ainsi tous ses documents d’origine avec les dossiers utilisés pour les classer.
Qu’est-ce que la compression ?
La compression désigne un processus de réduction de la taille des fichiers. Ce traitement peut être effectuer de diverses manières : en réorganisant les données, en éliminant les redondances ou en utilisant des algorithmes complexes pour représenter les données différemment.
Il existe deux types principaux de compression : sans perte et avec perte.
La compression sans perte
La compression sans perte permet de restaurer les données dans leur état original après décompression, sans aucune perte d’information.
Il s’agit donc d’écrire les informations différemment. C’est un peu l’équivalent de ce que vous faites lorsque vous prenez des notes. Imaginons que votre enseignant vous donne cette définition :
La théorie de l’attachement, développée par John Bowlby, suggère que l’attachement entre un enfant et ses soignants est crucial pour le développement émotionnel et psychologique de l’enfant.
John Deuffe, MCF en Psychologie.
Vous prenez en note le texte suivant :
La thie de l’attachmt dévelo par J. Bowlby, sug. que l’attachmt U un enf et ses soign. est crucial pour le dévmt émo et psy de l’enf.
Moi, étu Psy.
Vous avez ainsi appliqué une compression d’environ 30 % permettant de passer de 190 à 134 caractères.
Cette compression est sans perte puisqu’en connaissant les abréviations utilisées, il est possible de retrouver le texte d’origine sans perte d’informations.
Les algorithmes de compression sans perte cherchent à identifier les redondances dans un texte afin de limiter les répétitions. Pour cela, il existe plusieurs méthodes :
- Codage par dictionnaire : Des séquences répétitives sont remplacées par des références courtes à une entrée dans un « dictionnaire » de séquences connues.
Pour illustrer le principe de compression avec codage par dictionnaire, utilisons l’algorithme de Lempel-Ziv (LZ), l’un des plus connus et utilisés dans ce domaine. Cet exemple simplifié vise à montrer comment les données peuvent être compressées en identifiant et en remplaçant les séquences répétitives par des références à des occurrences antérieures de ces mêmes séquences dans les données.
Prenons le texte à compresser suivant :
"bon bonbon bonbonbon"
Voici les étapes de la compression consistant à créer un dictionnaire :
Veuillez notez que les étapes d’indexation proposées ici ont été simplifiées pour des raisons pédagogiques.
- Initialisation : Le dictionnaire commence en étant vide (dans la pratique, il pourrait commencer avec des séquences de base connues pour augmenter l’efficacité). Au fur et à mesure de la lecture, chaque nouvelle séquence (mot ou combinaison de lettres) non encore rencontrée est ajoutée.
- Première occurrence : lorsque l’algorithme rencontre du texte nouveau, il l’ajoute au dictionnaire :
- 0 : b
- 1 : o
- 2 : n
- Deuxième occurrence : lorsque les lettres réapparaissent elles ne sont pas ajoutées au dictionnaire. Le mot bon lui est ajouté sous une autre forme :
- 3 : 0+1+2
- Extension : La séquence « bonbon » forme une nouvelle entrée
- 4 : 3+3
- Répétitions ultérieures : Pour la séquence « bonbonbon » l’entrée est la suivante :
- 5 : 4+3
- Initialisation : Le dictionnaire de compression est initialisé. Conformément aux pratiques optimales, il peut précharger des séquences couramment utilisées pour améliorer l’efficacité de la compression dès les premières étapes de l’analyse des données.
- Première occurrence : lorsque l’algorithme rencontre de nouvelles séquences, il les ajoute au dictionnaire. Les indices servent d’identifiants uniques pour les caractères ou séquences lors du processus de compression.
- 0 : b
- 1 : o
- 2 : n
- Traitement de bon : À la rencontre de la séquence « bon » pour la première fois, elle est identifiée comme une nouvelle séquence distincte plutôt que comme une agglomération de séquences précédemment rencontrées. Elle est donc ajoutée en tant que telle dans le dictionnaire :
- 3 : bon
- Traitement de bonbon : Lors de la lecture de « bonbon », l’algorithme détecte la présence préalable de la séquence « bon » dans le dictionnaire. Utilisant l’identification par index, il reconnaît que cette séquence a déjà été encodée et peut être réutilisée :
- 4 : 3+3
Cette notation indique que la séquence « bonbon » est conceptualisée comme une répétition de la séquence « bon », déjà codée avec l’indice 3. Ici, « 3+3 » symbolise la répétition de la séquence référencée par l’indice 3. Il s’agit cependant d’une abstraction simplifiée pour illustrer la répétition de la séquence « bon ». Dans une mise en œuvre réelle de compression de données, les références à des séquences répétées sont gérées via des mécanismes d’indexation et de pointeurs plus complexes.
Une fois le dictionnaire construit, le texte compressé peut être représenté par une série de références et d’identifiants, par exemple : 0,1,2 (pour bon), 4 (pour bonbon), 4,3 (pour bonbonbon) où chaque numéro fait référence à une entrée spécifique dans le dictionnaire construit pendant la compression.
Cette représentation est beaucoup plus compacte que le texte original, surtout si les séquences se répètent sur de longs segments de données. L’efficacité de la compression dépend fortement de la nature des données et de la fréquence des répétitions.
Pour reconstruire le texte original à partir de sa version compressée, le décompresseur reconstruit le dictionnaire en suivant les mêmes étapes que le compresseur, utilisant les références pour recréer les séquences. Chaque référence pointe vers une séquence spécifique dans le dictionnaire, permettant de restaurer le texte original sans perte.
Au lieu de stocker le dictionnaire, les algorithmes LZ stockent généralement une série d’instructions ou de références qui permettent de reconstruire le dictionnaire lors de la décompression. Ces instructions incluent des informations sur les séquences et comment elles se rapportent les unes aux autres (par exemple, des paires d’indices et de caractères suivants). Stocker le dictionnaire de manière explicite réduirait l’efficacité de la compression, surtout si le dictionnaire est grand ou si les données sont très répétitives.
- Codage de Huffman : Ce codage attribue des codes de longueurs variables aux éléments de données, en fonction de leur fréquence d’apparition. Les éléments les plus fréquents reçoivent les codes les plus courts, ce qui réduit la taille globale des données.
La compression avec perte
La compression avec perte réduit la taille du fichier en éliminant certaines données jugées moins importantes, ce qui va affecter la qualité ou la précision des données restaurées. Ce type de compression s’applique principalement aux fichier multimédia comme les images ou les vidéos. L’utilisateur devra ainsi faire un compromis lors de la compression entre le poids du fichier et sa qualité en fonction de la destination de l’image.
Dans l’exemple suivant, l’image de gauche est la moins compressée. Les deux autres images ont été compressées avec différents algorithmes. Le poids est beaucoup plus faible, mais la qualité a été réduite drastiquement (n’hésitez pas à zoomer l’image en cliquant dessus pour vous en rendre compte).
