Quels sont les algorithmes de compression sans perte couramment utilisés ?

Les algorithmes de compression sans perte couramment utilisés sont : 1. L'algorithme LZ77, qui est la base de nombreux autres algorithmes de compression sans perte ; 2. L'algorithme LZR, qui est un algorithme conçu pour améliorer LZ77 ; l'objectif est de devenir un algorithme de remplacement de temps linéaire pour LZ77 ; 4. Algorithme DEFLATE 5. Algorithme LZMA, etc.

La compression des données est le processus de réduction de la taille du fichier tout en conservant la même ou la plupart des données. Il fonctionne en éliminant les données inutiles ou en les réorganisant dans un format plus efficace. Lors de la compression des données, vous pouvez choisir d'utiliser des méthodes avec ou sans perte. Les méthodes avec perte effacent définitivement certaines données, tandis que les méthodes sans perte garantissent que toutes les données sont conservées. La méthode à utiliser dépend de la précision souhaitée pour votre fichier.

Cet article vous présentera 6 algorithmes différents de compression de données sans perte et 4 algorithmes de compression d'images/vidéo basés sur l'apprentissage profond.

6 algorithmes de compression de données sans perte

Les algorithmes de compression sans perte sont généralement utilisés à des fins d'archivage ou à d'autres fins de haute fidélité. Ces algorithmes vous permettent de réduire la taille du fichier tout en garantissant que le fichier est entièrement récupérable. Il existe de nombreux algorithmes de compression sans perte parmi lesquels choisir. Ce qui suit présente 6 algorithmes couramment utilisés :

1 LZ77

L'algorithme LZ77 a été publié en 1977. Comme base pour de nombreux autres algorithmes de compression sans perte, il utilise le concept de « fenêtres coulissantes ». Dans ce concept, LZ77 gère un dictionnaire. Le dictionnaire utilise des triplets :

Décalage : la distance entre le début de la phrase et le début du fichier

Longueur de course : le nombre de caractères qui composent la phrase

Caractère décalé : un marqueur indiquant une nouvelle phrase, le premier symbole dans le tampon de transfert une fois la correspondance terminée

Lorsque le fichier est analysé, le dictionnaire sera mis à jour en temps réel pour refléter les dernières données compressées et taille. Par exemple, si un fichier contient la chaîne "abbadabba", alors l'élément compressé dans le dictionnaire est "abb(0,1,'d')(0,3,'a')". Vous pouvez consulter le processus de démontage dans le tableau ci-dessous :

Dans cet exemple, les données compressées ne sont pas beaucoup plus petites que les données initiales. Mais généralement, cet effet de compression apparaîtra lorsque le fichier est très long.

2. LZR

LZR a été proposé par Michael Rodeh en 1981. Il a été développé sur la base du LZ77. Le but de cet algorithme est de devenir un algorithme de remplacement temporel linéaire du LZ77, mais après encodage, le pointeur Udell peut pointer vers n'importe quel décalage du fichier, ce qui signifie qu'il nécessite une consommation de mémoire considérable, donc les performances ne sont pas aussi bonnes que celles du LZ77. .

3. LZSS

LZSS, nom complet Lempel-Ziv-Storer-Szymanski, a été proposé en 1982. C'est également un algorithme conçu pour améliorer le LZ77. Il introduit une méthode pour détecter si la taille du fichier est réellement réduite. Si l'effet de compression ne peut pas être obtenu, le format d'entrée d'origine sera conservé. LZSS supprime également l'utilisation de caractères de décalage, en utilisant uniquement les paires . Cet algorithme de compression est largement utilisé dans les formats d'archives tels que RAR et dans la compression des données réseau.

4. DEFLATE

L'algorithme DEFLATE a été proposé en 1993. L'auteur est Phil Katz. Cet algorithme combine le préprocesseur LZ77 ou LZSS avec le codage Huffman. Le codage de Huffman est une loi proposée en 1952. Il s'agit d'un codage entropique qui attribue des codes principalement en fonction de la fréquence d'apparition des caractères.

5. LZMA

L'algorithme LZMA, le nom complet est L'algorithme de chaîne de Markov de Lempel-Ziv (LZMA), a été proposé en 1998 et est une version améliorée de LZ77, visant à réaliser 7-ZIp. archives de fichiers. Il utilise une méthode de compression en chaîne qui applique un algorithme LZ77 modifié au niveau des bits plutôt qu'au niveau des octets. La sortie de cet algorithme de compression est ensuite traitée par codage arithmétique pour une compression ultérieure ultérieure. En fonction de l'implémentation spécifique, des étapes de compression supplémentaires peuvent être introduites.

