Ê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
Codage par plages
Résumé
Le codage par plages ou codage par longueur de plage(appelé en anglais Run-Length Encoding/RLE) est un algorithme de compression de données sans perte qui repose sur l'idée de comprimer des plages de valeurs identiques en signalant le nombre de fois qu'une valeur donnée devrait être répétée.
Considérons un ensemble de données contenant des plages de valeurs répétées comme suit.
aaaabcccccd
Cet ensemble pourrait être représenté ainsi par un système de codage par plages:
a4b1c5d1
Dans cette représentation, des caractères ont été épargnés aux deux endroits dans l'ensemble où se trouvaient des caractères répétés. Cependant, comme chaque caractère est suivi d'un nombre de répétitions, un caractère a été rajouté aux deux emplacements ou se trouvaient des caractères n'étant pas répétés. Une approche pour éviter cet inconvénient pourrait être d'utiliser un caractère spécifique pour signaler une répétition:
a4b*c5d
Cependant, cette approche a pour défaut de nécessiter un caractère de plus pour chaque répétition; l'algorithme devient donc inutile pour des plages de moins de quatre valeurs identiques. Par ailleurs, selon la façon dont une telle approche est implémentée, il est possible que l'on doive lui dédier un caractère, qui ne pourra donc pas apparaître dans l'ensemble de données puisqu'il sera réservé à la signalisation des répétitions. Une solution à ce deuxième problème serait de plutôt signaler la présence d'un nombre de répétitions en répétant d'abord la valeur un certain nombre de fois dans l'ensemble comprimé.
Le format BMP de Windows et OS/2 permet d'utiliser la compression RLE pour les images en 1, 4 et 8 bits/pixel (respectivement noir & blanc, 16 couleurs et 256 couleurs).
Le format PCX utilise également le principe de la compression RLE pour les images en 8 et 24 bits/pixel. Dans le cas des images en 24 bits/pixel, l'image est en fait découpée en trois plans de couleur (rouge, vert et bleu) où chaque plan est encodé comme une image en 8 bits/pixel.
Le codage par longueur de plage est aussi utilisé pour les fax Groupe 3 et Groupe 4 (Recommandations ITU-T T.
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.
Concepts associés (5)
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.
Algorithme de compression sans perte
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.
Graphics Interchange Format
Le Graphics Interchange Format (littéralement « format d'échange d'images »), plus connu sous l'acronyme GIF (prononcé en français : , ou ), est un format d' couramment utilisé sur Internet. Le format GIF a été mis au point en 1987 par le groupe CompuServe, dirigé par l'informaticien Steve Wilhite , pour permettre le téléchargement d'images en couleur. Ce format utilise l'algorithme de compression sans perte LZW, nettement plus efficace que l'algorithme RLE utilisé par la plupart des formats alors disponibles (PCX, ILBM puis BMP).
Cours associés (2)
COM-102: Advanced information, computation, communication II
Text, sound, and images are examples of information sources stored in our computers and/or communicated over the Internet. How do we measure, compress, and protect the informatin they contain?
COM-406: Foundations of Data Science
We discuss a set of topics that are important for the understanding of modern data science but that are typically not taught in an introductory ML course. In particular we discuss fundamental ideas an