Compression dans le Big Data : types et techniques

\

Introduction

Cet article traite de la compression dans le contexte du Big Data, en couvrant les types et méthodes de compression. Je mettrai également en lumière pourquoi et quand chaque type et méthode devrait être utilisé.

\

Qu'est-ce que la compression ?

Selon la définition générale anglaise de la compression, elle fait référence à la réduction de quelque chose pour occuper un espace plus petit. En informatique, la compression est le processus de réduction des données à une taille plus petite. Les données, dans ce cas, peuvent être représentées sous forme de texte, de fichiers audio, vidéo, etc. Pensez-y comme tout ce que vous stockez sur le disque dur de votre ordinateur, sous forme de données représentées dans différents formats. Pour fournir une définition plus technique, la compression est le processus d'encodage des données pour utiliser moins de bits.

\ Il existe plusieurs raisons de compresser les données. La raison la plus courante et intuitive est d'économiser de l'espace de stockage. D'autres raisons découlent du fait que les données sont plus petites. Les avantages de travailler avec des données plus petites incluent :

1. Temps de transmission des données plus rapide : Les données compressées sont de taille plus petite et prennent moins de temps pour être transmises de la source à la destination.
2. Consommation de bande passante réduite : Cette raison est fortement liée à l'avantage d'une transmission de données plus rapide. Les données compressées utilisent moins de bande passante réseau, augmentant ainsi le débit et réduisant la latence.
3. Performances améliorées pour les systèmes numériques qui dépendent fortement des données : Cela est évident dans les systèmes qui s'appuient sur le traitement des données. Ces systèmes exploitent la compression pour améliorer les performances des systèmes en réduisant le volume de données à traiter. Veuillez noter que cela peut être spécifique au système et dépendra de l'utilisation de la technique de compression appropriée. Les techniques de compression seront discutées plus tard dans cet article.
4. Efficacité des coûts : Les services cloud facturent le stockage des données. En utilisant moins de stockage, des économies de coûts sont introduites, en particulier dans les systèmes Big Data.

\ D'autres raisons de compression dépendent de différentes techniques et formats de compression. Certains algorithmes de chiffrement peuvent être utilisés comme méthode de compression. Ce faisant, cela inclut une couche de sécurité pour les raisons évoquées précédemment de compresser les données. De plus, l'utilisation de formats de compression courants apporte compatibilité et possibilités d'extensibilité aux systèmes externes à des fins d'intégration.

\ Il convient de noter que les raisons de la compression ressemblent également à des avantages. Cependant, la compression n'est pas sans compromis. Un compromis courant de la compression est la nécessité de décompression, ce qui peut être préoccupant pour les systèmes à ressources limitées. D'autres compromis dépendent de la technique de compression et du type de données utilisées.

\

Types de compression

Pour discuter des différentes techniques utilisées pour compresser les données, je vais d'abord catégoriser la compression en 2 catégories principales. Cet article discutera ensuite des techniques pertinentes pour chaque catégorie. La compression peut être globalement regroupée en compression avec perte et sans perte.

\ Comme les noms révèlent déjà leur signification, les techniques de compression avec perte sont des techniques qui ne préservent pas la fidélité complète des données. En termes simples, certaines données sont supprimées, mais pas assez pour rendre ce que les données représentent méconnaissable. Ainsi, la compression avec perte peut offrir un niveau de compression très élevé par rapport à la compression sans perte, qui sera présentée sous peu.

\ Une caractéristique de la compression avec perte est qu'elle est irréversible, c'est-à-dire que lorsqu'on présente le fichier compressé, on ne peut pas restaurer les données brutes avec leur fidélité d'origine. Certains fichiers et formats de fichiers conviennent à la compression avec perte. Elle est généralement utilisée pour les images, l'audio et les vidéos. Par exemple, les images au format JPEG se prêtent bien à la compression, et en compressant une image JPEG, le créateur ou l'éditeur peut choisir quelle perte introduire.

\ D'autre part, la compression sans perte est réversible, ce qui signifie que lorsqu'elle est compressée, toutes les données sont préservées et entièrement restaurées lors de la décompression. Cela implique que la compression sans perte convient aux fichiers de type texte, et dans le monde des entrepôts de données et des lakehouses, ce serait le seul type pertinent à utiliser. Certains formats de fichiers audio (FLAC et ALAC) et d'image (GIF, PNG, etc.) fonctionnent bien avec ce type de compression.

