15 Algorithmes de compression de données les plus populaires

Les algorithmes de compression de données peuvent être définis comme le processus de réduction de la taille des fichiers au moment de conserver les mêmes ou similaires à une certaine mesure de données. Ceci est fait en effectuant l’élimination des données inutiles ou en refaisant les données pour une plus grande efficacité.

Au moment de la compression, vous avez la possibilité de choisir entre les méthodes avec ou sans perte. Si nous parlons de la méthode avec perte, elle efface définitivement les données. D’autre part, la méthode sans perte prend soin de vos données originales. Le type que vous choisissez dépend de la qualité que vous exigez pour vos fichiers.
Dans cet article, vous trouverez un mélange d’algorithmes de compression de données sans perte et d’algorithmes de compression d’images et de vidéos basés sur l’apprentissage profond.

Les algorithmes de compression de données sans perte sont normalement des êtres utilisés pour remplir la fonction d’archive ou toute autre fonction de haute qualité. Ces algorithmes de compression de données permettent d’effectuer une réduction de la taille des fichiers. Il garantit également que les fichiers peuvent être restaurés entièrement s’ils devaient l’être.

LZ77

LZ77 a été annoncé en 1977 et qualifié de base de tant d’autres algorithmes de compression sans perte. Il utilise normalement la méthode de la « fenêtre glissante ». Dans cette méthodologie, il s’occupe d’un dictionnaire qui fait usage de triples pour représenter:

• Offset- Il peut être appelé comme le début réel de la phrase et le début du fichier.
• Longueur d’exécution-Il est défini comme la quantité des caractères qui vous aident à faire une phrase.
• Caractères de déviation-Ce sont les commercialisateurs qui indiquent une nouvelle phrase.

Il comprend une indication que la phrase utilisée est complètement égale à la phrase originale et définit également s’il y a un caractère différent.

Comme vous allez analyser un fichier, le dictionnaire est mis à jour dynamiquement pour le reflet du contenu des données compressées et de la taille également.

LZR

LZR a été développé et annoncé dans l’année 1981. Michael Rodeh l’a annoncé, et il l’a modifié plus tard. Il peut être utilisé comme une alternative principale pour l’algorithme de compression de données LZ77, mais vous avez également la possibilité de l’utiliser pour n’importe quel décalage dans le fichier. Si vous ne l’utilisez pas de manière linéaire, il a besoin d’une quantité importante de mémoire. Cette condition fait de LZ77 une meilleure option à utiliser. Cet algorithme de compression de données est simple à mettre en œuvre et a le potentiel pour des performances très élevées lorsqu’il est mis en œuvre sur le matériel.

Il est l’algorithme qui est largement utilisé Unix data compression algorithm utility compress and is used in the GIF image format. Il est devenu le premier algorithme de compression de données largement utilisé sur les ordinateurs. Un grand fichier texte anglais peut généralement être compressé de LZW à environ la moitié de sa taille originale.

LZSS

LZSS signifie Lempel Ziv Storer Szymanski et il a été développé et annoncé dans l’année 1982. Il s’agit d’un algorithme de compression de données qui améliore le LZ77. Ce processus de compression est réalisé en incluant une méthode qui permet de vérifier si une substitution diminue la taille du fichier. Si elle ne diminue pas, l’entrée est laissée dans sa forme originale. Il ne préfère pas non plus l’utilisation de caractères déviants, et préfère seulement utiliser des paires de longueur de décalage.

Cet algorithme est principalement utilisé pour l’archivage des fichiers dans différents formats tels que RAR ou ZIP, ou pour la compression de données réseau.

Il peut être qualifié de technique de codage par dictionnaire. LZSS tente de remplacer une chaîne de symboles par une référence à un emplacement du dictionnaire de la même chaîne. La principale différence entre LZ77 et LZSS est que dans LZ77, la référence au dictionnaire pouvait être plus longue que la chaîne qu’elle remplaçait. Dans LZSS, de telles références sont omises si la longueur est inférieure au point de « rupture ».

Deflate

