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. Des méthodes plus complexes réalisant une modélisation probabiliste de la source permettent d'obtenir de meilleurs ratios de compression.

Il a été inventé par David Albert Huffman, et publié en 1952.

Principe

Le principe du codage de Huffman repose sur la création d'une structure d'arbre composée de nœuds.

Supposons que la phrase à coder est « this is an example of a huffman tree ». On recherche tout d'abord le nombre d'occurrences de chaque caractère. Dans l'exemple précédent, la phrase contient 2 fois le caractère h et 7 espaces. Chaque caractère constitue une des feuilles de l'arbre à laquelle on associe un poids égal à son nombre d'occurrences.

L'arbre est créé de la manière suivante, on associe chaque fois les deux nœuds de plus faibles poids, pour donner un nouveau nœud dont le poids équivaut à la somme des poids de ses fils. On réitère ce processus jusqu'à n'en avoir plus qu'un seul nœud : la racine. On associe ensuite par exemple le code 0 à chaque embranchement partant vers la gauche et le code 1 vers la droite.

Un exemple d'arbre de Huffman, généré avec la phrase « this is an example of a huffman tree ».

Pour obtenir le code binaire de chaque caractère, on remonte l'arbre à partir de la racine jusqu'aux feuilles en rajoutant à chaque fois au code un 0 ou un 1 selon la branche suivie. La phrase « this is an example of a huffman tree » se code alors sur 135 bits au lieu de 288 bits (si le codage initial des caractères tient sur 8 bits). Il est nécessaire de partir de la racine pour obtenir les codes binaires car sinon lors de la décompression, partir des feuilles peut entraîner une confusion lors du décodage.

Pour coder « Wikipedia », nous obtenons donc en binaire : 101 11 011 11 100 010 001 11 000, soit 24 bits au lieu de 63 (9 caractères x 7 bits par caractère) en utilisant les codes ASCII (7 bits).

Différentes méthodes de construction de l'arbre

Il existe trois variantes de l'algorithme de Huffman, chacune d'elles définissant une méthode pour la création de l'arbre :

  1. statique : chaque octet a un code prédéfini par le logiciel. L'arbre n'a pas besoin d'être transmis, mais la compression ne peut s'effectuer que sur un seul type de fichier (ex. : un texte en français, où les fréquences d'apparition du 'e' sont énormes ; celui-ci aura donc un code très court, rappelant l'alphabet morse) ;
  2. semi-adaptatif : le fichier est d'abord lu, de manière à calculer les occurrences de chaque octet, puis l'arbre est construit à partir des poids de chaque octet. Cet arbre restera le même jusqu'à la fin de la compression. Cette compression occasionnera un gain de bits supérieur ou égal au codage de Huffman statique mais il sera nécessaire, pour la décompression, de transmettre l'arbre, ce qui annulera généralement le gain obtenu[1] ;
  3. adaptatif : c'est la méthode qui offre a priori les meilleurs taux de compression car il utilise un arbre connu (et ainsi non transmis) qui sera ensuite modifié de manière dynamique au fur et à mesure de la compression du flux selon les symboles précédemment rencontrés[1]. Cette méthode représente cependant le gros désavantage de devoir modifier souvent l'arbre, ce qui implique un temps d'exécution plus long. Par contre, la compression est toujours optimale et il n'est pas nécessaire que le fichier soit connu avant de compresser. En particulier, l'algorithme est capable de travailler sur des flux de données (streaming), car il n'est pas nécessaire de connaître les symboles à venir.

Propriétés

Un code de Huffman est un code de source. Pour une source , représentée par une variable aléatoire , de distribution de probabilité , l'espérance de la longueur d'un code est donnée par

est la longueur du mot de code, le code associé au symbole de source , et est l'ensemble des symboles de source.

Un code de Huffman est un code préfixe à longueur variable. Il est optimal, au sens de la plus courte longueur, pour un codage par symbole[2]. C'est-à-dire que pour un code de Huffman , et pour tout code uniquement décodable, alors :

Limitations du codage de Huffman

On peut montrer que pour une source , d'entropie de Shannon la longueur moyenne d'un mot de code obtenu par codage de Huffman vérifie :

Cette relation montre que le codage de Huffman s'approche de l'entropie de la source et c'est-à-dire du code optimum mais cela peut s'avérer en fait assez peu intéressant dans le cas où l'entropie de la source est forte, et où un surcoût de 1 bit devient important. De plus le codage de Huffman impose d'utiliser un nombre entier de bit pour un symbole source, ce qui peut s'avérer peu efficace.

Une solution à ce problème est de travailler sur des blocs de symboles. On montre alors qu'on peut s'approcher de façon plus fine de l'entropie :

mais le processus d'estimation des probabilités devient plus complexe et coûteux.