Choisir une méthode

Il n'existe pas de meilleure méthode de compression générale. Différents facteurs entrent en jeu dans le choix de la méthode qui serait appropriée au cas par cas. Pour étayer cela avec des exemples, un ingénieur de données dans le secteur financier travaillant sur des données tabulaires stockées aurait tendance à utiliser la compression sans perte en raison de l'impact des données manquantes dans la création de rapports précis. Alternativement, la compression avec perte pourrait être la solution pour optimiser une page web avec beaucoup d'images en compressant les images et en réduisant les éléments de chargement en rendant le site web plus léger. Par conséquent, il est crucial de mener une évaluation pour déterminer la méthode de compression la plus appropriée qui s'aligne sur les exigences commerciales.

Techniques de compression

Cette section ne couvrira que les techniques de compression courantes pour la compression avec perte et sans perte. Veuillez noter que cela n'est en aucun cas exhaustif. De plus, les techniques discutées peuvent avoir de légères variations pour améliorer leurs performances, comme le soutiennent différentes recherches.

Techniques de compression sans perte

Trois techniques sans perte courantes sont le Run-Length Encoding (RLE), le codage de Huffman et les techniques Lempel-Ziv-Welch.

\ Run-Length Encoding : Le RLE est basé sur l'encodage des données, de sorte qu'il remplace les séquences de données répétées par un seul élément de données et le nombre de cet élément de données. Il est efficace pour les longues séries de données répétées. De plus, les ensembles de données qui ont des dimensions (champs) triés d'un faible niveau à un niveau élevé de cardinalité bénéficient du RLE.

\ Par exemple, prenez une chaîne simple comme AAAAABBCDDD. Le RLE compresse les données pour devenir A(5)B(2)C(1)D(3). Pour être plus pratique, prenez un tableau dans l'image ci-dessous.

\ Figure 1 - avant RLE. Il est important d'observer que le niveau de cardinalité augmente sur les champs de gauche à droite

Figure 2 - Après RLE

Parce que le RLE dépend des séries de champs répétés, et dans le deuxième exemple, de la cardinalité et de l'ordre de tri des données, l'enregistrement Mouse sur la colonne item ne peut pas être compressé en juste Mouse (3) car la colonne précédente divise toutes les valeurs en IT, Mouse et HR, Mouse. Certains formats de fichiers sont compatibles avec le RLE, tels que les formats de fichiers bitmap comme TIFF, BMP, etc. Les fichiers Parquet prennent également en charge le RLE, ce qui le rend très utile dans les lakehouses de données modernes utilisant le stockage d'objets comme S3 ou GCS.

\ Codage de Huffman : Il est basé sur la modélisation statistique qui attribue des codes de longueur variable aux valeurs dans les données brutes en fonction de la fréquence à laquelle elles se produisent dans les données brutes. La représentation de cette modélisation peut être appelée arbre de Huffman, qui est similaire à un arbre binaire. Cet arbre est ensuite utilisé pour créer un code de Huffman pour chaque valeur dans les données brutes. L'algorithme donne la priorité à l'encodage des valeurs les plus fréquentes avec le moins de bits possible.

\ Prenons les mêmes données utilisées dans l'exemple RLE AAAAABBCDDD. L'arbre de Huffman correspondant ressemble à ceci.

\ Arbre de Huffman

À partir de l'arbre, nous pouvons voir que la lettre A est représentée par 0 de même D est présenté par 10. Comparé aux lettres B: 111 et C:110, nous observons que A et D sont représentés par moins de bits. C'est parce qu'ils ont une fréquence plus élevée ; par conséquent, l'algorithme de Huffman les représente avec moins de bits par conception. Les données compressées résultantes deviennent 00000111111110101010.

\ Le codage de Huffman utilise la règle de préfixe, qui stipule que le code représentant un caractère ne doit pas être présent dans le préfixe d'un autre code. Par exemple, un code de Huffman valide ne peut pas avoir les lettres c et d représentées en utilisant C: 00 et D: 000 car la représentation de C est un préfixe de D.

\ Pour voir cela en action, le Computer Science Field Guide a un générateur d'arbre de Huffman avec lequel vous pouvez jouer.