Deflate est un format de fichier d’algorithme de compression de données sans perte qui fait usage d’une combinaison de LZSS et de codage de Huffman. Il a été conçu par Phil Katz au cours de l’année 1993. Le codage de Huffman est également un algorithme qui a été développé en 1952. Il peut être défini comme un algorithme de codage entropique qui vous aide à attribuer votre code en fonction de la fréquence du caractère.

Katz a également conçu l’algorithme original qui est utilisé pour construire les flux Deflate. Comme il a été indiqué dans le document RFC, un algorithme produisant des fichiers Deflate était largement considéré comme pouvant être mis en œuvre d’une manière qui n’était pas couverte par des brevets. Cela a conduit à son utilisation généralisée, en plus du format de fichier ZIP qui était le but principal de Katz pour le concevoir. Le brevet n’est plus disponible.

LZMA

LZMA signifie l’algorithme de la chaîne de Markov de Lempel Ziv et il a été conçu et publié en 1998. On peut également dire qu’il s’agit d’une modification du LZ77. Cette modification a été réalisée pour l’archiveur Zip avec un format .7z. La méthode de compression en chaîne est utilisée pour mettre en œuvre le LZ77 modifié au niveau du bit plutôt que de l’octet. L’apparition de sortie sera traitée davantage en utilisant le codage arithmétique pour effectuer plus de compression.

La performance des autres étapes de compression dépend de l’implémentation exacte. Cet algorithme de compression de données utilise un schéma de compression par dictionnaire un peu très similaire à l’algorithme LZ77 qui a été publié par Abraham Lempel et Jacob Ziv dans l’année 1977. Il présente également un taux de compression élevé et une taille variable du dictionnaire de compression. Tout en conservant une vitesse de décompression très similaire aux autres algorithmes de compression couramment utilisés.

LZMA2

LZMA2 a été conçu et publié en l’an 2009. Il peut également être défini comme la modification du LZMA. Il rend le LZMA meilleur en améliorant ses performances avec de plus grandes capacités de multithreading. Le LZMA2 offre également une meilleure gestion des données incompressibles. C’est un format conteneur simple qui peut inclure à la fois des données non compressées et des données LZMA, et ce, avec plusieurs paramètres d’encodage LZMA différents.

LZMA2 prend en charge la compression et la décompression multithread arbitrairement évolutive et la compression efficace des données partiellement incompressibles. Cependant, il peut avoir quelques problèmes de sécurité et peut être peu sûr et moins efficace que LZMA. En termes simples, cela peut être utile pour vous, mais oui, il n’est pas si sûr par rapport à LZMA.

Compression basée sur le perceptron multicouche (MLP)-

MLP peut être défini comme une technologie qui utilise plusieurs couches de neurones pour l’entrée, le traitement et donner des données de sortie. Il peut être mis en œuvre pour les tâches de réduction de la dimension et aussi la compression des données. L’algorithme basé sur MLP a été développé pour la première fois dans l’année 1988 et rejoint les processus déjà existants de:

• Codage binaire- codage standard à deux symboles.
• Quantification- problèmes d’entrée d’un ensemble continu à un ensemble discret.
• Transformation du domaine spatial – modifications pixel par pixel des données.

Pour la détermination du code binaire optimal, l’algorithme MLP utilise les sorties des processus ci-dessus dans un réseau neuronal de décomposition.

En outre, cet algorithme a été modifié avec des techniques intuitives qui ont permis une approximation précise des données complètement basée sur les données voisines par la rétro-propagation. Il peut vous être très utile dans la compression des données d’image et de vidéo.

Dee Coder- Deep Neural Network Based Video Compression

Deep Coder est défini comme un cadre basé sur le réseau neuronal convolutif (CNN). Cela rend la représentation d’une alternative à ces techniques de compression vidéo que nous utilisons depuis si longtemps. Pour les signaux prédictifs et résiduels, différents réseaux neuronaux convolutifs (CNN) sont apportés utilisés par ce modèle.

Il effectue l’encodage des cartes de caractéristiques dans le flux binaire avec l’utilisation de la quantification scalaire et d’un très ancien et traditionnel algorithme de compression de fichiers appelé encodage de Huffman. Il est affirmé que ce modèle est capable de fournir des performances supérieures par rapport à la norme de codage vidéo bien connue H.264/AVC.

Réseau neuronal convolutif (CNN) – Compression basée

