LZW
Ce calculateur compresse/décompresse une chaîne en utilisant l'algorithme de Lempel-Ziv-Welch (LZW).
Cette page existe grâce aux efforts des personnes suivantes :
Anton
| |
Gaulthier Marrel
| |
 | Timur
|
Les calculateurs de cet article sont utilisés pour compresser et décompresser une chaîne en utilisant l'algorithme LZW. La méthode LZW est simple et fiable, elle ne nécessite pas le stockage d'un dictionnaire - le dictionnaire est généré dynamiquement durant la compression et la décompression.
Pour étudier les opération de l'algorithme, cochez la case "Montrer les détails" - les calculateurs afficheront le journal du travail et les dictionnaires de phrases générés.
Compression de texte LZW
Le vidage binaire ou fichier binaire généré par le calculateur précédent peut être passé dans le calculateur suivant, ce qui restaurera la chaîne initiale. Il est nécessaire de régler la méthode de formation du dictionnaire source de la même manière que pour le calculateur de compression. (Choisissez le même codage ou spécifiez explicitement le même dictionnaire).
Décompression LZW
- Déplacez des fichiers ici
Algorithme de Lempel-Ziv-Welch
L'algorithme de compression sans perte LZ78 a été publié en 1978 par Abraham Lempel et Jacob Ziv puis ensuite modifié par Terry Welch en 1984. Après la publication de Welch, l'algorithme a été nommé LZW d'après les initiales des noms des auteurs (Lempel, Ziv, Welch). L'algorithme a été breveté, mais tous les brevets ont désormais expiré, ce qui nous donne la superbe opportunité de publier notre implantation de celui-ci ici.
Description de l'algorithme LZW
- Créer le dictionnaire initiale contenant tous les caractères possibles.
- Mettre le premier caractère dans la phrase saisie W.
- Lire le caractère suivant K.
- Si EOF renvoyer W, alors :
Si la phrase WK est déjà dans le dictionnaire, W ⟵ WK. Aller à 3 ,
Sinon renvoyer le code de W , ajouter WK au dictionnaire, W ⟵ K. Aller à 3.
Pour décoder les données générées de cette manière, vous n'avez pas besoin de stocker le dictionnaire, il est recréé par lui-même lors du processus de décompression
- Créer le dictionnaire initiale contenant tous les caractères possibles.
- Mettre le premier code dans la phrase saisie W.
- Lire le code suivant K.
- Si EOF renvoyer le caractère ayant le code W, sinon :
Si la phrase avec le code WK n'est pas dans le dictionnaire, renvoyer la phrase avec le code W et ajouter la phrase avec le code WK au dictionnaire.
Sinon, assigner le code WK à la phrase saisie et aller à 3.
L'article initial de Welch était destiné à coder une phrase dans un dictionnaire avec une taille de code fixée à 12 octets, mais pour les petits messages cette approche peut même accroître la longueur du message codé comparée au texte initial. Ainsi, il est assez fréquent d'utiliser la longueur de code dynamique, qui change à chaque fois que la limite du dictionnaire est atteinte.
Gestion de la croissance de la taille du dictionnaire
Dans l'algorithme de compression décrit ci-dessus, la taille du dictionnaire n'est pas limitée. En pratique, ceci peut mener à des contraintes de ressources lors de la compression de grandes quantités de données.
Il y a des modifications connus pour l'algorithme afin d'essayer de résoudre ce problème :
- LZC - l'implantation de l'algorithme de l'utilitaire de compression limite la taille maximale du dictionnaire à 16 octets. Lorsque la taille maximale est atteinte, le dictionnaire arrête de changer. L'algorithme contrôle le rapport de compression, et s'il se dégrade considérablement, il réinitialise le dictionnaire et commence à en former un nouveau.
- LZT - sur le dépassement, élimine la phrase du dictionnaire qui n'a pas été utilisée depuis la plus longue période
Nos caractéristiques d'implantation
Dictionaire initial
Nos calculateurs implantent un vocabulaire qui ne cesse d'augmenter, ce qui peut être trop coûteux pour les très grosses données. La taille des codes des phrases commencent à 8 octets pour le dictionnaire initial spécifié par le codage standard, voire moins pour un dictionnaire saisi à la main. Dans le second cas, la taille des codes des phrases est le nombre minimum d'octets nécessaires pour exprimer le nombre de caractères dans le dictionnaire. Longueur de l'octet.
Codages multi-octets
Certains codages peuvent prendre plus de 1 octet par caractère, par exemple le codage UTF-8 contient des caractères de longueurs variant de 1 à 4 octets. Dans tous les cas, le dictionnaire contiendra 256 éléments avec des codes de 0 à 255, peu importe le codage que vous choisissez.
Pour les codages multi-octets, un dictionnaire généré dynamiquement aura l'air plutôt exotique - ses phrases seront inévitablement composées de différentes parties de caractères adjacents. Dans ce cas, pour plus de clarté dans les tableaux de résultat, nous utilisons un marqueur d'octet manquant (par défaut c'est le caractère '~'). Par exemple, lors de la compression de la phrase "9 €", représentée dans le codage in UTF-8, le dictionnaire dynamique peut être rempli avec des combinaisons des caractères suivants :
9 - neuf,
' ' - espace,
€~~ - premier octet du symbole euro,
~€~ - deuxième octet du symbole euro,
~~€ - troisième octet du symbole euro,
€~ - les deux premiers octets du symbole euro,
~€ - les deux derniers octets du symbole euro,
€ - les trois octets du symbole euro.
Nous avons introduit la description de caractère uniquement par souci de commodité, n'oubliez pas que les parties constituantes de nombreux caractères multi-octets sont juste de 8 octets chacun, et elles peuvent être identiques pour différents caractères.
par exemple :
€ ~~ - le premier octet du symbole euro, son code en utf-8 = 226
₽ ~~ - le premier octet du symbole rouble, son code en utf-8 = 226.
Zéros à droite
L'algorithme de compression peut produire une gamme d'octets dont la taille n'est pas un multiple de 8. Dans ce cas, le calculateur de compression remplit la fin avec des octets zéro. Comme notre implantation utilise une taille variable de codes de phrase, cette approche peut pauser problème si le dictionnaire initial fixé manuellement est très petit.
Dans cet exemple le message final ne fera que 18 octets et 6 octets devront être complétés par des zéros pour stocker tout le message dans un fichier binaire.
Comme les paramètres spécifiés, la taille du code de la phrase n'est que de 4 octets, alors les mots supplémentaires seront lus durant la décompression, et si nous devons créer le dictionnaire initial avec le code pour le premier caractère = 0, alors les caractères supplémentaires seront décompressés.
Nous résolvons ce problème en ajoutant un caractère nul au début du dictionnaire, qui est souvent interprété comme la fin d'une chaîne.
Lors de l'utilsation du codage pour le dictionnaire initial, ce problème n'aura jamais lieu, puisque la taille du code de la phrase est toujours d'au moins 8 octets.
commentaires