De plus, le codage de Huffman n'est pas adapté dans le cas d'une source dont les propriétés statistiques évoluent au cours du temps, puisque les probabilités des symboles se modifient et le codage devient inadapté. La solution consistant à ré-estimer à chaque itération les probabilités symboles est impraticable du fait de sa complexité en temps. La technique devient alors le codage Huffman adaptatif : à chaque nouveau symbole la table des fréquences est remise à jour et l'arbre de codage modifié si nécessaire. Le décompresseur faisant de même pour les mêmes causes… il reste synchronisé sur ce qu'avait fait le compresseur.

En pratique, lorsque l'on veut s'approcher de l'entropie, on préfèrera un codage arithmétique qui est optimal au niveau du bit.

Des méthodes plus complexes réalisant une modélisation probabiliste de la source et tirant profit de cette redondance supplémentaire permettent d'améliorer les performances de compression de cet algorithme (voir LZ77, prédiction par reconnaissance partielle, pondération de contextes).

Code canonique

Pour un même ensemble de symboles à coder, plusieurs codes de Huffman différents peuvent être obtenus.

Il est possible de transformer un code de Huffman en un code de Huffman canonique qui est unique pour un ensemble de symboles d'entrée donné. Le principe est d'ordonner au départ les symboles dans l'ordre lexical.

Remarque: entre deux symboles S1 et S2 qui, dans un code de Huffman spécifique, sont codés de la même longueur sont toujours codés de la même longueur dans le code Huffman canonique. Dans le cas où deux symboles ont la même probabilité et deux longueurs de code différentes, il est possible que le passage d'un code de Huffman à un code de Huffman canonique modifie la longueur de ces codes, afin de garantir l'attribution du code le plus court au premier symbole dans l'ordre lexicographique.

Utilisations

Le codage de Huffman ne se base que sur la fréquence relative des symboles d'entrée (suites de bits) sans distinction pour leur provenance (images, vidéos, sons, etc.). C'est pourquoi il est en général utilisé au second étage de compression, une fois la redondance propre au média mise en évidence par d'autres algorithmes. On pense en particulier à la compression JPEG pour les images, MPEG pour les vidéos et MP3 pour le son, qui peuvent retirer les éléments superflus imperceptibles pour les humains. On parle alors de compression non conservative (avec pertes).

D'autres algorithmes de compression, dits conservatifs (sans pertes), tels que ceux utilisés pour la compression de fichiers, utilisent également Huffman pour comprimer le dictionnaire résultant. Par exemple, LZH (Lha) et deflate (ZIP, gzip, PNG) combinent un algorithme de compression par dictionnaire (LZ77) et un codage entropique de Huffman.

Histoire

Le codage a été inventé par David Albert Huffman, lors de sa thèse de doctorat au MIT. L'algorithme a été publié en 1952 dans l'article A Method for the Construction of Minimum-Redundancy Codes, dans les Proceedings of the Institute of Radio Engineers[3].

Les premiers Macintosh de la société Apple utilisaient un code inspiré de Huffman pour la représentation des textes : les 15 caractères les plus fréquents d'une langue étaient codés sur 4 bits, et la 16e configuration servait de préfixe au codage des autres sur un octet (ce qui faisait donc tantôt 4 bits, tantôt 12 bits par caractère, voir UTF-8). Cette méthode simple permettait d'économiser 30 % d'espace sur un texte moyen, à une époque où la mémoire vive restait encore un composant coûteux.

Voir aussi

Articles connexes

Liens externes

Bibliographie

Notes et références

  1. a et b Mark Nelson (trad. Soulard Hervé), La Compression des données : Texte, Images, Sons, France, Dunod, , 420 p. (ISBN 2-10-001681-4), page 65.
  2. Cover, Thomas (2006), p. 123-127.
  3. D.A. Huffman, A method for the construction of minimum-redundancy codes, Proceedings of the I.R.E., septembre 1952, pp. 1098-1102.

Read other articles:

TanjungKelurahanNegara IndonesiaProvinsiKepulauan Bangka BelitungKabupatenBangka BaratKecamatanMuntokKodepos33311[1]Kode Kemendagri19.05.01.1001 Kode BPS1903030007 Luas24,00 km²Jumlah penduduk15.456 jiwa (2020)Kepadatan644 jiwa/km² Tanjung merupakan salah satu kelurahan yang berada di kecamatan Muntok, kabupaten Bangka Barat, provinsi Kepulauan Bangka Belitung, Indonesia. Kelurahan ini memiliki luas wilayah 24,00 km², dengan jumlah penduduk sebanyak 15.456 jiwa (2020) dan...

 

 