Les CNN sont définis comme des réseaux neuronaux de différentes couches. Il est principalement utilisé pour la reconnaissance d’images et la détection de la caractéristique. Dès que vous l’appliquez à la compression, ces réseaux font appel à la convolution pour calculer la connexion entre les pixels voisins. Si nous le comparons avec les algorithmes basés sur les MLP, les CNN montrent de meilleurs résultats de compression qu’eux.

Cela vous fournit également des performances de super-résolution améliorées et une réduction des artefacts. En plus de cela, les algorithmes de compression de données basés sur CNN apportent des améliorations à la qualité des images JPEG. Cela se fait en réduisant le rapport signal-bruit de pointe et la similarité structurelle.

La compression basée sur le CNN peut également se réunir avec les performances de la norme de codage vidéo à haute efficacité. Ceci est fait avec l’utilisation de l’estimation de l’entropie. Il peut également être très utile pour vous dans l’exécution de la compression des fichiers.

Compression basée sur le Generative Adversarial Network (GAN)-

Les GAN peuvent être définis comme une alternative des réseaux neuronaux qui font usage de deux réseaux qui sont en concurrence. Ceci est fait pour la production d’analyses et de prédictions plus précises. Au cours de l’année 2017, les algorithmes basés sur les GAN ont été développés pour la première fois. Ces algorithmes de compression de données peuvent compresser les fichiers plus de deux fois et demie plus petits par rapport aux méthodes traditionnelles couramment utilisées, comme JPEG ou WebP.

Les algorithmes basés sur le GAN peuvent être utilisés pour la compression en temps réel avec un traitement parallèle utilisé ensemble. Cet algorithme fonctionne car il comprime complètement les images en se basant sur les caractéristiques les plus correspondantes.

Lorsque le décodage est effectué, sur la base des prédictions qui ont été faites par ces caractéristiques les images sont reconstruites. Si nous le comparons avec la compression basée sur CNN, La compression basée sur GAN produira des images de très haute qualité pour vous par l’élimination de la perte adversariale.

Prédiction par correspondance partielle (PPM)

La PPM est une technique de compression de données statistiques adaptatives basée sur la modélisation et la prédiction du contexte. Ces modèles utilisent un ensemble de symboles précédents dans le flux de symboles non compressé pour prédire le symbole suivant dans le flux. Les algorithmes PPM peuvent également être utilisés pour regrouper les données en groupements prédits dans l’analyse par grappes.
Le nombre de symboles précédents, n, détermine l’ordre du modèle PPM qui est désigné par PPM(n).

Des variantes non bornées où le contexte n’a pas de limites de longueur existent également et sont désignées par PPM. Si aucune prédiction ne peut être faite sur la base de tous les n symboles de contexte, une prédiction est tentée avec n – 1 symbole. Ce processus est répété jusqu’à ce qu’une correspondance soit trouvée ou qu’il ne reste plus de symboles dans le contexte. À ce moment-là, une prédiction fixe est effectuée.
Les implémentations de la compression PPM varient grandement dans d’autres détails. La sélection réelle des symboles est généralement enregistrée à l’aide d’un codage arithmétique, bien qu’il soit également possible d’utiliser un codage de Huffman ou même un certain type de technique de codage par dictionnaire.

Codage par longueur d’exécution (RLE)

RLW est une forme de compression de données sans perte dans laquelle les séries de données (séquences dans lesquelles la même valeur de données apparaît dans de nombreux éléments de données consécutifs) sont stockées comme une seule valeur de données et un seul compte, plutôt que comme la série originale. Ceci est plus utile sur les données qui contiennent beaucoup de telles séries.

Par exemple, les images graphiques simples telles que les icônes, les dessins au trait, le jeu de la vie de Conway et les animations. Il n’est pas utile avec les fichiers qui n’ont pas beaucoup de passages car il pourrait augmenter considérablement la taille du fichier.

RLE peut également être utilisé pour faire référence à un format de fichier graphique précoce pris en charge par CompuServe pour compresser les images en noir et blanc, mais il a été largement supplanté par leur format d’échange graphique (GIF) plus tardif. RLE fait également référence à un format d’image peu utilisé dans Windows 3.x, avec l’extension rule, qui est un Run Length Encoded Bitmap, utilisé pour compresser l’écran de démarrage de Windows 3.x.