\ Codage Lempel–Ziv–Welch : Il a été créé par Abraham Lempel, Jacob Ziv et Terry Welch en 1984 et porte le nom des créateurs, évidemment 😅. Semblable au RLE et au codage de Huffman, le LZW fonctionne bien avec les données qui contiennent beaucoup de données répétées. L'algorithme LZW est basé sur un dictionnaire et crée un dictionnaire contenant des paires clé-valeur de modèles couramment observés dans les données brutes. Un tel dictionnaire peut également être appelé table de codes. En utilisant une illustration pour expliquer comment fonctionne cette technique, prenons nos données brutes pour être représentées par ABBABABABA. Lorsqu'elles sont transmises à travers l'algorithme en utilisant une configuration de A-Z comme valeurs possibles, la table de codes résultante ressemble à :

\ Table de codes LZW

À partir de la table de codes ci-dessus, il y a une paire clé-valeur pour toutes les lettres A-Z et des paires clé-valeur pour des modèles tels que AB, BB, BA et ABA. En ayant une représentation plus courte de ces modèles, l'algorithme LZW peut compresser les données brutes en les encodant en moins de bits. Ainsi, en utilisant la table de codes générée à partir de cette entrée, la version compressée est 0 1 1 26 29 28. Il est important de remarquer les espaces dans les données compressées. On pourrait les considérer comme la fin d'un caractère, de sorte que le décodeur n'interprétera pas un 1,0 comme un 10 car ils signifient des choses différentes.

\ Le LZW est généralement à usage général et largement utilisé aujourd'hui. Il est intégré dans de nombreux systèmes d'exploitation basés sur Unix/Linux derrière la commande shell compress. De plus, les formats de fichiers courants compatibles avec le LZW sont GIF, TIFF et PDF. D'autres applications de la compression LZW peuvent être vues dans le domaine du traitement du langage naturel, comme discuté dans cet article sur la tokenisation en NLP.

\ Le RLE, le codage de Huffman et le codage LZW ne sont que des exemples courants. Les techniques de compression sans perte vont au-delà de ces trois (3) décrites ci-dessus. D'autres techniques incluent DEFLATE, qui utilise une combinaison de codage Huffman et LZW - spécifiquement LZ77.

Techniques de compression avec perte

Dans cette section, nous examinerons deux types de compression avec perte. Rappelons que la compression avec perte introduit une perte dans les données d'origine, ce qui signifie que toutes les données ne sont pas conservées.

\ Transformée en cosinus discrète (DCT) : Cette méthode de compression est principalement utilisée dans les fichiers audio, image et vidéo et est également communément appelée compression par blocs. Elle utilise une fonction mathématique - la fonction cosinus, comme son nom l'indique - pour convertir des blocs de données d'origine en fréquences. Les blocs de données sont généralement une matrice de 8x8, 4x4, et ainsi de suite, dans cet ordre de grandeur.

\ La compression intervient lors du traitement des hautes fréquences se produisant dans les données, une fois que les données brutes sont traduites dans le domaine fréquentiel à l'aide de la fonction mathématique. Le processus global d'utilisation de la DCT pour la compression est :

• Décomposer les données brutes en morceaux. Par exemple, dans la compression d'image, cela pourrait être 8x8 pixels.
• Appliquer la fonction mathématique pour convertir les morceaux de données en fréquences. Cela entraînera certaines hautes fréquences et basses fréquences.
• Les hautes fréquences sont ensuite réduites ou supprimées en fonction du degré de perte acceptable que l'on est prêt à introduire. C'est là qu'il devient vraiment une compression avec perte.
• Pour reconvertir en données représentables, toutes les fréquences restantes sont transmises à travers une transformée en cosinus discrète inverse - IDCT - pour restaurer les données à partir des fréquences.

\ La DCT est largement utilisée dans différents domaines aujourd'hui, non seulement dans la compression mais aussi dans le traitement du signal. Les formats de fichiers courants compatibles avec la DCT sont JPEG (images), MP3 (audio) et MPEG (vidéo). De plus, la DCT peut atteindre des ratios de compression élevés, ce qui la rend adaptée aux systèmes numériques avec beaucoup d'images, comme les pages web sur Internet.

\ Compression fractale : Une fractale est un motif infini auto-répétitif qui se répète à différentes échelles. Lorsqu'elle est vue de n'importe quel point sur l'échelle, le motif semble similaire. Parce que les motifs sont similaires à n'importe quelle échelle, la compression fractale réduit l'échelle des « grandes » fractales pour réduire la taille des données.

\ Exemples de fractales