Déclaration de Malé Déclaration de Malé sur la dimension humaine du changement climatique mondial Adoption novembre 2007 modifier L'île de Malé, aux Maldives, dont la Déclaration porte le nom. La Déclaration de Malé sur la dimension humaine du changement climatique mondial est un traité conclu par les représentants de plusieurs petits États insulaires en développement qui se sont réunis pour signer la déclaration en novembre 2007. L'objectif de la Déclaration est de définir u...

 

 

Este artículo o sección tiene referencias, pero necesita más para complementar su verificabilidad.Este aviso fue puesto el 13 de junio de 2020. Guararé Distrito Lema: La Tierra del Chucu Chucu Coordenadas 7°49′N 80°16′O / 7.82, -80.27Capital GuararéIdioma oficial CastellanoEntidad Distrito • País  Panamá • Provincia Los SantosCorregimientos 10Eventos históricos   • Fundación 1864Superficie   • Total 215.6 km²[1]​...

ЛУЦЬКИЙ КЛІНІЧНИЙ ПОЛОГОВИЙ БУДИНОЛТип пологовий будинокЗасновано 1951Кількість ліжок 150Кількість лікарів 75Відділення 9 відділеньКраїна  УкраїнаАдреса 43005,  м. Луцьк, вул. Гулака Артемовського, 18Координати 50°45′27″ пн. ш. 25°20′30″ сх. д. / 50.75750° ...

 

 

Asedio de Amberes Guerra de los Ochenta AñosParte de guerra de los Ochenta Años Entrada de las tropas de Alejandro Farnesio en Amberes.Fecha 3 de julio de 1584 – 17 de agosto de 1585Lugar Amberes, (Bélgica Bélgica)Coordenadas 51°13′00″N 4°24′00″E / 51.2167, 4.4Resultado Victoria españolaBeligerantes Provincias Unidas Monarquía Católica Comandantes Philips van Marnix Alejandro Farnesio Juan del Águila Fuerzas en combate 100 000 habitantes[1]​60 00...

 

 

PausYohanes IVAwal masa kepausan24 Desember 640Akhir masa kepausan12 Oktober 642PendahuluSeverinusPenerusTeodorus IInformasi pribadiNama lahirtidak diketahuiLahirtanggal tidak diketahuiDalmatiaMeninggal12 Oktober 642tempat tidak diketahuiPaus lainnya yang bernama Yohanes Paus Yohanes IV (???-12 Oktober 642) adalah Paus Gereja Katolik Roma sejak 24 Desember 640 hingga 12 Oktober 642. Ia terpilih setelah empat bulan lamanya sede vacante (kekosongan tahta kepausan).[1] Referensi ^ CATHOL...

Russian chess player (born 1962) Yuri YakovichЮрий ЯковичYuri Yakovich, Warsaw 2012CountrySoviet Union → RussiaBorn (1962-11-30) November 30, 1962 (age 61)KuybyshevTitleGrandmaster (1990)FIDE rating2524 (December 2023)Peak rating2610 (July 1997) Yuri Rafailovich Yakovich (Russian: Юрий Рафаилович Якович; born November 30, 1962) is a Russian chess player. He was awarded the title of Grandmaster by FIDE in 1990. He was a member of the silver medal-...

 

 

Fictional character HinakoHinako characterHinako, as seen in her first appearance in Issho ni Training: Training with Hinako.First appearanceIssho ni Training: Training with HinakoLast appearanceIssho ni Training 026: Bathtime with Hinako & HiyokoDesigned byRyoko AmisakiIn-universe informationSpeciesHumanGenderFemale Hinako is a fictional character appearing in the three OVA anime: April 2009: Issho ni Training: Training with Hinako February 2010: Issho ni Sleeping: Sleeping with Hinako D...

 

 

Pub in Roehampton, London King's Head, Roehampton The King's Head is a Grade II listed public house at 1 Roehampton High Street, Roehampton, London SW15 4HL.[1] It dates back to the 17th century, although altered and extended since then.[1] References ^ a b Historic England. King's Head Inn public house (1300007). National Heritage List for England. Retrieved 1 April 2014. Wikimedia Commons has media related to King's Head, Roehampton. vtePubs in LondonBarking and Dagenham Adm...

  Gran Premio de Aragón de 2014Detalles de carrera 14.ª prueba de 18de la Temporada 2014 del Campeonato. Datos generalesFecha 28 de septiembre de 2014Sede MotorLand AragónCircuitoTipo ylongitud Instalaciones Permanentes5.078 km / 3.155 miMotoGP Pole position Vuelta rápida Marc Márquez1:47.187[1]​ Jorge Lorenzo1:49.107[1]​ Podio Jorge Lorenzo Aleix Espargaró Cal Crutchlow Moto2 Pole position Vuelta rápida Maverick Viñales1:54.073[2]​ Thomas Lüthi1:54.2...

 

 