bzip2

bzip2 est un programme de compression de données libre et gratuit qui utilise l’algorithme Burrows-Wheeler. Il ne compresse que des fichiers uniques et n’est pas un archiveur de fichiers. Il est développé par Julian Seward et maintenu par Federico Mena. Seward a publié la première version publique de bzip2, la version 0.15, en juillet 1996. La stabilité et la popularité du compresseur ont augmenté au cours des années suivantes, et Seward a publié la version 1.0 à la fin de l’année 2000.

Après une interruption de neuf ans des mises à jour du projet depuis 2010. Le 4 juin 2019, Federico Mena a accepté le statut de mainteneur du projet bzip2. bzip2 compresse les données dans des blocs de taille comprise entre 100 et 900 kB.

Il utilise la transformation Burrows-Wheeler pour convertir les séquences de caractères qui reviennent fréquemment en chaînes de lettres identiques. Il applique ensuite une transformation de déplacement vers l’avant et un codage de Huffman. L’ancêtre de bzip2, bzip, utilisait un codage arithmétique au lieu de Huffman. Le changement a été effectué en raison d’une restriction de brevet logiciel.

Codage de Huffman

Le code de Huffman est un type particulier de code à préfixe optimal qui est couramment utilisé pour la compression de données sans perte. Le processus de recherche ou d’utilisation d’un tel code procède à l’utilisation du codage de Huffman, un algorithme développé par David A. Huffman alors qu’il était étudiant en doctorat au MIT, et publié dans l’article de 1952 « A Method for the Construction of Minimum-Redundancy Codes ».

La sortie de l’algorithme de Huffman peut être vue comme une table de code à longueur variable pour coder un symbole source (tel qu’un caractère dans un fichier). L’algorithme dérive cette table de la probabilité ou de la fréquence d’occurrence estimée (poids) pour chaque valeur possible du symbole source.

Comme dans les autres méthodes de codage entropique, les symboles les plus courants sont généralement représentés en utilisant moins de bits que les symboles moins courants. La méthode de Huffman peut être mise en œuvre efficacement. Trouver un code en un temps linéaire au nombre de poids d’entrée si ces poids sont triés.

ZStandard

Zstandard (ou zstd) est un algorithme de compression de données sans perte développé par Yann Collet chez Facebook. Zstd est l’implémentation de référence en C. La version 1 de cette implémentation a été publiée en tant que logiciel libre le 31 août 2016.
Zstandard a été conçu pour donner un taux de compression comparable à celui de l’algorithme DEFLATE (développé en 1991 et utilisé dans les programmes originaux ZIP et gzip), mais plus rapide, notamment pour la décompression. Il est réglable avec des niveaux de compression allant de -5 (le plus rapide) à 22 (le plus lent en vitesse de compression, mais le meilleur taux de compression).

Zstd à son niveau de compression maximum donne un taux de compression proche de LZMA, LZAHM, et PPM. Il est plus performant que LZA, ou bzip2. Zstandard atteint la frontière de Pareto actuelle, car il décompresse plus rapidement que tout autre algorithme actuellement disponible avec un taux de compression similaire ou meilleur

Les dictionnaires peuvent avoir un impact important sur le taux de compression des petits fichiers, Zstandard peut donc utiliser un dictionnaire de compression fourni par l’utilisateur. Il propose également un mode d’entraînement, capable de générer un dictionnaire à partir d’un ensemble d’échantillons.

Conclusion

Ces algorithmes de compression de données vous aideront à optimiser la taille des fichiers. Différents types d’algorithmes de compression de données vous fourniront des résultats différents. Cependant, si vous ne trouvez pas le bon algorithme ici, vous pouvez jeter un coup d’œil à ce guide et affiner votre recherche. Les algorithmes ne manquent pas, mais vous devez être spécifique lorsque vous recherchez l’algorithme approprié pour votre projet.

J’espère que cet article vous a été utile pour choisir le meilleur algorithme de compression de données en fonction de vos besoins. Merci d’avoir lu cet article. Vous pouvez également consulter les meilleurs algorithmes de cryptage et de hachage.

Stay Tuned

.