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 ? Qu’est 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 :
---------------------
 
C’est très simple, un fichier à une certaine taille. On veut réduire sa taille pour de nombreuses raisons. On l’imbrique dans un fichier ZIP ou RAR. C’est 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 l’apparition du réseau, l’augmentation 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 d’un méga chacun à envoyer, imaginez le temps que ça peut prendre. C’est un exemple.
 
Exemple concret : Un groupe s’apprête à faire une démonstration à des acheteurs, dans une heure. A cause d’une contrainte extérieure, technique, et humaine, ils ont besoin de plusieurs fichiers rapidement. Une solution de repli existe.  
 
Ils contactent leur agence à l’autre bout de la planète. Plusieurs fichiers de plusieurs mégas chacun leur ferait perdre le contrat, à cause du temps d’envoi 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 d’envoi et de réception est réduit de moitié. Ils seront à leur rendez-vous pour leur démonstration.
 
Inconvénients :  
 
Dans le monde de l’informatique il y a toujours des renards, des corbeaux qui ne cherchent qu’à exploiter les failles. Il n’en 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 d’autres fichiers zip. L’anti-virus n’atteindra 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 c’est utilisé. Mais la possibilité est donnée à des pirates d’utiliser 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 d’utilisation qui viennent appuyer l’utilité de compresser malgré ce petit inconvénient.  
 
Exemples de compressions :
 
Exemples d’utilisation de la compression pour le stockage
 

• Bases de données (les fichiers du FBI contiennent environ 200 millions d’empreintes digitales)  
• Mini-disc (les données audio y sont compressées)
• Le coût et les limites technologiques nécessitent d’utiliser la compression de données pour le stockage d’importants volumes d’information.

Exemples d’utilisation de la compression pour le transport
 

• Réseaux par câbles (Minitel, Internet dont la bande passante, i.e. le débit est très faible)  
• Réseaux sans fil (communication par satellite avec par exemple la télévision par satellite, le téléphone portable …)
• Pour une durée donnée, la compression permet de faire circuler plus d’informations, le débit est donc plus grand.

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 l’informatique, il existe plusieurs méthodes de compression, plusieurs types de fichiers.  
 

• Il y a des méthodes de compression (conversion) qui permettent de compresser le fichier en un format donné, exemple : WAV en MP3 (de nombreuses informations non audible pour un humain seront perdues, pour réduire la taille du fichier, de manière irréversible). Compression avec pertes.

• L’opposé existe, comme par exemple imbriquer des fichiers dans des conteneurs Manière réversible on retrouvera toutes les informations. Compression sans pertes.

---------------------
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 l’on met dans des grandes boites, que l’on 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. C’est 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 qu’en 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 l’extension ZIP ou RAR et de l’application 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 l’une 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 l’intérêt à prendre l’un ou l’autre.
 

 
 
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, c’est dans des fonctions essentiels. Exemples :
 
Recovery Record : Permet de récupérer les fichiers endommagés
 

• Cryptage : Crypte les données. Essentiel parfois.  
• Vérouillages d’archives : Permet de mettre un mot de passe au fichier archive pour l’ouvrir.  

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 d’eux même. Il est clair que 7-Zip n’est pas fait pour compresser des fichiers multimédia.
 

 
 
Lequel utilser, lequel choisir ?
 
Le prix n’est pas le seul argument à prendre en compte pour accepter ou refuser un achat d’une application qui peut apporter beaucoup.
 
7-ZIP :
 
Nous utilisons cet exemple. Faisons un saut en arrière de dix ans, par exemple en 1995.    

• Ancien système d’exploitation (Génération des 9x,….)
• Processeur peu performant (Pentium 90,100,…)
• RAM faible : 16 Mo
• Support de stockage peut important (ex : Disque dur maximum 8 go)
• Les graveurs de CD coutaient très chères.  
• Internet pas ou peut développer à part pour les personne ayant les moyens (je rappelle que l’ADSL pour ne prendre que cet exemple n’existait pas)

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 n’avaient pas une place omniprésente comme aujourd’hui, les spywares, malwares et autres joyeusetés n’existaient pas non plus. Les permissions n’existaient pas non plus.
 
Ces machines là existent encore aujourd’hui ! Sur d’anciens systèmes d’exploitation 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, qu’il est bien adapté aux fichiers de tailles moyennes, alors il prend toute sa place sur ces anciens systèmes et machines.  
 
Winrar :
 

• Bon nombre de contraintes ont empêché le développement du Multimédia, par conséquent le stockage de gros fichiers, volumineux. Aujourd’hui, les machines ont évolué, les tailles des disques ont augmenté, les processeurs ont progressé, les systèmes sont de plus en plus rapides, l’accès à internet a impliqué de protéger les données (ex : permissions NTFS). Une machine est susceptible d’être attaquée depuis l’extérieur et les données divulguées.  

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 l’espace libre et par conséquent de l’argent.  
 
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 s’utiliser 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 qu’il 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, l’application 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 l’algorithme de Huffman, et capable de donner de meilleurs taux de compression. Ils mettent ainsi en place l’algorithme 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 l’algorithme 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 qu’une séquence de caractères peut apparaître plusieurs fois dans un fichier. L’algorithme LZ de compression consiste à émettre à la place des séquences, les adresses de ces séquences d’un dictionnaire généré à la volée. C’est un algorithme de compression nettement plus performant en moyenne que les algorithmes statistiques puisqu’il permet d’obtenir des gains plus élevés sur la majorité des fichiers. L’algorithme LZ se distingue des méthodes statistiques pour plusieurs raisons :  
 
 

