|
La compression de données - Généralités |
| Article posté par serioussam Sujet de TPE 2004, réalisé par Sebastien Monchamps et Geoffrey Anneheim. Vous pouvez télécharger le dossier complet dossier complet , ainsi que le compresseur avec les sources. Stockage des données informatiques : Aujourd?hui, les données informatiques prennent de plus en plus de place et des solutions on été inventées pour palier au problème de stockage de fichiers. Pas tant sur PC réellement à cause de la taille des disques durs qui évolue sans cesse, mais plutôt pour les appareils astronomiques, la transmission d?images prise par les ondes, les appareils du type lecteur MP3, les appareils photo numériques qui possèdent un très faible espace de stockage ou encore les flux de données sur Internet? Prenons l?exemple des images numériques qui font partie des données nécessitant un grand espace de stockage, et qui sont des données courantes en informatique. Une image de qualité photographique soit 4 milliards de couleurs et de taille de 1280x720 pixels (35x20 cm), occupe 4 Méga Octets soit une suite de plusieurs millions de 0 et de 1 ! Il serait donc impossible d?envoyer ce genre d?image rapidement sur Internet et d?en stocker un grand nombre sur un appareil photo. La compression devient donc un élément indispensable, et ce sans perte de données: il serait impensable de perdre des octets dans le cas d?un fichier exécutable ou encore d?un fichier texte. Plusieurs techniques on été mises en ?uvre et chacune répond plus ou moins à des exigences (Difficultés de mise en ?uvre, efficacité de compression, vitesse d?exécution, degré de conservation de l?information). L?algorithme de compression doit être choisi en fonction du besoin. Par exemple en astronomie on privilégiera la qualité et pour les appareils photographiques numériques la difficulté de mise en ?uvre et surtout la vitesse d?exécution, pour ne pas à avoir à réaliser des circuits complexes demandant un coût assez élevé. Nous avons décidé d?étudier de plus près les différentes méthodes de compression qui permettent de réduire la taille de différents fichiers et d?essayer de dresser un bilan des capacités des différentes méthodes de compression et des programmes en fonction des types de fichiers et des logiciels présents dans le commerce ou sur Internet? mais une simple étude théorique ne suffit pas, un programme regroupant plusieurs solutions de compression sera réalisé et ce en langage C++ ainsi que la création d?un environnement avec Visual Basic 6.0. Généralités sur la représentation des données. Avant de commencer il est nécessaire de connaître comment sont stockées les données sur un ordinateur. Le bit (Binary Digit) est l?unité de la numération binaire, il ne peut prendre que deux valeurs : 0 ou 1 (Non ou Oui). Toutes les données informatiques plus précisément numériques sont enregistrées sous la forme de succession de bits. Ainsi un octet est un regroupement par paquet de 8 bits, cette unité a été choisie car elle fut une solution adapté pour les ordinateurs munis d?un processeur 8 bits, un octet peut prendre 2^8 = 256 valeurs différentes de 0 à 255 en non signé et de -128 à 127 en signé (base 10) et le plus courant de 0x00 à 0xFF (en base 16). Un caractère est un signe codé sur un octet d?après une table précise, la table ASCII (American Standard Code for Information Interchange) qui peut varier suivant la machine et le système d?exploitation. C?est un codage standardisé de représentation des caractères alphanumériques, ainsi un code représente un caractère soit le code 33 (base 10) pour le caractère ! ou encore 65 (base 10) pour A, ce dernier caractère transcrit en binaire donne 0b1000001 (base 2) ce qui sera inscrit sur le support de stockage (Disque Dur, Disquette, CD?). On se rend vite compte du nombre élevé de bits lorsque que l?on tape un texte?C?est pourquoi on utilise des multiples de l?octet soit le Kilooctet qui est égal à 2^10 octets soit 1024 octets (8192 bits). Le mégaoctet vaut 2^20 octets soit 1 048 576 octets. Le gigaoctet vaut 2^30 octets soit 1 073 741 824 octets ! Points généraux sur les algorithmes de compression. Gain de place Le degré de réduction des données peut être obtenu avec cette formule : Qcomp = Taille Initiale / Taille Finale Le taux de compression exprimé en pourcentage est l?inverse du quotient de compression : Tcomp = 1 / Qcomp Le gain de compression est exprimé en pourcentage en effectuant le complément à 1 du taux de compression : Gcomp = 1- Tcomp = (Taille Initiale ? Taille Finale) /Taille Finale Exemple : Un fichier original de 2 000 octets compressé en 500 octets un quotient de 2,5, un taux de compression de 40%, et un gain de compression de 60%. Définition du terme compression : La compression est le processus mathématique informatisé qui permet de traiter un fichier d'entrée à sa taille maximale vers un fichier de sortie de taille réduite. Si un algorithme de compression peut diminuer la taille des fichiers, il peut également augmenter la taille de certains autre. La compression sans pertes et avec pertes: La compression est divisé en 2 familles, la première dite compression sans perte permet de compresser un fichier avec des taux raisonnables et le restaurer tel quel après décompression et la compression avec perte, s?appliquant aux données multimédia comme les images, le son et les vidéos. On remarquera toujours qu?un fichier compressé avec perte aura de meilleur taux de compression qu?un fichier compressé sans perte. Pour les compressions non conservatrices, on utilise une formule pour déterminer la qualité du résultat. On considérera que (n') est une donnée récupérée d'une donnée originale (n). Si n1 = n'1, n2 = n'2 ? on a une compression conservatrice. Sinon, pour N suite de données, on mesure l'EQM (Erreur Quadratique Moyenne) grâce à la formule suivante : Conclusion : Un algorithme performant possède donc un quotient de compression maximal, et une EQM minimale. Toutefois, cette valeur ne reflète pas les informations perçues par l??il humain. Généralement, lors d'une compression avec pertes, les données perdues sont les moins importantes. L'EQM peut ainsi être élevée et l'image de bonne qualité. |
>> Vos commentaires [0]
|