[PDF] ExamendeTP:codagedeHuffman

Série d’exercices 2 : code de Huffman Problème 1

le canal en considérant le code de Huffman obtenu dans le problème 1 Problème 4 Considérons un alphabet composé des 26 lettres minuscules Traer l’arre de Huffman adaptatif après le traitement de la séquene [b b s e w b s l] Mettez à jour le code de chaque lettre après chaque lecture et générer la séquence binaire résultante

ExamendeTP:codagedeHuffman

Une fois l’arbre de Huffman construit, vous pouvez attaquer l’encodage et le décodage d’une chaîne de caractèresviacetarbre 5 3 1Décodage Le décodage est l’opération la plus simple Elle prend en paramètre l’adresse du nœud racine de l’arbre de

Cours/TD 3 Codage Huffman

1 2 Approximation de l’entropie par codage en blocs Limitations du codage de Huffman – Le codage de Huffman impose d’utiliser un nombre entier de bits pour un symbole source ⇒ codage Huffman sur des blocs de n symboles On montre alors qu’on peut s’approcher de facon plus fine de l’entropie

Codage de Huffman - projeteuorg

Le codage de Huffman est une méthode de compression statistique de données qui permet de réduire la longueur du codage d'un alphabet Le code de Huffman (1952) est un code de longueur variable optimal, c'est-à-dire tel que la longueur moyenne d'un texte codé soit minimale On observe ainsi des réductions de taille de l'ordre de 20 à 90

Corrigé : codage de Huffman Partie ICodage d’une suite de

option informatique Corrigé : codage de Huffman Partie I Codage d’une suite de caractères Question 1 a) Commençons par écrire une fonction assoc de type char >clef >code telle que assoc u c renvoie le codage du

CODAGE ET COMPRESSION D IMAGES SANS PERTES

Exercice 1 (Codage de Huffman) Dans cette exercice nous allons appliquer à l’image le codage de Huffman en considérant les couleurs comme l’alphabet de la source Pour toute lecture, l’image sera parcourue "ligne par ligne" en commençant par le coin en haut à gauche 1

Algo L3 Info Travaux dirigés, séance 101 Compression

Codage de longueur variable Construire avec l’algorithme de Huffman un codage de longueur variable pour A Donner l’arbre de codage correspondant et le tableau des codes Calculer la longueur moyenne du co-dage et commenter le résultat en une phrase Réponse 0 : Après avoir fait tourner Huffman (on peut avoir plusieurs solutions) on obtient

APMM TD correction - Fournier-Sniehotta

Ce codage n’est pas complet, car l’ensemble des mots de code est un sous-ensemble du codage complet de taille 5 : {0, 100, 101, 110, 111} Les codages {0, 10, 110, 111} et {00, 01, 10, 11} sont complets donc mieux adaptés 2 CODAGES COMPRESSIFS: SHANNON, FANO-SHANNON ET HUFFMAN

Cours/TD 4 Compression par transform´ee Codage JPEG