La compression fractale a été introduite par Michael Barnsley dans les années 1980. L'idée générale en utilisant une image est que si une image contient plusieurs parties qui se ressemblent, pourquoi les stocker deux fois ? Pour ce faire, la compression fractale fait ce qui suit :

• Partitionne l'image en blocs non chevauchants connus sous le nom de blocs de plage. Cela pourrait être des blocs de plage de 8x8, 16x16 pixels, etc.
• Elle analyse l'image à la recherche de motifs auto-répétitifs (motifs fractals). En utilisant les blocs de plage, l'algorithme trouve de plus grandes sections de l'image qui sont similaires à ces blocs de plage. Ces sections plus grandes sont appelées blocs de domaine.
• Une fonction de transformation est ensuite appliquée au bloc de domaine pour approximer les blocs de plage. Ces fonctions de transformation sont des fonctions mathématiques telles que la mise à l'échelle, la translation, la rotation, etc. Elles peuvent également être appelées transformations. Ces transformations sont appelées codes fractals en ce qui concerne la compression fractale.
• Les données sont ensuite encodées vers ces fonctions de transformation. Au lieu de stocker les données pixel par pixel, les transformations sont stockées. Ces transformations sont les règles qui décrivent comment reconstruire l'image à partir de blocs de domaine.

\ Avec les codes fractals, l'image est reconstruite à l'aide d'un processus itératif. Ce processus peut être coûteux en calcul, mais la compression fractale pourrait atteindre un ratio de compression élevé par rapport à d'autres techniques de compression. En raison de sa dépendance aux motifs auto-répétitifs, elle fonctionnerait mieux sur les données qui se conforment à avoir de tels motifs auto-répétitifs. Des exemples seraient des photographies de paysages (images de la nature) et des images d'ADN.

\ Il existe d'autres techniques de compression avec perte, telles que la transformée en ondelettes discrète, la quantification. Ces techniques sont généralement utilisées dans les fichiers d'images, audio et vidéo et conviennent à certains types ou formats de fichiers - JPEG, MP3 - pour chaque type de fichier.

\ La compression avec perte a généralement des ratios de compression plus élevés que la compression sans perte et attend parfois que l'utilisateur connaisse la quantité de perte à introduire à l'avance. Il est pertinent de souligner que le choix de la méthode et de la technique de compression dépend de plusieurs facteurs. Au cœur de ces facteurs se trouvent le format des données et le résultat souhaité.

TL;DR

Dans l'ensemble, cet article traite de la compression dans le monde des données. Il s'appuie fortement sur le corpus de connaissances existant en informatique et en théorie de l'information. Compresser signifie réduire le volume qu'une entité occupe, et dans le domaine des données, le volume fait référence à l'espace de stockage. La compression dans les systèmes numériques présente de nombreux avantages lorsqu'elle est bien faite. L'évidence est qu'elle réduit l'espace et donne de la place pour stocker plus de données. D'autres avantages incluent une transmission plus rapide, une utilisation moindre de la bande passante et une amélioration générale de l'efficacité dudit système. Rappelez-vous, c'est quand c'est bien fait.

\ Pour tirer parti des avantages de la compression, il est essentiel de savoir quel type utiliser. La compression est soit avec perte soit sans perte. La compression avec perte introduit une perte dans les données d'origine qui est généralement irréversible, tandis que la compression sans perte compresse les données et conserve toutes les informations contenues dans les données d'origine. De plus, il y a un discours sur les types de compression hybrides, mais je pense qu'une combinaison de avec perte et sans perte est juste avec perte. Faites-moi savoir ce que vous en pensez dans les commentaires.

\ Enfin, différentes techniques ont été introduites pour la compression avec perte et sans perte. La liste des techniques et les explications de ces techniques ne sont ni exhaustives ni complètes. Je les considère seulement comme un bon début pour vous donner une idée de la façon dont chaque technique fonctionne. Pour conclure, j'ai ajouté des ressources supplémentaires pour vous aider à enquêter davantage et à lire plus en profondeur sur la compression dans le big data.

Ressources supplémentaires

Vidéo : Fondamentaux du Data Lake - Encodage RLE avec Parquet en pratique

Article : Une revue des techniques de compression de données

Article : Techniques de compression sans perte

Une introduction concise à la compression de données par David Salomon

Article : Une étude de diverses techniques de compression de données

Article de blog : Compression dans les formats de fichiers ouverts

Article : Formats de fichiers ouverts

Article : Compression dans les bases de données

Compression avec perte pour les données génomiques (ARN)

\