Head of state and of government of the U.S. state of South Dakota Governor of South DakotaSeal of South DakotaState flagIncumbentKristi Noemsince January 5, 2019Government of South DakotaStyleThe HonorableResidenceThe Governor's Mansion (official) Watertown, South Dakota (private)Term lengthFour years, renewable once consecutively[1]Inaugural holderArthur C. Mellette1889[2]FormationConstitution of South DakotaSalary$139,100.00 [3] [4]WebsiteOfficial websit...

 

 

Maya province in Yucatan from c. 950 to 1544 This article is about the Postclassic Maya province. For the modern city, see Chetumal. For the archaeological site, see Santa Rita, Corozal. Province of Chetumalu kuchkabal Chetumal (Yucatecan Mayan)ca. 950–1544 Emblem glyph of Altun Ha Map of the Province of Chetumal / known former and present settlements marked / 1957 map by R. L. Roys / via HathiTrustStatusDissolvedCapitalChichen Itza; Mayapan; ChetumalCommon languagesYucatecan MayanReli...

Season of television series ArcherSeason 7DVD coverStarring H. Jon Benjamin Judy Greer Amber Nash Chris Parnell Aisha Tyler Lucky Yates Jessica Walter Adam Reed Country of originUnited StatesNo. of episodes10ReleaseOriginal networkFXOriginal releaseMarch 31 (2016-03-31) –June 2, 2016 (2016-06-02)Season chronology← PreviousSeason 6Next →Season 8 List of episodes The seventh season of the animated television series, Archer, premiered on FX on March 31, 2016.[1...

 

 

American actress This biography of a living person needs additional citations for verification. Please help by adding reliable sources. Contentious material about living persons that is unsourced or poorly sourced must be removed immediately from the article and its talk page, especially if potentially libelous.Find sources: Chelsea Field – news · newspapers · books · scholar · JSTOR (February 2020) (Learn how and when to remove this template message) ...

 

 

NATO operation in the Horn of Africa Operation Ocean ShieldPart of Operation Enduring Freedom – Horn of AfricaUSS Farragut destroying a pirate skiff in the Gulf of Aden (March 2010)Date17 August 2009 – 24 November 2016LocationIndian Ocean, Gulf of Aden, Guardafui Channel, Arabian Sea, Red SeaResult Coalition victory Number of Somali pirate attacks have been reduced dramaticallyBelligerents  NATO  Denmark  United Kingdom  United States  France  Netherland...

Opera training program The topic of this article may not meet Wikipedia's notability guidelines for companies and organizations. Please help to demonstrate the notability of the topic by citing reliable secondary sources that are independent of the topic and provide significant coverage of it beyond a mere trivial mention. If notability cannot be shown, the article is likely to be merged, redirected, or deleted.Find sources: OperaWorks – news · newspapers · books&...

 

 

1943 film The House of RainDirected byAntonio RománWritten byWenceslao Fernández Flórez Pedro de Juan Antonio RománStarringLuis HurtadoBlanca de SilosCarmen VianceNicolás D. PerchicotCinematographyHeinrich GartnerEdited byJuan J. Doria Music byJosé Muñoz Molleda ProductioncompanyHércules FilmsDistributed byHércules FilmsRelease date4 October 1943Running time88 minutesCountrySpainLanguageSpanish The House of Rain (Spanish: La casa de la lluvia) is a 1943 Spanish drama film directed by...

 

 

Pour l’esclave dans la société scandinave médiévale, voir Thrall. Thrall (Go'el) Personnage de fiction apparaissant dansWarcraft. Thrall (7818040108).jpg Sexe Masculin Espèce Orc Cheveux Noir Yeux Bleu Activité Ancien chef de la Horde Arme favorite Marteau du Destin Classe Prophète (dans Warcraft III)Chaman (dans World of Warcraft) Faction Horde Créé par Blizzard Entertainment modifier  Statue de Thrall à la convention Blizzard de Pékin en 2006 Thrall est un personnage issu ...

Interdisciplinary science Microfluidics refers to a system that manipulates a small amount of fluids (10−9 to 10−18 liters) using small channels with sizes ten to hundreds micrometres. It is a multidisciplinary field that involves molecular analysis, molecular biology, and microelectronics.[1] It has practical applications in the design of systems that process low volumes of fluids to achieve multiplexing, automation, and high-throughput screening. Microfluidics emerged in the beg...

 

 

Michael Panaretos (Greek: Μιχαήλ Πανάρετος) (c. 1320 – c. 1390) was an official of the Trapezuntine empire and a Greek historian. His sole surviving work is a chronicle of the Trapezuntine empire of Alexios I Komnenos and his successors. This chronicle not only provides a chronological framework for this medieval empire, it also contains much valuable material on the early history of the Ottoman Turks from a Byzantine perspective, however it was almost unknown until Jakob Phi...

 

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!