Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Algorithme de compression sans perte
Résumé
vignette|Comparaison de la compression d'image entre les formats JPG (à gauche) et PNG (à droite). PNG utilise une compression sans perte.
On appelle algorithme de compression sans perte toute procédure de codage ayant pour objectif de représenter une certaine quantité d'information en utilisant ou en occupant un espace plus petit, permettant ainsi une reconstruction exacte des données d'origine. C'est-à-dire que la compression sans perte englobe les techniques permettant de générer un duplicata exact du flux de données d'entrée après un cycle de compression/expansion. Pour cette raison, la compression sans perte est utilisée pour compresser des fichiers contenant des données qui ne peuvent pas être dégradées ou perdues, tels que des fichiers textes, images et son.
Ce type de compression est basé sur les concepts de la théorie de l'information, tels que la redondance et l'entropie des données et est généralement implémenté à l'aide d'un ou deux types de modèles différents : statique et basé sur dictionnaire .
Le modèle statique lit et code en utilisant la probabilité d'apparition de chaque caractère. Sa forme la plus simple utilise une table de probabilités statiques. La génération d'une arborescence de Huffman remplie de données présente un coût de calcul important, par conséquent, celle-ci n'est pas toujours générée, mais des blocs de données représentatifs sont analysés, ce qui donne lieu à un tableau de fréquences caractéristique. À partir de là, une arborescence de Huffman est générée, généralisée au reste des données, donnant lieu à un modèle statique. Cependant l'utilisation d'un modèle statique a ses limites. Si un flux d'entrée ne correspond pas bien aux statistiques précédemment accumulées, le taux de compression se dégraderait, au point que le flux de données sortant était aussi long que le flux entrant (voire plus long). Par conséquent, la prochaine amélioration évidente consistait à créer une table construite à la réception du flux d'entrée.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Publications associées (16)
Concepts associés (57)
Codage de Huffman
Le codage de Huffman est un algorithme de compression de données sans perte. Le codage de Huffman utilise un code à longueur variable pour représenter un symbole de la source (par exemple un caractère dans un fichier). Le code est déterminé à partir d'une estimation des probabilités d'apparition des symboles de source, un code court étant associé aux symboles de source les plus fréquents. Un code de Huffman est optimal au sens de la plus courte longueur pour un codage par symbole, et une distribution de probabilité connue.
Portable Network Graphics
Le Portable Network Graphics (PNG, prononcé « ping ») est un format ouvert d’, . Le PNG est un format sans perte spécialement adapté pour publier des images simples comprenant des aplats de couleurs. Il a été normalisé par l’ISO (ISO/CEI 15948:2004). PNG est une spécification pour Internet et l’objet d’une Recommandation W3C et d’une RFC. Il a été créé pour contourner la licence existante sur le format GIF, le plus en vogue à la fin des années 1990, Unisys, propriétaire de deux brevets sur des algorithmes utilisés par la compression sous GIF ayant réclamé des royalties.
MP3
Le MPEG-1 Audio Layer ou MPEG-2 Audio Layer , plus connu sous son abréviation de MP3, est la spécification audio des standards MPEG-1 et MPEG-2. Il s'agit d'un format de compression audio avec perte permettant une réduction importante de la taille du flux de données audio, tout en conservant une qualité de restitution couramment jugée acceptable, donnant le choix du débit selon le compromis taille-qualité souhaité. C'est aussi l'un des formats de musique numérique les plus répandus. L'extension de nom de fichier est .
Cours associés (59)
CS-119(c): Information, Computation, Communication
L'objectif de ce cours est d'introduire les étudiants à la pensée algorithmique, de les familiariser avec les fondamentaux de l'Informatique et de développer une première compétence en programmation (
COM-404: Information theory and coding
The mathematical principles of communication that govern the compression and transmission of data and the design of efficient methods of doing so.
ME-232: Mechanics of structures (For GM)
L'étudiant acquiert les bases de l'analyse des contraintes et déformation des poutres élastiques linéaires soumises à la traction, cisaillement, torsion, flexion; les coefficients d'influence et la m
Séances de cours associées (489)
Introduction à la mécanique structurale
Introduit les bases de la mécanique structurale, couvrant les fermes planes, les forces internes et l'analyse de l'équilibre.
Compression des données et théorème de Shannon: Codes Huffman
Explore les performances de l'algorithme Shannon-Fano et introduit des codes Huffman pour une compression efficace des données.
Compression des données et entropie : Conclusion
Couvre la définition de l'entropie, l'algorithme de Shannon-Fano et les sujets à venir.