• Le fichier compressé ne stocke pas le dictionnaire, ce dernier est automatiquement généré lors de la décompression. Il n’existe donc pas de table d’entête.
• Contrairement aux méthodes statistiques qui utilisent la probabilité de présence sur un ensemble de taille fixe de symboles, l’algorithme LZ représente un algorithme d’apprentissage, puisque les séquences répétitives de symboles sont dans un premier temps détectées puis compressées seulement lors de leurs prochaines occurrences. Le taux de compression est dépendant de la taille du fichier. Plus la taille est importante, et plus le taux de compression l’est aussi.

Il permet le compactage à la volée, puisqu’il n’y 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 l’algorithme
 
Il existe des variantes des compressions LZ :
 

• LZP : Algorithme qui se base sur la répétition de phrases entières.
• LHA, LZS, LZX, LZH : Algorithmes quasiment identiques, encore dérivés du LZ77. Il n’est employé que pour l’utilitaire Lharc, très répandu au Japon, mais de moins en moins utiliser dans le Monde.

Conclusion :
 
 
L’algorithme LZ est aujourd’hui considéré comme la méthode de compression la plus efficace et une des plus connues. Elle est relativement rapide ; ce qui a rendu l’utilisation 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 jusqu’en 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 l’utilisation du format gif par exemple car celui ci reposait sur l’algorithme 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 :

• Taux de compression élevé.  
• Taille du dictionnaire variable (jusqu'à 4 Go).  
• Vitesse de compression : environ 1 Mo/s sur un processeur à 2 GHz.  
• Vitesse de décompression : environ 10-20 Mo/s sur un processeur à 2 GHz.  
• Faible demande de mémoire pour la décompression (selon la taille du dictionnaire).  
• Petite taille du code de décompression : environ 5 Ko.  
• Support du multi-threading et de l'hyper-threading du P4.(plusieurs opérations).

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.

>> 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:
 
L’algorithme de Huffmann a été décrit pour la première fois en 1952. L’algorithme 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 d’information. Prenons l’exemple d’un fichier de texte : Le fragment d’information sera un caractère ou une suite de caractères
 
L’algorithme de Huffman se base sur la fréquence d’apparition d’un 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 l’information, on va donc devoir utiliser une table de fréquences et deux choix s’offrent à nous : calculer une table et l’inté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 d’une 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 n’aura pas à calculer les fréquences, par contre l’efficacité 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 s’appuie 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 d’obtenir 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 qu’elles 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 l’entropie H de la source :
 

 
L’efficacité 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, l’efficacité 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 l’arbre 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 nœuds, et de feuilles. On appelle racine le père de tous les nœuds (la racine  
 
est aussi un nœud). Un nœud représente une 'branche' de l'arbre. Une feuille est un nœud 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 nœud fils gauche", et un '1' signifie "aller au nœud fils droite".
 

 
Voilà le tableau résumant la compression :
 

 
 
Conclusion :
 
Cet algorithme est gratuit, simple et efficace. Grâce à ça il est beaucoup utilisé aujourd’hui. C’est un avantage non négligeable pour une entreprise d’avoir 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 aujourd’hui, dans bon nombre d’application.  Il s’en sert pour classer le texte et faire le tri là-dessus
 
D’autres fonctions mathématiques sont mises en œuvre, comme l’addition, la soustraction, la multiplication, la division, la conversion hexadécimal, ASCII, binaire.
 
 
-----------------------------------
CONCLUSION
-----------------------------------
 
 
Deux logiques s’affrontent. Le Libre et le payant. Certains systèmes de codage comme le système Huffman étaient libres d’accès, d’autres é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 d’années. Le plus vieux remonte à prés de soixante ans en arrière. Depuis, peu sont sorti ; ce qui prouve bien l’efficacité de ces systèmes de codage crée aux balbutiements de l’informatique (surtout grand public).
 
Résumons :
 

• LZ : L’algorithme LZ est aujourd’hui 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 n’est pas un algorithme de compression à proprement parler. C’est 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 l’utilisent.

 
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 d’applications comme Winrar l’ont 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 qu’un autre, mieux adapté au type de fichier à compresser.  
 
Il n’y a pas de choix à faire, juste à s’adapter 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
 

Waouh ! Ca c'est du topic R++

Ca c'est pas un topic de paidai  

Bravo pour tout ce taff, très intéressant comme sujet

la vache, respect

Très bon boulot !

Beau boulot !
Merci

Topic de qualité    
 
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.

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

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.

 
La plupart des AV permettent de choisir le niveau de profondeur qu'on veut atteindre.

BRAVO Pour ce +++++

 
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.
 

 
Vous avez lu son exposé ou vous vous en tenez à la longueur du post pour jusger?

A ton avis ?

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.

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 ?

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.

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.

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.

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.

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é.

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