Les Algorithmes de compression ZIP & RAR !
Les Algorithmes de compression ZIP & RAR ! - Tutoriels - Windows & Software
Marsh Posté le 12-01-2007 à 10:05:08
>> BWT<<
Fichier ZIP 
ui
Fichier RAR : Non
Historique:
La transformée de Burrows-Wheeler, couramment appelée BWT (pour Burrows-Wheeler Transform) est une technique de compression de données. Elle fut inventée par Michael Burrows et David Wheeler. Cette technique fut rendue publique en 1994, suite à de précédents travaux de Wheeler en 1983. Il ne s'agit pas à proprement parler d'un algorithme de compression, car aucune réduction de taille n'est effectuée, au contraire (voir ci-dessous), mais bien d'une méthode de réorganisation des données : les probabilités pour que des caractères identiques initialement éloignés les uns des autres se retrouvent côte à côte sont alors augmentées. Cette technique n'est pas très utilisée, mais l'on peut cependant remarquer qu'elle est présente dans le format bzip2 qui est actuellement l'un des formats offrant le plus grand quotient de compression.
Théorie:
Comme nous l'avons dit, la transformée de Burrows-Wheeler ne compresse pas les données, elle se contente de les réorganiser de manière à obtenir un plus petit taux de compression.
Tout d'abord, la chaîne de caractères à coder doit être copiée dans un tableau carré en décalant la chaîne d'un caractère vers la droite à chaque nouvelle ligne. Ces lignes sont ensuite classées par ordre alphabétique. Nous savons que, grâce au décalage, chaque dernière lettre de chaque ligne précède la première lettre de la même ligne, sauf pour la ligne originale dont on notera la position. De plus, comme les lignes sont rangées par ordre alphabétique, on peut retrouver la première colonne du tableau grâce à la dernière colonne.
Application :
Prenons un exemple. Supposons que la chaîne à coder soit « TEXTE ». On réalise tout d'abord le tableau de 5 lignes (nombre de lettre). Toutes les lettres sont décalées vers la droite. Une fois terminé cette opération, on trie par ordre alphabétique.
Pour la décompression, il est nécessaire de garder en mémoire la position de la chaîne originale, ici 4. Le texte codé est donc la dernière colonne, soit : « 4TTXEE »
Conclusion :
Cette transformation n'apporte aucun gain de compression immédiat, au contraire, car il est nécessaire de transmettre des informations supplémentaires pour le décodage. Cependant, Burrows et Wheeler recommandent ensuite d'utiliser un algorithme de type MTF. Ainsi, la chaîne possédant de nombreuses répétitions de caractères contiendra beaucoup de 0. Ceci assure avec un algorithme de type codage de Huffman un quotient de compression élevé.
>> HUFFMAN<<
Fichier ZIP : Oui
Fichier RAR : Non
Historique:
Lalgorithme de Huffmann a été décrit pour la première fois en 1952. Lalgorithme crée des codes de longueurs variables en fonction des probabilités fournies par le modèle, ou la connaissance de la séquence complète.
La méthode de compression Huffman consiste à diminuer au maximum le nombre de bits utilisés pour coder un fragment dinformation. Prenons lexemple dun fichier de texte : Le fragment dinformation sera un caractère ou une suite de caractères
Lalgorithme de Huffman se base sur la fréquence dapparition dun fragment pour le coder : plus un fragment est fréquent, moins on utilisera de bits pour le coder. On peut remarquer que les voyelles sont beaucoup plus fréquentes, dans notre fichier texte, que les consonnes
Pour pouvoir compresser puis décompresser linformation, on va donc devoir utiliser une table de fréquences et deux choix soffrent à nous : calculer une table et lintégrer au fichier ou utiliser une table générique intégrée dans la fonction de compression.
- 1 : La compression est meilleure. Elle nécessite le calcul dune table de fréquences et le fichier sera plus important également du fait de la présence de cette table dans le fichier
- 2 : La compression sera plus rapide puisque elle naura pas à calculer les fréquences, par contre lefficacité de la compression sera moindre et le gain obtenu par la première méthode (ratio de compression + taille de la table) peut être supérieur à celui de la deuxième (ratio de compression).
Théorie:
Le code de Huffman est le code irréductible optimal. Il sappuie sur trois principes :
P = probabilités
N = Fréquence
- Si pj > pi alors ni = nj,
- Les deux mots les moins probables ont des longueurs égales.
Ces derniers sont écrits avec les mêmes n max-1 premiers caractères.
En utilisant itérativement cette procédure, on construit les mots-codes Mi des messages mi.
Exemple :
On considère la source S = {m1, m2,
, m8} munie de la loi de probabilité : p1 = 0,4 ; p2 = 0,18 ; p3 = p4 = 0,1 ; p5 = 0,07 ; p6 = 0,06 ; p7 = 0,05 ; p8 = 0,04.
On place ces probabilités par ordre décroissant dans la colonne pi(0) du tableau ci-dessous.
On remarque que dans la colonne pi(0) les probabilités des messages m7 et m8 sont les plus faibles. On les somme alors puis on réordonne, toujours par ordre décroissant, les probabilités afin de créer la colonne pi
De manière générale, on somme les deux probabilités les plus faibles de la colonne pi(k), puis on réordonne les probabilités par ordre décroissant afin dobtenir la colonne pi(k+1). Finalement on a donc le tableau suivant.
On attribue les bits 0 et 1 aux deux derniers éléments de chaque colonne :
Pour chaque message mi, on parcourt le tableau de gauche à droite et on détecte dans chaque colonne On propose par exemple de déterminer le mot code M6 du message m6. On détecte donc toutes les transformations incluant m6 (représentées en bleu), les bits quelles rencontrent (représentées en vert) :
Le mot-code M6 est alors obtenu par simple lecture de droite à gauche des bits contenus dans les rectangles verts : 0 1 0 1. En procédant de même pour chacun des messages, on obtient :
La longueur moyenne des mots-codes vaut donc :
On peut comparer cette grandeur avec lentropie H de la source :
Lefficacité h du code de Huffman pour cet exemple est donc de 2,61 / 2,552 = 97,8 %.
À titre de comparaison, il faut 3 bits pour coder en binaire naturel 8 messages différents
(23 = 8). Pour cet exemple, lefficacité du code binaire naturel est donc de seulement 3 / 2,552 = 85 %.
Application :
Soit un texte possédant 100 lettres, dans lesquelles il y a 44 fois la lettre 'e', 21 fois la lettre 'a', 14 fois la lettre 'c', et 7 fois les lettres 'b' 'd' et 'f'.
Construction de larbre de Huffman :
Afin de coder les caractères, nous allons construire un arbre binaire. On rappelle, qu'un arbre est constitué d'une racine, d'un ou plusieurs nuds, et de feuilles. On appelle racine le père de tous les nuds (la racine
est aussi un nud). Un nud représente une 'branche' de l'arbre. Une feuille est un nud qui n'a pas de fils. Nous allons voir que la valeur binaire d'un caractère codé par Huffman n'est en fait que le chemin allant de la racine à la feuille codant ce caractère. Ainsi, lors de la lecture d'une valeur binaire par Huffman, un '0' signifie aller au nud fils gauche", et un '1' signifie "aller au nud fils droite".
Voilà le tableau résumant la compression :
Conclusion :
Cet algorithme est gratuit, simple et efficace. Grâce à ça il est beaucoup utilisé aujourdhui. Cest un avantage non négligeable pour une entreprise davoir accès à du code libre. Il est utilisé pour le JPEG et MPEG en particulier. Malgré son ancienneté, cette méthode est toujours remise au goût du jour, et offre des performances appréciables. En effet, beaucoup de recherches en algorithmique ont permis d'améliorer les fonctionnalités de la méthode Huffman de base, par exemple les arbres binaires, les arbres équilibrés, etc.
-----------------------------------
ROLES DES MATHEMATIQUES
-----------------------------------
Les mathématiques ont un rôle prépondérant dans les algorithmes et systèmes de codage utilisés. Prenons Huffman, il utilise les probabilités. Le système de codage LZ toutes dérivées confondus utilise le système de la comparaison.
Enfin, un pré-système de codage (LZW) utilise les matrices, énormément utilisées aujourdhui, dans bon nombre dapplication. Il sen sert pour classer le texte et faire le tri là-dessus
Dautres fonctions mathématiques sont mises en uvre, comme laddition, la soustraction, la multiplication, la division, la conversion hexadécimal, ASCII, binaire.
-----------------------------------
CONCLUSION
-----------------------------------
Deux logiques saffrontent. Le Libre et le payant. Certains systèmes de codage comme le système Huffman étaient libres daccès, dautres étaient propriétaires. Grâce à ça des applications ont pu voir le jour (7-ZIP et Winrar).
Un partie des systèmes de codage a été créée il y a une trentaine dannées. Le plus vieux remonte à prés de soixante ans en arrière. Depuis, peu sont sorti ; ce qui prouve bien lefficacité de ces systèmes de codage crée aux balbutiements de linformatique (surtout grand public).
Résumons :
- LZ : Lalgorithme LZ est aujourdhui considéré comme la méthode de compression la plus efficace et une des plus connues. Avantage : rapide.
- LZMA : Taux de compression élevé, vitesse de compression très rapide, utilise les nouvelles technologies (multithreading par exemple)
- BWT : Ce nest pas un algorithme de compression à proprement parler. Cest une méthode pour organiser qui fonctionnera avec un algorithme ; Huffman par exemple.
- Huffman : Cet algorithme a la chance dêtre rapide en plus dêtre gratuit. Les créateurs du format JPEG lutilisent.
Le choix de tel ou tel système de codage, se fera sur le besoin. Par exemple sur Windows 98 ; LZMA ne sera pas au maximum de ses capacités. Les éditeurs dapplications comme Winrar lont bien compris. En fonction du type de fichier, de la machine, de la configuration, des besoins économiques et matériels, ils utiliseront un algorithme plus quun autre, mieux adapté au type de fichier à compresser.
Il ny a pas de choix à faire, juste à sadapter aux contraintes et demandes des utilisateurs.
-----------------------------------
LIENS EXTERNES
-----------------------------------
http://www.maximumcompression.com/
Voilà, j'espère vous avoir un peu plus éclairé sur les algorithmes de crypthage utilisés pour les fichierss ZIP & RAR !
A bientôt
Cvb
Message édité par cvb le 12-01-2007 à 21:24:52
![[:delarue]](https://forum-images.hardware.fr/images/perso/delarue.gif "[:delarue]")
Marsh Posté le 12-01-2007 à 13:56:08
Reply![[:klem3i1]](https://forum-images.hardware.fr/images/perso/klem3i1.gif "[:klem3i1]")
Marsh Posté le 12-01-2007 à 20:22:24
Reply
Marsh Posté le 12-01-2007 à 20:26:49
Reply
Marsh Posté le 12-01-2007 à 20:57:30
Topic de qualité ![[:bien]](https://forum-images.hardware.fr/images/perso/bien.gif "[:bien]")
Pour ceux que ce genre de chose interesse, le site kivabien : http://www.maximumcompression.com/
On y retrouve un peu de theorie, mais surtout une base comparative de quasi tous les softs de compressions du marché testé dans différents types d'utilisations.
Marsh Posté le 12-01-2007 à 21:22:08
Merci pour vos commentaires ! 
J'espère que ça aidera quelques personnes à percer les "secrets" de la compression....
En faisant ce rapport j'ai beaucoup, beaucoup apris !
El Pollo Diablo > Merci pour ton lien 
Je vais rajouter ton lien en bas de la seconde page dans la section 'liens externes' !
Bien à vous
Cvb
Message édité par cvb le 12-01-2007 à 21:23:40
Marsh Posté le 12-01-2007 à 21:45:11
super comme thread. Je ne savais pas que les anti virus s'arretais jusqu'a un certain niveau ....
je ne comprends pas le principe de l'algo multimédia. Tu veux peut etre parler de la compression de fichiers d'image/video sans compression avec perte comme par exemple le wav, le raw, bmp, ?
qu'elle est l'interet du verouillage d'archive quand c'est crypté ?
Il aurait pu etre interessant de mettre en avant le format 7z qui a ce qui parait etre tres perfomant au niveau compression.
Marsh Posté le 12-01-2007 à 22:38:39
| weed a écrit : super comme thread. Je ne savais pas que les anti virus s'arretais jusqu'a un certain niveau .... |
La plupart des AV permettent de choisir le niveau de profondeur qu'on veut atteindre.
Marsh Posté le 14-01-2007 à 21:13:23
| weed a écrit : super comme thread. Je ne savais pas que les anti virus s'arretais jusqu'a un certain niveau .... |
Bonsoir,
Est-ce que tu peux reformuler, ta "première" question ? je ne comprends pas
Pour répondre à la seconde question, on peut penser qu'il s'agit là d'une securité supplémentaire ! Personellement, je ne l'ai jamais mise en oeuvre. Certains y répondront mieux que moi sans doute
En ce qui concerne le format 7z : Nous avions en fait que trois jours pour faire ce rapport et faire une soutenance derrière ! Donc j'avoue que nous n'avons pas eue le temps, de traiter tout les formats de compresssion (on n'as traité en priorité les formats utliser pour créer les fichiers ZIP et RAR)
A bientot
M.
Marsh Posté le 14-01-2007 à 21:27:33
| san_ a écrit : Bravo pour tout ce taff, très intéressant comme sujet |
| klemo a écrit : la vache, respect |
| freds45 a écrit : Très bon boulot ! |
| Face_Off a écrit : Beau boulot ! |
| El Pollo Diablo a écrit : Topic de qualité |
Vous avez lu son exposé ou vous vous en tenez à la longueur du post pour jusger? 
---------------
last.fm
Marsh Posté le 14-01-2007 à 21:35:02
C'est tres scolaire dans le format et y'a quelques imprecisions et racourcis hasardeux, mais ça reste du bon boulot ![[:spamafote]](https://forum-images.hardware.fr/images/perso/spamafote.gif "[:spamafote]")
Marsh Posté le 15-01-2007 à 22:08:15
| El Pollo Diablo a écrit : C'est tres scolaire dans le format et y'a quelques imprecisions et racourcis hasardeux, mais ça reste du bon boulot |
Là c'est plus constructif.
---------------
last.fm
Marsh Posté le 09-08-2008 à 13:34:32
Bonjour,
bel exposé, d'abord et ensuite j'ai une question.
Si la compression fonctionnait tout le temps à partir d'une certaine taille au cas où il y aurait une taille minimale au délà duquel la compression serait toujours intéressant alors le fichier zip généré devrait alors toujours être plus petits que le message original.
Et donc alors ca implique mathématiquement qu'il est possible que deux fichiers compressés aboutissent au même fichier zip ? non ?
Marsh Posté le 09-08-2008 à 14:47:28
C'est pour ca que ce n'est pas possible. Mathématiquement, on ne peut pas définir une bijection entre un ensemble et un ensemble plus petit.
Quel que soit le système de compression sans perte, il y aura des fichiers qui une fois compressés feront la même taille ou seront plus gros que l'original.
![[:drap]](https://forum-images.hardware.fr/images/perso/drap.gif "[:drap]")
Marsh Posté le 26-11-2013 à 09:36:23
Désolé de ce gros déterrage, mais si quelqu'un peut me renseigner merci :
J'utilise en soft Winrar / Winzip et également 7zip de côté.
J'ai des grosses archives (40Go) et la compression en elle même n'est pas le soucis. Je voulais savoir quelle archive est la plus fiable, afin d'éviter des fichiers corrompus, illisibles. Le tout pour éviter de perdre mes données.
Merci et désolé du vieux déterrage.
Marsh Posté le 26-11-2013 à 10:51:37
Si tu n'accoles pas un mécanisme de réparation en cas de corruption de données (le rar le gère en natif, sinon tu peux le rajouter via par exemple QuickPar), alors tous les formats seront à égalité la dessus.
Bien sûr cela voudra dire qu'il te faudra un peu plus de place, pour stocker les infos de réparation.
Marsh Posté le 26-11-2013 à 13:25:29
Winrar permet de le faire (compter 3% en plus).
En fait, je pensais que certaines archives étaient plus sûres que d'autres, dont le rar.
Ayant eu qq zip corrompus, j'ai pas envie de perdre mes données.
Marsh Posté le 07-01-2014 à 17:45:01
Au final, Winzip étant devenu une usine à gaz, lent surtout dans sa version 17 (à l'ouverture d'un .zip, je dois attendre 15-20 secondes, un bug, je sais pas pourquoi), je garde Winrar de côté avec 7zip en doublon et le tour est joué.
Message édité par freduche le 07-01-2014 à 17:45:42
Marsh Posté le 30-09-2016 à 10:59:37
Bonjour
Je cherche à faire faire des compressions zip à un CPU embarqué qui tourne en C sur Freertos
Toutes les lib que je trouve ne parlent pas de zip mais uniquement des algos de compression
La plus simple et limpide à utiliser est celle ci
http://bcl.comli.eu/
qui propose plusieurs algos :
case 1: printf( "RLE " ); break;
case 2: printf( "Huffman " ); break;
case 3: printf( "Rice 8-bit " ); break;
case 4: printf( "Rice 16-bit " ); break;
case 5: printf( "Rice 32-bit " ); break;
case 6: printf( "Rice 8-bit signed " ); break;
case 7: printf( "Rice 16-bit signed " ); break;
case 8: printf( "Rice 32-bit signed " ); break;
case 9: printf( "LZ77 " ); break;
case 10: printf( "Shannon-Fano " ); break;
Mon problème est que aucun de ces algos génère un fichier ouvrable avec un outil de décompression zip (j'utilise 7 zip et l'outil intégré à Windows)
De ce que je comprends il y aurait au moins du LZ77 dans les ZIP (effectivement sur mes fichiers texte c'est de loin le plus performant) mais même dans ce topic détaillé je ne vois pas d'explication sur ce qui permet de passer du simple algo à Zip
Sauriez vous m'expliquer comment faire du zip ? soit à l'aide d'une lib C had hoc, soit en manipulant comme il faut les algos que je sais exécuter aujourd'hui avec la lib bcl que je cite ici.
Merci par avance
Sujets relatifs:
- Demontrer qu un fichier ZIP est pas conforme ?
- Vitesse de Compression avec Auto Gordian Knot
- [Office 2007] La compression des images est cassée ?
- [WINRAR]exporter/importer les profils de compression
- Compression winrar !
- [ Debat ] De l'intérêt de la compression des exe téléchargés
- [DAT] Comment fonctionne la compression matérielle ?
- Commande RAR ou ZIP
- Fichiers Zip avec FlashGot
Marsh Posté le 12-01-2007 à 10:02:44
Bonsoir à vous tous et toutes,
Je veux vous faire profitez des recherches, que nous avons mené (en groupe) sur un sujet qui nous avait été demandé : les Algorithmes de compression ZIP & RAR ! C'est un sujet à forte consonnance mathématiques, mais qui apporte beaucoup !
SOMMAIRE:
Introduction
La compression
Avantages et inconvénients
Exemple de compression
Compression avec pertes
Compression sans pertes
Fichier ZIP & RAR
Fichier ZIP
Fichier RAR
Comparatif en 7-Zip & WinRAR
Lequel utiliser, lequel choisir ?
Conclusion
Systèmes de codage
LZ77
LZMA
BWT
Huffman
Rôles des mathématiques
Conclusion
--------------------------------------------------------------------
---------------------
INTRODUCTION :
---------------------
Les données quelque soit la nature des fichiers occupent une place, un espace sur les volumes de stockage tels que disques durs, volumes externes, casettes, parfois non négligeable. Les volumes de stockage nétant pas extensible sans moyen financier supplémentaire (achat de disque durs supplémentaires, ect ) la compression à trouvé toute sa place.
Ce rapport va traiter la compression de fichier ZIP et RAR. En quoi consiste la compression, quels sont les types de compression qui existent ? Quest ce que renferment les mots ZIP et RAR ? Quelles sont les applications pouvant créer ces fichiers, sont-elles viables ?
Une fois traité ces questions nous rentrerons en détails et dans le sujet de plein pied, avec les systèmes de codages utilisés, mise en uvre pour compresser, décompresser. Les mathématiques ont un rôle prédominant, mais lequel ? Quels systèmes de codage choisir ?
---------------------
LA COMPRESSION :
---------------------
Cest très simple, un fichier à une certaine taille. On veut réduire sa taille pour de nombreuses raisons. On limbrique dans un fichier ZIP ou RAR. Cest un conteneur, qui va réduire la taille de notre fichier (Cf chapitre Fichier Zip & Rar). Ce conteneur peut contenir plusieurs fichiers. Plusieurs conteneurs existent et tous les fichiers ne peuvent être réduits.
Avantages et inconvénients de la compression :
Avantages :
Avec lapparition du réseau, laugmentation des échanges, par les réseaux câblés, la compression des données a trouvé un souffle supplémentaire. Quand vous avez plusieurs fichiers de plus dun méga chacun à envoyer, imaginez le temps que ça peut prendre. Cest un exemple.
Exemple concret : Un groupe sapprête à faire une démonstration à des acheteurs, dans une heure. A cause dune contrainte extérieure, technique, et humaine, ils ont besoin de plusieurs fichiers rapidement. Une solution de repli existe.
Ils contactent leur agence à lautre bout de la planète. Plusieurs fichiers de plusieurs mégas chacun leur ferait perdre le contrat, à cause du temps denvoi et de réception des courriels.
Grâce à la compression, ils vont pouvoir imbriquer leur fichier dans un fichier ZIP qui lui-même compressera les fichiers sans pertes. Il ne reste plus quà envoyer ce fichier par le réseau. Le temps denvoi et de réception est réduit de moitié. Ils seront à leur rendez-vous pour leur démonstration.
Inconvénients :
Dans le monde de linformatique il y a toujours des renards, des corbeaux qui ne cherchent quà exploiter les failles. Il nen existe une avec les fichiers compressés. Un virus peut très bien être renfermé dans un fichier compressé. Les anti-virus scannent que dans 4 niveaux de profondeur.
Exemple dans le schéma ci-dessous, des fichiers zip peuvent être imbriqués dans dautres fichiers zip. Lanti-virus natteindra pas le virus, car il est dans un sixième niveau de profondeur (6 fichiers zip imbriqués dans le premier). Dans la réalité je ne sais pas si cest utilisé. Mais la possibilité est donnée à des pirates dutiliser cette méthode. Un anti-virus avec une certaine renommée, avec un très fort service commercial derrière, ne scannait pas les fichiers compressés à un certain moment. Les dégâts étaient importants pour certains utilisateurs peut scrupuleux.
Quelques exemples ci-dessous dutilisation qui viennent appuyer lutilité de compresser malgré ce petit inconvénient.
Exemples de compressions :
Exemples dutilisation de la compression pour le stockage
Exemples dutilisation de la compression pour le transport
Les applications sont nombreuses. Une notion à été abordée au début, la notion de pertes et sans pertes. Pour rester dans le domaine de linformatique, il existe plusieurs méthodes de compression, plusieurs types de fichiers.
---------------------
LA COMPRESSION AVEC PERTE:
---------------------
Exemple très rapide de compression avec pertes que tout le monde connait. La compression JPEG qui utilise des systèmes de codage aussi, Huffman notamment (Cf Système de codage). Ce tableau vous montre la puissance des algorithmes quand on convertit un format lourd (BMP) en format léger (JPG). Le fichier original (BMP) est de 2,50 Mo.
Quelques exemples de compression avec pertes dans ce tableau.
---------------------
LA COMPRESSION SANS PERTES:
---------------------
La compression sans pertes ce sont des fichiers, dossiers que lon met dans des grandes boites, que lon compresse ensuite, avec une extension. Fichier ZIP et Fichier RAR.
---------------------
FICHIER ZIP & RAR:
---------------------
Le ZIP et le RAR sont des formats de fichier permettant la compression de données, sans pertes, sans aucune pertes des données. Un présentation rapide ci-dessous, de ces deux extensions.
Fichier ZIP :
Le format ZIP a été inventé par Phil Katz pour le logiciel PKZIP. Il a été conçu en réponse à un problème de droits entre le programme PKARC et le format ARC lancé par la Software Enchantement Associates. ARC est vendu en tant que partagiciel principalement aux utilisateurs de BBS afin qu'ils puissent compresser leurs fichiers plus rapidement.
Katz décida de cesser le développement de PKARC et décrivit son propre format PKZIP utilisant l'extension de fichier .zip et l'algorithme deflate. Le format JAR (Java Archive) est identique au format ZIP. On peut renommer les fichiers .jar en .zip.
Fichier RAR:
Le format RAR est un format de fichier propriétaire permettant la compression de données. Ce format a été inventé par Eugene Roshal.
Il a également publié un code source permettant de décompresser les archives RAR sous une licence qui en permet la libre distribution et modification (la version libre ne peut toutefois pas décompresser les archives RAR de version 3). Cette licence interdit d'utiliser ce code source pour construire un codeur compatible. La méthode de codage est dite propriétaire.
L'un des avantages du format RAR est son efficacité à produire des découpes de fichiers. D'autres formats de compression comme le format ouvert 7-zip le permettent également. Un autre avantage du format RAR est sa capacité de chiffrement des données ; celui-ci est toutefois possible par d'autres formats, tel 7z.
Avant tout travail, de compression des données il existe un prétraitement des données. Cest un travail léger effectué sur des données avant leur traitement proprement dit. Il s'agit classiquement de produire effectivement le code qui sera compilé, en dépliant les macros, en réunissant les fichiers, en vérifiant que toutes les bibliothèques sont là, un peu de la même manière quen C avant de compiler.
En fonction du type de fichier choisi, de la compression demandée, il emploiera un système de codage. En fonction de lextension ZIP ou RAR et de lapplication utilisée un système de codage sera employé.
Un tableau récapitulatif montre les systèmes de codage utilisés par les applications pour obtenir ces fichiers. Nous avons pris deux applications lune pour faire les ZIP et la seconde pour faire les RAR.
-----------------------------------
COMPARATIF EN 7-ZIP & WINRAR
-----------------------------------
Le ZIP et le RAR utilisent les mêmes algorithmes à quelques choses prés. 7-ZIP qui permet de créer des fichiers ZIP tout comme Winrar. Un petit comparatif entre les deux applications permettant de créer des fichiers ZIP et RAR, avant de rentrer dans le vif du sujet et détudier les systèmes de codages employés. Le choix de 7-ZIP est arbitraire.
Introduction :
Deux tableaux ci-dessous vont aider à comprendre les différences entre les deux applications, avantages et inconvénients de chacun et lintérêt à prendre lun ou lautre.
Que nous montre ce tableau ? Nous pouvons remarquer que les deux applications utilisent les mêmes systèmes de codage, à une exception prés (LZMA). Là ou les deux applications vont commencer à se distinguer, cest dans des fonctions essentiels. Exemples :
Recovery Record : Permet de récupérer les fichiers endommagés
Ces nombreuses fonctions trouvent leur utilité dans bon nombre de cas, surtout dans le milieu professionnel. Crypter les données, mettre un mot de passe, peut être nécessaire, pour un particulier mais aussi et surtout un professionnel. Les exemples ne manquent pas.
Ces deux derniers tableaux parlent deux même. Il est clair que 7-Zip nest pas fait pour compresser des fichiers multimédia.
Lequel utilser, lequel choisir ?
Le prix nest pas le seul argument à prendre en compte pour accepter ou refuser un achat dune application qui peut apporter beaucoup.
7-ZIP :
Nous utilisons cet exemple. Faisons un saut en arrière de dix ans, par exemple en 1995.
Si on se replace dans le contexte de cette époque, peut de gros fichiers existaient, on travaillait au mieux sur de gros fichiers texte, les virus navaient pas une place omniprésente comme aujourdhui, les spywares, malwares et autres joyeusetés nexistaient pas non plus. Les permissions nexistaient pas non plus.
Ces machines là existent encore aujourdhui ! Sur danciens systèmes dexploitation 7-ZIP serait très bien ; léger, rapide et libre. Si on rebondit sur le fait que 7-Zip ne gère pas le multimédia, quil est bien adapté aux fichiers de tailles moyennes, alors il prend toute sa place sur ces anciens systèmes et machines.
Winrar :
Pour prendre en compte cela, il fallait en plus des fonctionnalités déjà présentes sur les systèmes, un logiciel qui réduise la place des données en les compressant, pour économiser de lespace libre et par conséquent de largent.
Si cette application pouvait crypter les données, récupérer les anciens fichiers compressés sur des veilles disquettes, traiter de gros fichiers comme les images ou vidéos, elle serait la bienvenue, pour particulier et professionnel bien sûr. Winrar répondait à ces attentes.
Conclusion :
7-ZIP peut sutiliser sur de grosses machines mais sera moins performant. Il ne répondra pas à toutes vos attentes. Son avantage : Libre. Winrar sont concurrent part avec un « désavantage », son prix est de 30 Dollars.
Par contre il rattrape ce retard avec les nombreuses fonctions quil propose qui dans bon nombre de cas peuvent servir ; dans le milieu professionnel notamment. Le chapitre suivant, traiteras des algorithmes de cryptage mis en uvre (fonction mathématiques, exemples,ect )
-----------------------------------
SYSTEMES DE CODAGES
-----------------------------------
Les algorithmes ZIP et RAR utilisent des systèmes de codage, crées par de chercheurs, mathématiciens. Ci-dessous, un historique, la théorie, lapplication et une conclusion succincte des quatre systèmes suivant utilisés : LZ77, LZMA, BWI, HUFFMAN
>> LZ77 <<
Fichier ZIP : Oui
Fichier RAR : Oui
Historique des algorithmes LZ :
En 1977 Jacob Ziv et Abraham Lempel fournissent une technique de compression différente de lalgorithme de Huffman, et capable de donner de meilleurs taux de compression. Ils mettent ainsi en place lalgorithme LZ77. Puis vient LZSS, version améliorée de LZ77 par Storer et Szymanski puisque la recherche des séquences dans le dictionnaire est réduite logarithmiquement. Enfin vient lalgorithme LZ78, plus connu sous le nom LZW, amélioration faite par Terry Welch en 1984 de LZSS de par le fait que les séquences sont rangées dans une arborescence. Il porte le nom de ses 3 inventeurs : Lempel, Ziv et Welch.
Théorie :
Le principe est fondé sur le fait quune séquence de caractères peut apparaître plusieurs fois dans un fichier. Lalgorithme LZ de compression consiste à émettre à la place des séquences, les adresses de ces séquences dun dictionnaire généré à la volée. Cest un algorithme de compression nettement plus performant en moyenne que les algorithmes statistiques puisquil permet dobtenir des gains plus élevés sur la majorité des fichiers. Lalgorithme LZ se distingue des méthodes statistiques pour plusieurs raisons :
Il permet le compactage à la volée, puisquil ny a pas à lire le fichier au préalable, il compresse les séquences de symboles au fur et à mesure.
Application :
La chaîne /WED/WE/WEE/WEB.
Compactons-la avec Lempel-Ziv :
Il faut 15*8 = 120 bits pour stocker cette chaîne en mémoire
(1 caractère = 8 bits = 1octet)
L'algorithme sort : '/WED<256>E<260><261><257>B'. Ici, il ne faut plus que 4*9 + 6*8 = 84 bits. (après /WED, on dépasse 255 : il faut utiliser 9 bits).
Remarque : Pour un taux de compression "normal", il est recommandé d'utiliser une fenêtre de plusieurs milliers de caractères, pour un tampon de pré-lecture d'une centaine de caractères.
Variante de lalgorithme
Il existe des variantes des compressions LZ :
Conclusion :
Lalgorithme LZ est aujourdhui considéré comme la méthode de compression la plus efficace et une des plus connues. Elle est relativement rapide ; ce qui a rendu lutilisation de la compression possible sur les disques durs de façon transparente. Cette méthode est aussi utilisée dans le format .gif, mais encore dans les compresseurs tels que ZIP, ARJ.
La compression par dictionnaire de type LZ(TIFF,GIFF par LZ et PNG pour GIF) est très rapide mais ne compresse que peu les images de 2 à 24 bits. Néanmoins, elle était peu utilisée car elle était brevetée par la société Unisys jusquen juillet 2004 (8 Juillet 2004) où le brevet a expiré. Par conséquent, cette dernière ne peut plus à présent réclamer des droits sur lutilisation du format gif par exemple car celui ci reposait sur lalgorithme LZ.
>> LZMA<<
Fichier ZIP : Oui
Fichier RAR : Non
Historique :
LZMA, pour Lempel-Ziv-Markov chain-Algorithm, est un algorithme de compression de données créé en 2001.
Théorie :
Il utilise une compression avec dictionnaire assez similaire au LZ77 et offre un fort taux de compression et une taille variable de dictionnaire de compression (jusqu'à 4 Go). (Voir aussi LZW)
Application :
Ses principales caractéristiques sont :
Conclusion:
Il est utilisé dans les formats 7z du programme 7-zip et par Stuffit, Stuffit étant une famille de logiciel permettant de compresser et décompresser des archives sur les Macs.
Message édité par cvb le 12-01-2007 à 10:07:14