6. LZMA2

L'algorithme LZMA2 a été proposé en 2009 et est une version améliorée de LZMA. Il améliore les performances de LZMA en termes de capacités multithread et améliore les performances de traitement des données de type incompressible.

4 algorithmes de compression d'images/vidéos basés sur le deep learning

En plus des algorithmes de compression statique présentés ci-dessus, il existe également des algorithmes de compression basés sur le deep learning parmi lesquels choisir .

1. Algorithme de compression basé sur le perceptron multicouche

La technologie Multi-Layer Perceptron (MLP) utilise plusieurs couches de neurones pour acquérir, traiter et produire des données. Il peut être appliqué aux tâches de réduction de dimensionnalité des données et à la compression des données. Le premier algorithme basé sur MLP a été proposé en 1988 et a été appliqué à :

Codage binaire - codage standard à deux symboles

Quantification - restriction des ensembles continus aux ensembles discrets Entrée

Transformation dans un domaine spécifique - modifications des données au niveau des pixels

L'algorithme MLP utilise la sortie de l'étape précédente du réseau neuronal de décomposition pour déterminer la meilleure combinaison de codes binaires. Plus tard, des techniques de prédiction sont utilisées pour optimiser cette méthode. Les techniques de prédiction peuvent améliorer la précision des données sur la base de données adjacentes grâce à la rétropropagation.

2. DeepCoder -- réseau neuronal profond basé sur la compression vidéo

DeepCoder est un framework basé sur Convolutional Neural Network (CNN), qui constitue une alternative à la technologie de compression vidéo traditionnelle. Ce modèle utilise des CNN distincts pour le signal prédit et le signal résiduel. Il utilise des techniques de quantification scalaire et un algorithme de compression de fichiers traditionnel – le codage de Huffman – pour mapper les fonctionnalités de codage dans un flux binaire. On pense généralement que les performances de ce modèle sont meilleures que celles de la célèbre spécification de codage vidéo H.264/AVC.

3. Algorithme de compression basé sur CNN

CNN est un réseau neuronal en couches, généralement utilisé pour la reconnaissance d'images et la détection de fonctionnalités. Lorsqu'ils sont appliqués à la compression, ces réseaux de neurones utilisent des opérations de convolution pour calculer les corrélations entre pixels adjacents. CNN démontre de meilleurs résultats de compression que les algorithmes basés sur MLP, améliore les performances de super-résolution et réduit les artefacts. De plus, la compression basée sur CNN améliore également la qualité des images JPEG car elle réduit le rapport signal/bruit (PSNR) et la similarité structurelle (SSIM). La compression basée sur CNN atteint également les performances HEVC en utilisant des méthodes d'estimation d'entropie.

4. Algorithme de compression basé sur le réseau contradictoire génératif (GAN)

Le GAN est un type de réseau neuronal qui utilise deux réseaux neuronaux pour se faire concurrence afin de produire une analyse et des prévisions plus précises. Le premier algorithme de compression basé sur le GAN a été proposé en 2017. Le taux de compression des fichiers de ces algorithmes est 2,5 fois supérieur à celui d'autres méthodes courantes (telles que JPEG, WebP, etc.). Vous pouvez utiliser des méthodes basées sur GAN pour obtenir une compression en temps réel en parallélisant le traitement. Le principe principal est de compresser les images en fonction des fonctionnalités les plus pertinentes. Lors du décodage, l'algorithme reconstruit l'image en fonction de ces caractéristiques. Par rapport aux algorithmes basés sur CNN, les algorithmes de compression basés sur GAN peuvent produire des images de meilleure qualité en éliminant les pertes contradictoires.

Résumé

Les algorithmes de compression peuvent vous aider à optimiser la taille du fichier. Différents algorithmes ont des résultats différents. Cet article décrit brièvement 6 algorithmes de compression statiques sans perte et 4 algorithmes de compression basés sur le deep learning. Bien entendu, si aucun de ces algorithmes ne s’applique à votre scénario, vous pouvez consulter cet article pour trouver un algorithme adapté à votre scénario. Il existe de nombreux algorithmes, il y en a toujours un qui vous convient !

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!