Après avoir regardé le drame HBO « Silicon Valley », j’ai toujours été intéressé par les algorithmes de compression. Richard Hendricks et son algorithme de compression intermédiaire sont bien sûr faux, mais après avoir cherché Google, j’ai découvert qu’il existe un génie d’algorithme de compression dans la vraie vie.
Yann Collet a inventé l’algorithme de compression LZ4 en 2011. Bien sûr, l’algorithme LZ4 n’est pas aussi impressionnant que le middle out, mais il est connu pour sa vitesse de compression invincible et sa vitesse de décompression plus rapide lorsque c’est garanti d’un certain taux de compression.
Je ne vais pas entrer dans les détails ici sur l’évaluation de sa vitesse de compression, si cela vous intéresse, vous pouvez lire cet article comparatif :La connexion hyperlientérée est visible.
Également jointe est l’adresse GitHub de LZ4 :La connexion hyperlientérée est visible.
Cet article se concentre sur l’explication du principe de l’algorithme de compression LZ4. Un grand dieu a déjà écrit une explication de l’algorithme LZ4 :La connexion hyperlientérée est visible.Mais quand j’étudiais avant, j’ai trouvé cet article peu accueillant pour les débutants, alors j’en ai commencé un autre pour les novices comme moi.
Si vous résumez en une phrase, LZ4 est un LZ77 qui stocke un dictionnaire avec une table de hachage de taille 16k et simplifie la récupération.
LZ4 est un algorithme de compression sans perte qui offre une vitesse de compression de > 500 Mo/s par cœur, pouvant être adaptée à des processeurs multicœurs. Il dispose de décodeurs extrêmement rapides avec des vitesses de plusieurs Go/s par cœur, atteignant souvent les limites de vitesse de la RAM sur les systèmes multicœurs.
La vitesse peut être ajustée dynamiquement, en sélectionnant un facteur d'« accélération » qui échange le taux de compression contre une vitesse plus élevée. En revanche, une dérivée à haute compression LZ4_HC est également prévue pour augmenter la compression au détriment du temps CPU. Toutes les versions ont la même vitesse de décompression.
Alors, qu’est-ce que LZ77 ?
Compression et principe du LZ77
LZ77 est un algorithme qui applique un dictionnaire pour la compression. En termes simples, il s’agit de laisser le programme observer (voir le dictionnaire) si les données actuellement vues sont dupliquées avec les précédentes, et si oui, nous enregistrons la distance (décalage) et la longueur des champs dupliqués pour remplacer les champs dupliqués et compresser les données.
référenceLa connexion hyperlientérée est visible.
Pour une chaîne de lettres A A B B B C, lorsque le second A est lu, le programme enregistre (1,1) (1 chiffre du précédent, longueur 1), et de même, lorsque le second B est lu, le programme sauve (2,1) (distance 2, longueur 1).
Mais si la chaîne est plus longue et que le programme enregistre les données dans le dictionnaire en permanence, la recherche de champs en double devient extrêmement longue, car dans le pire des cas, le programme parcourt tout le dictionnaire à chaque nouvelle lettre lue. LZ77 utilise une méthode de fenêtre coulissante pour résoudre ce problème.
Similaire au point de départ du TCP utilisant une fenêtre coulissante, une fenêtre glissante peut réduire la surface du cache pour éviter de traiter trop de données mises en cache en même temps. Dans LZ77, le dictionnaire n’augmente pas tout le temps, mais supprime les premiers caractères ajoutés lorsqu’il dépasse la taille maximale spécifiée par le dictionnaire, afin de garantir que la taille du dictionnaire reste toujours maintenue à la taille maximale spécifiée.
Supposons que la longueur du dictionnaire soit 3
| dictionnaire |
| A | A B C B B A B C
Sortie (0,0,A)
| A A | B C B B A B C
Sortie(1,1)
| A A B | C B B A B C
Production (0,0,B)
A | A B C | B B A B C
Sortie (0,0,C)
A A | B C B | B A B C
Sortie(2,1)
L’autre partie de la fenêtre coulissante est le cache à rechercher (le tampon de regard n’a pas de traduction officielle). Le cache à rechercher est la partie non compressée de la longueur la plus proche du dictionnaire. L’algorithme LZ77 correspondra à la chaîne la plus longue de cette partie du caractère qui est identique au dictionnaire. L’exemple précédent peut être considéré comme un tampon anticipé de 1.
Supposons que la longueur du dictionnaire soit 5 et que la taille du cache à rechercher soit 3
| dictionnaire | Tampon de prévision |
A | A B C B B | A B C |
Sortie (5,3)
La plus longue chaîne correspondante est ABC
Processus complet de compression :
Supposons que la longueur du dictionnaire soit 5 et que la taille du cache à rechercher soit 3
| dictionnaire | Tampon de prévision |
| A A B | C B B A B C
Sortie (0,0,A)
| A | A B C | B B A B C
Sortie(1,1)
| A A | B C B | B A B C
Production (0,0,B)
| A A B | C B B | A B C
Sortie (0,0,C)
| A A B C | B B A | B C
Sortie(2,1)
| A A B C B | B A B | C
Sortie(1,1)
A | A B C B B | A B C |
Sortie (5,3)
A A B C | B B A B C | 。。。 |
Il n’est pas nécessaire de sauvegarder le dictionnaire dans le fichier de sortie du compresseur, car le programme de décompression restaure le dictionnaire en faisant correspondre les unités de sortie.
Procédé de décompression
L’un des grands avantages de l’algorithme LZ77 est qu’il est très rapide à décompresser.
Si la première unité correspondante est (0,0,A), alors A est en sortie.
La seconde unité correspondante est (1,1), qui copie le bit précédent de la chaîne de sortie, et produit A si la longueur de copie est 1.
。。。
Si la dernière unité correspondante est (5,3), alors regardez 5 bits dans la chaîne de sortie de copie, et si la longueur de copie est 3, alors sortissez A, B, C.
La partie la plus chronophage de la compression de l’algorithme LZ77 est de trouver le caractère correspondant le plus long dans le cache à rechercher dans le dictionnaire. Si le dictionnaire et la cache à rechercher sont trop courts, les chances de trouver une correspondance sont minces. Par conséquent, LZ4 a modifié l’algorithme d’appariement pour LZ77.
Tout d’abord, le dictionnaire de l’algorithme LZ4 est une table de hachage. La clé du dictionnaire est une chaîne de 4 octets, chaque touche correspond à un seul emplacement, et la valeur dans la fente est la position de cette chaîne.
Au lieu de chercher dans le cache, LZ4 lit quatre octets à la fois depuis le fichier d’entrée, puis cherche l’emplacement correspondant à la chaîne dans la table de hachage, qui sera désormais désignée sous le nom de chaîne présente.
Si vous avez atteint les 12 derniers caractères, mettez-les directement dans le fichier de sortie.
S’il n’y a pas de valeur assignée dans l’emplacement, cela signifie que les quatre octets apparaissent pour la première fois, ajoutent ces quatre octets et positions à la table de hachage, puis continuent la recherche.
S’il y a une affectation dans l’emplacement, cela signifie que nous avons trouvé une valeur correspondante.
Si la valeur dans la fente plus la taille de la fenêtre cursante < la position du caractère courant, alors la position de correspondance dépasse la taille du bloc, et le programme met à jour la valeur dans la case de hachage à la position de la chaîne courante.
LZ4 vérifiera s’il y a eu un conflit de hachage. Si les 4 octets dans l’emplacement ne sont pas identiques à la chaîne courante, il doit y avoir un conflit de hachage. Le xxhash de l’auteur est également connu pour son efficacité, mais les conflits sont inévitables. En cas de conflit, le programme met également à jour la valeur dans l’emplacement de hachage à la position actuelle de la chaîne
Enfin, nous pouvons confirmer que la correspondance est valide, et le programme continuera à vérifier si les caractères suivants dans la chaîne correspondante sont les mêmes. Enfin, copiez tous les caractères de la fin de la correspondance valide précédente au début de cette correspondance valide dans le fichier compressé, puis ajoutez la séquence de correspondance de cette correspondance valide.
Collet appelle les unités correspondantes sorties par les séquences LZ4, qui constituent le fichier compressé LZ4. Les détails sont les suivants :
Le jeton mesure 1 octet, les 4 premiers mots étant la longueur littérale et les 4 derniers la longueur de correspondance. Comme mentionné précédemment, tous les caractères de la fin de la correspondance valide précédente jusqu’au début de cette correspondance valide seront copiés dans un fichier compressé, ces fichiers non compressés sont littéraux, et leur longueur est la longueur littérale.
Littéralement suivie d’une déviation. Comme dans LZ77, la déviation et la longueur de la correspondance font référence à la longueur de la chaîne courante par rapport à sa correspondance, et la longueur de la correspondance correspondance de la chaîne actuelle à la même chaîne dans le dictionnaire. En décompression, il faut le parcourir pour trouver la chaîne à copier et la longueur à copier. L’ampleur de la déviation est fixe.
Dans la figure, longueur littérale+ et longueur correspondante+ signifient que si les mots littéraux ou de longueur correspondante 4 dans le jeton ne suffisent pas, ils continueront d’augmenter dans les positions correspondantes. 4 mots peuvent représenter de 0 à 15, et s’il y en a plus, ajouter un octet, c’est-à-dire ajouter 255 à la taille jusqu’à ce que l’octet soit inférieur à 255. Dans la longueur correspondante, 0 représente 4 octets.
Les 12 derniers octets se terminent littéralement parce qu’ils ont été copiés directement.
Regardons le code (Python est plus abstrait)
Résumé Cela dit, je n’ai toujours pas résumé pourquoi le LZ4 est si rapide. Commençons par comparer la recherche dans le dictionnaire entre LZ77 et LZ4. Le LZ77 natif recherche des dictionnaires en recherchant la plus grande correspondance dans le cache à rechercher et dans le dictionnaire. C’est un problème de recherche de la plus grande chaîne identique dans deux chaînes. Si nous n’utilisons pas la programmation dynamique, au pire nous devons considérer toutes les sous-chaînes d’une chaîne puis les associer dans une autre chaîne. Si × utilisons la programmation dynamique, nous utiliserons une table pour conserver la plus longue correspondance dans la dynamique, ce qui ne nous permettra de compléter la correspondance que dans le cas de O(m*n). Et cela concerne uniquement une paire de caches de recherche et de dictionnaires. Dans le pire des cas, s’il n’y a pas de correspondances, alors LZ77 devra compter (la longueur de l’ensemble du fichier - la longueur du cache à rechercher) comme de nombreux problèmes de correspondance de ce type. LZ4 utilise en réalité un niveau plus large de programmation dynamique : il stocke 4 octets et leurs positions dans une table de hachage, puis correspond à chaque fois 4 octets de données pour vérifier si les valeurs de la table de hachage sont valides. Après avoir trouvé une valeur correspondante valide, si vous regardez les données de suivi des deux ensembles de valeurs correspondantes, vous pouvez aussi trouver sa correspondance la plus longue. Puisque chaque clé de la table de hachage LZ4 ne correspond qu’à un seul emplacement, le travail de recherche, d’ajout et de modification de la table de hachage ne nécessite que O(1). Si d’autres correspondances sont trouvées après l’appariement, davantage de comparaisons de groupes sont nécessaires, mais dans le temps total, ces comparaisons remplaceront le temps supplémentaire de recherche dans la table de hachage, donc le temps total de l’algorithme LZ4 n’est que O(n). Je dois admirer la beauté de l’algorithme de Collet ! Pour accélérer encore plus l’algorithme, Collet fixe la taille par défaut de la table de hachage à 16k, ce qui est recommandé de ne pas dépasser 32k, afin de pouvoir être intégrée dans le cache L1 de presque tous les processeurs (Intel). Tout le monde sait que la vitesse et le ratio mémoire du cache L1 du CPU sont très différents, il n’est donc pas surprenant que LZ4 vole vite, sans parler du fait que l’équation de hachage utilisée dans la table de hachage de LZ4 reste la xxhash la plus rapide. Bien sûr, un tel design présente ses inconvénients. Plus la table de hachage est petite, moins elle a de clés. Cela signifie que d’autres conflits de hachage vont survenir, ce qui est inévitable. Et plus il y a de collisions de hachages qui signifie moins de correspondances. Et une table de hachage plus petite signifie aussi une fenêtre glissante plus petite, ce qui signifie que plus de correspondances seront jetées car elles sont trop éloignées. Moins de correspondances représentent un taux de compression plus faible, ce qui explique pourquoi le LZ4 a un taux de compression moins prononcé. Looking Ahead LZ4 propose une large gamme de scénarios d’application. Tout comme la sortie centrale était utilisée en VR dans la Silicon Valley, LZ4 peut augmenter l’utilisation de la bande passante en apportant moins d’E/S au prix d’une latence très faible grâce à sa très grande vitesse de compression. Il y a aussi une petite hypothèse : s’il y a un processeur avec un cache plus grand au niveau 1, le LZ4 peut-il augmenter le taux de compression sans compromettre la vitesse ?
Langue source:La connexion hyperlientérée est visible. |
Publié sur 03/01/2022 13:54:23
|
|
|
|