Codage JPEG 1 Compression par transform´ee : transform´ee, quanti-fication, codage pr`es de l’entropie 1 1 Transform´ees Bases orthogonales Definition Soit E

Examen Théorie de l’Information

I - Exercice codage de source (25 minutes) Une source binaire génère les symboles s1 et s2 avec les probabilité p(s1)=0,9 et p(s2)=0,1 Les deux symboles sont indépendants a) Calculer l’entropie de cette source binaire Î H(S) = 0,469 bit/symbole b) Calculer l’entropie de la source étendue, constituée de n=3 symboles de la source

[PDF] codage arithmétique pdf

[PDF] codage arithmétique algorithme

[PDF] représentation des nombres signés exercices corrigés

[PDF] exercice de systeme de numeration

[PDF] système binaire informatique

[PDF] calcul nombre binaire

[PDF] cours sur le calcul binaire pdf

[PDF] codage et représentation de l'information exercices corrigés

[PDF] le codage informatique

[PDF] exercice corrigé codage source

[PDF] combien d'information sont représentées par 15 bits

[PDF] virgule fixe et virgule flottant pdf

[PDF] virgule fixe exercices corrigés

[PDF] exercice corrigé codage virgule fixe

[PDF] virgule flottant ieee 754

Université Claude Bernard - Lyon1 Licence Sciences et Technologies - L3 Algorithmique, Programmation et Complexité - LIFAP6 Printemps 2017

Examen de TP : codage de Huffman

Durée : 3 heures.

1

Co dagede Huffman

Le codage de Huffman est un procédé très utilisé en compression de données. Il sert à encoder un texte en

binaire, en utilisant pour chaque lettre un nombre de bits dépendant du nombre de fois où la lettre est présente :

plus la lettre apparaît, plus le nombre de bits est petit. Ainsi, le nombre total de bits utilisés pour encoder le

texte est réduit par rapport à un codage ASCII standard qui utilise huit bits pour chaque lettre.

1.1

Arbres binaires

Le code binaire associé à chaque lettre est défini par un arbre binaire. Les feuilles de l"arbre correspondent aux

lettres de l"alphabet. Les noeuds interne ne contiennent pas d"information. Le chemin emprunté pour atteindre

une feuille depuis la racine définit le code de la lettre sur cette feuille : à gauche 0, à droite 1. Par exemple :a0

b0 p0 r111a!0 b!10 p!110 r!111 barbapapa!10011110011001100 1.2

Optimisation du co de

Lorsque le texte à encoder est connu, il est possible d"optimiser l"arbre binaire utilisé pour raccourcir les codes

des lettres les plus fréquentes. C"est ce que fait l"algorithme de Huffman : il commence par compter dans le

texte le nombre d"apparitions de chaque caractère. Par exemple, dans la phrase : je veux et j"exige d"exquises excuses nous avons : e : 9 ␣ : 5s : 4 x : 4u : 3 i : 2j : 2 " : 2c : 1 d : 1g : 1 q : 1t : 1 v : 1 où " ␣ » est le caractère espace, et " " » est l"apostrophe.

À partir de ces fréquences, l"algorithme initialise un arbre par caractère, avec comme poids le nombre d"ap-

paritions du caractère :9 e5 ␣4 s4 x3 u2 i2 j2 "1 c1 d1 g1 q1 t1 v

Dans la suite, nous indiquerons le poids d"un sous-arbre au niveau du noeud interne où il est enraciné.

À chaque itération, l"algorithme sélectionne les deux arbres ayant les poids les plus faibles, et les assemble

pour former les deux enfants d"un arbre binaire dont le poids est la somme des deux arbres. Lorsque plusieurs

arbres sont à égalité pour le poids le plus faible, l"arbre sélectionné parmi eux peut être n"importe lequel. Ainsi,

à la première itération, nous pourrions obtenir : 9 e5 ␣4 s4 x3 u2 i2 j2 "1 c1 d1 g1 q2 1 t1 v et après quatre itérations de plus : 9 e5 ␣4 s4 x3 u4 2 1 c1 d2 "4 2 i2 j2 1 g1 q2 1 t1 v

Lorsqu"il ne reste plus qu"un seul arbre, l"algorithme est terminé. Plus formellement, l"algorithme de Huffman

est le suivant : FonctionHuffman!arbredonnées :l"alphabet et les fréquences de chaque lettre résultat :l"arbre binaire du codage de Huffman

Algorithmecréer une file à priorités

pour chaquecaractèrecde l"alphabetfairecréer un arbrea a.caractère c a.poids fréquence dec

ajouteraà la file à prioritéstant quela file à priorités contient plus d"un arbrefairecréer un arbrea

a.gauche l"arbre de poids le plus faible de la file à priorités (que l"on retire de la file) a.droite l"arbre de poids le plus faible de la file à priorités (que l"on retire de la file) a.poids a.gauche.poids+a.droite.poids

ajouteraà la file à prioritésretournerle seul arbre contenu dans la file à priorités2Base de co de

Nous vous fournissons une archive de base, munie de tous les fichiers à remplir, du Makefile pour les compiler.

Vous n"avez pas normalement besoin d"ajouter de fichiers supplémentaires. 3

Mo dalitésde rendu

Votre code est a rendre sous la forme d"une archive via Tomusshttps://tomuss.univ-lyon1.fr. Le Makefile

dispose d"une règle pour générer l"archive pour vous :make archive

Cette commande crée une archive avec votre nom d"utilisateur comme nom, et y intègre le Makefile ainsi

que tous les fichierscppethpp. 4

Lib ertéd"action et conseils

Pour ce TP, vous êtes autorisés à utiliser toutes les fonctionnalités de la librairie standard. Vous êtes également

autorisés à consulter la documentation en ligne. Vous n"êtes par contre pas autorisés à communiquer entre vous,

oralement ou via votre poste de travail ou votre téléphone. Le code que vous produirez devra rester le votre.

Vous ne recevrez pas de points pour une implémentation tout prête récupérée en ligne. Cela ne vous empêche

pas de vous en inspirer, mais prenez garde à mentionner vos sources car ne pas le faire constitue un plagiat.

Nous sommes conscients que quel que soit le soin que nous mettons à la rédaction du sujet, il est probable

que certaines questions ne soient pas claires pour vous. N"hésitez donc pas à demander à votre encadrant de

clarifier une question pour vous. De même il est parfois difficile d"évaluer la difficulté et le temps nécessaire

pour répondre aux questions. Selon les rendus que nous recevrons, nous en tiendrons compte dans la notation

en notant éventuellement sur plus de 20.

Ne jetez pas votre code s"il ne marche pas. Laissez le en commentaire et mentionnez dans vos commentaires

ce que vous avez fait pour essayer de trouver l"erreur, éventuellement les messages d"erreur qui vous semblent

significatifs et ce que vous en avez déduit. Le bonnes choses présentes dans ces commentaires pourront ainsi

éventuellement vous bénéficier.

5

V otretra vail

5.1

Structure de données de b ase

Pour représenter un arbre de Huffman, vous complèterez la structure présente dans le fichierhuffman.hpp.

La structureHArbrereprésente à la fois un noeud de l"arbre et l"arbre tout entier, donné par sa racine. Chaque

noeud comporte : l"adresse de son enfan tg auche; l"adresse de son enfan tdro it; un p oids; un caractère (q uin"est utilisé q uesi le noeud est une feuille). 5.2

Initialisation d"un noeud

Le squelette de code fourni comporte trois fonctions d"initialisation des noeuds. Ces fonctions réalisent l"allo-

cation du nouveau noeud et renvoient son adresse. 5.2.1

Initial isationà partir d"un caractère

Cette fonction est utilisée pour initialiser les feuilles de l"arbre. Le poids à fournir est le nombre de fois où le

caractère est apparu dans le texte à partir duquel l"arbre est créé. La fonction réalise l"allocation du noeud sur

le tas, initialise ses champs et renvoie l"adresse du noeud créé. 5.2.2

Initial isationà partir des enfan ts

Cette fonction sert à construire l"arbre selon le principe de Huffman. À partir des deux sous-arbres à assembler,

un nouveau noeud est alloué pour leur servir de parent, et pour encoder le poids de l"arbre résultant. Ce

noeud ne représente pas de caractère particulier, seules les feuilles correspondent à un caractère. Comme pour

l"initialisation à partir d"un caractère, le nouveau noeud est alloué sur le tas et son adresse est renvoyée par la

fonction. 5.2.3 Initial isationà partir d"une c haînede caractères

Cette fonction est celle qui construit réellement l"arbre via l"algorithme de Huffman. Elle prend en paramètre

la chaîne de caractères à encoder, calcule le nombre d"apparitions de chaque lettre, initialise les feuilles de

l"arbre, puis réalise la fusion progressive des arbres jusqu"à obtenir un arbre unique. C"est l"adresse du noeud

racine de cet arbre qui est renvoyée. Nous vous conseillons de procéder par étapes : lister l"ensem bledes caractères présen tsainsi que leur nom bred"apparitions ; initialiser les feuilles de l"arbre et les insérer dans la file a priorité ; réaliser la fusion progressiv edes arbres.

Pour chacune de ces étapes, vérifiez bien que le résultat est correct avant de passer à la suivante.

La chaîne de caractères en entrée est fournie via le typestd::string. Ce type se comporte comme un tableau,

avec quelques outils en plus. Vous pouvez récupérer la taille de la chaîne de caractères viaint taille = s.size() ;

et vous pouvez accéder au i

èmecaractère viachar c = s[i] ;

Notez que les caractères sont des nombres codés sur 8 bits, donc entre 0 et 255. Vous pouvez donc facilement

compter les caractères en initialisant un tableau de 256 zéros et en y accédant en utilisant le caractère. Par

exemple :tab["a"] = 12 ; //inscrire 12 dans la case du tableau correspondant au caractere a

Pour réaliser la fusion des arbres via la file a priorité, nous vous proposons une file a priorité dans les fichiers

huff_heap.[hc]pp. Si vous vous sentez plus à l"aise avec une autre structure de données, vous n"êtes pas

obligés de l"utiliser, mais nous vous le recommandons fortement. Pour que cette structure fonctionne, vous

devez avoir codé correctement la fonctionhuff_poids(HArbre* a). Cette fonction renvoie simplement le poids

du sous-arbre, selon la façon dont vous l"avez stockée dans votre arbre. 5.3

Enco dageet déco dage

Une fois l"arbre de Huffman construit, vous pouvez attaquer l"encodage et le décodage d"une chaîne de

caractères via cet arbre. 5.3.1

Déco dage

Le décodage est l"opération la plus simple. Elle prend en paramètre l"adresse du noeud racine de l"arbre de

Huffman ayant servi à encoder. Il prend également en paramètre le code à décoder, fourni sous la forme d"un

tableau de bits via le typestd::vector. Pour parcourir ce tableau, vous pouvez obtenir sa taille viaint taille = code.size() ;

et pour accéder au i èmeélément, le vector se comporte comme un tableau :bool bit = code[i] ;

Le dernier paramètre est la chaîne de caractères à remplir. Pour ajouter un caractère dans cette chaîne, vous

pouvez utilisers.push_back("a") ; //ajout du caractere a en fin de chaine

L"algorithme pour le décodage consiste donc à utiliser les bits du code un par un dans l"ordre pour descendre

dans l"arbre à droite ou à gauche. Dès qu"une feuille est atteinte, le caractère de cette feuille est ajouté à la

chaîne de caractères de sortie, et le parcours de l"arbre redémarre de la racine. 5.3.2

Enco dagesimple mais coûteux

L"encodage est un peu plus compliqué. Nous vous proposons tout d"abord une version simple. La fonction

d"encodage prend en paramètre l"adresse du noeud racine de l"arbre de Huffman à utiliser, la chaîne de caractères

à encoder, et le tableau dynamique de bits (booléens) à remplir.out.push_back(true) ; // ajout d"un 1

out.push_back(false) ; // ajout d"un 0

Nous vous proposons de commencer par écrire une fonction qui prend en paramètre un noeud de Huffman

et un caractère, et qui renvoie un booléen indiquant si le caractère correspond à l"une des feuilles descendantes

du noeud. De cette manière, depuis la racine, vous pouvez déterminer le premier bit du code d"un caractère

en regardant s"il se trouve dans le sous-arbre de gauche ou de droite. Une fois le premier bit déterminé, vous

pouvez descendre dans le sous-arbre correspondant et recommencer pour déterminer le second bit, jusqu"à vous

trouver sur la feuille correspondant au caractère. 5.3.3

Enco dageamélio ré

L"algorithme précédent calcule de multiples fois la même chose en lançant de multiples recherches d"un

caractère. De plus chaque recherche va potentiellement explorer tous les noeuds du sous-arbre sur lequel elle

est lancée. Pour améliorer l"algorithme précédent, vous pouvez commencer par lister les feuilles de l"arbre, leurs

caractères, et les code associés. Comme lors de la construction de l"arbre, vous pouvez vous aider d"un tableau

de taille 256 pour associer des informations à des caractères.quotesdbs_dbs29.pdfusesText_35