Compression Statistique

Frederic Koriche

Description

Compression Statistique
Frederic Koriche
Cours Théorie de l’Information
Compression: partie II
Université Montpellier II, France
[e-mail]Concepts Généraux Compression Statistique
Compression de Huffman Codes Préfixes de Shannon Faro Arbres Pondérés
Outline
1 Concepts Généraux
Compression Statistique
Codes Préfixes
Arbres Pondérés
2 Compression de Huffman
L’algorithme
Propriétés
3 Compression de Shannon Faro
L’algorithme
Propriétés
Cours Compression II Compression StatistiqueConcepts Généraux Compression Statistique
Compression de Huffman Codes Préfixes de Shannon Faro Arbres Pondérés
Source
Ensemble de mots S. Le plus souvent les
mots sont des char (8 bits).
Table de fréquences
Table qui associe à tout mot de la source
son nombre d’occurrences dans la source.abracadabra
Le f(x) peut être
Source
remplacé par la probabilité d’occurrence:
f(x)
p(x) =
|S|
Compression Statistique
Trouver un codage préfixe de la source qui
tienne compte de la probabilité
d’occurrence de chaque mot.
Cours Compression II Compression StatistiqueConcepts Généraux Compression Statistique
Compression de Huffman Codes Préfixes de Shannon Faro Arbres Pondérés
Source
Ensemble de mots S. Le plus souvent les
mots sont des char (8 bits).
abracadabra
Source Table de fréquences
Table qui associe à tout mot de la source
son nombre d’occurrences dans la.
Le f(x) peut êtremot poids
remplacé par la probabilité d’occurrence:
a 5
b 2 f(x)
p(x) =c 1 |S|
d 1
r 2
Compression ...

Sujets

• Liste des indicatifs téléphoniques internationaux par indicatif
• Propriété Camalon
• Feuille de style
• Compression et détente adiabatique
• Liste des généraux de la Révolution et du Premier Empire
• N?ud

Informations

• Publié par: Shuwyur
• Nombre de lectures: 100
• Langue: Français

Extrait

CompressionStatistique FredericKoriche CoursThéoriedel’Information Compression:partieII UniversitéMontpellierII,France [e-mail]

3 CompressiondeShannon-Faro L’algorithme Propriétés 2 CompressiondeHuffman L’algorithme Propriétés ConceptsGénéraux CompressionStatistique CodesPréfixes ArbresPondérés 1 Outline euqitsitatSnoisserpmoCIInoisserpmoCsruoC sérédnoPserbrA sexfiérPsedoC euqitsitatSnoisserpmoC oraF-nonnahSednoisserpmoC namffuHednoisserpmoC xuarénéGstpecnoC

abracadabra Source Source EnsembledemotsS.Leplussouventles motssontdeschar(8bits). p ( x )= f | ( S x | ) Tabledefréquences Tablequiassocieàtoutmotdelasource sonnombred’occurrencesdanslasource. Lenombred’occurrences f ( x )peutêtre remplacéparlaprobabilitéd’occurrence: CompressionStatistique Trouveruncodagepréfixedelasourcequi tiennecomptedelaprobabilité d’occurrencedechaquemot. sérédnoPserbrA sexfiérPsedoC euqitsitatSnoisserpmoC oraF-nonnahSednoisserpmoC namffuHednoisserpmoC xuarénéGstpecnoC euqitsitatSnoisserpmoCIInoisserpmoCsruoC

abracadabra Source motpoids 5a 2b 1c 1d 2r Tabledefréquences Source EnsembledemotsS.Leplussouventles motssontdeschar(8bits). Tabledefréquences Tablequiassocieàtoutmotdelasource sonnombred’occurrencesdanslasource. Lenombred’occurrences f ( x )peutêtre remplacéparlaprobabilitéd’occurrence: p ( x )= f ( x ) | S | CompressionStatistique Trouveruncodagepréfixedelasourcequi tiennecomptedelaprobabilité d’occurrencedechaquemot. euqitsitatSnoisserpmoCIInoisserpmoCsruoC sérédnoPserbrA sexfiérPsedoC euqitsitatSnoisserpmoC oraF-nonnahSednoisserpmoC namffuHednoisserpmoC xuarénéGstpecnoC

Source EnsembledemotsS.Leplussouventles motssontdeschar(8bits). C Tabledefréquences Tablequiassocieàtoutmotdelasource sonnombred’occurrencesdanslasource. Lenombred’occurrences f ( x )peutêtre remplacéparlaprobabilitéd’occurrence: p ( x )= f ( x ) | S | n CompressionStatistique Trouveruncodagepréfixedelasourcequi tiennecomptedelaprobabilité d’occurrencedechaquemot. amffuHednoisserpmoC xuarénéGstpecnoC euqitsitatSnoisserpmoCIInoisserpmoCsruoC sérédnoPserbrA sexfiérPsedoC euqitsitatSnoisserpmoC oraF-nonnahSednoisserp abracadabra Source m motpoidscode 05a 012b d c 1 1 1 1 0 0 1 0 1112r Codagepréfixe o

sérédnoPserbrA sexfiérPsedoC euqitsitatSnoisserpmoC oraF-nonnahSednoisserpmoC namffuHednoisserpmoC xuarénéGstpecnoC euqitsitatSnoisserpmoCIInoisserpmoCsruoC tom a b c d e edoc 000 100 010 110 001 10 010 0 a 0 1 c b 0 1 e d CodePréfixe Lecodaged’unensembledemotsSest appelécodepréfixesiaucuncoded’un motde S n’estlepréfixeducoded’un autremotde S . Arbredecodage Unarbredecodagepourunensemblede mots S estunarbrebinairevérifiantles propriétéssuivantes: chaquebrancheestétiquetéepar0 oupar1, chaquefeuilleestétiquetéeparun motde S , lecodecorrespondantàunefeuille de S estlecheminparcourudepuisla racinejusqu’àlafeuille.

sérédnoPserbrA sexfiérPsedoC euqitsitatSnoisserpmoC oraF-nonnahSednoisserpmoC namffuHednoisserpmoC xuarénéGstpecnoC euqitsitatSnoisserpmoCIInoisserpmoCsruoC tom a b c d e edoc 000 100 010 110 001 10 010 0 a 0 1 c b 1 0 e d CodePréfixe Lecodaged’unensembledemotsSest appelécodepréfixesiaucuncoded’un motde S n’estlepréfixeducoded’un autremotde S . Arbredecodage Unarbredecodagepourunensemblede mots S estunarbrebinairevérifiantles propriétéssuivantes: chaquebrancheestétiquetéepar0 oupar1, chaquefeuilleestétiquetéeparun motde S , lecodecorrespondantàunefeuille de S estlecheminparcourudepuisla racinejusqu’àlafeuille.

euqitsitatSnoisserpmoCIInoisserpmoCsruoC sérédnoPserbrA sexfiérPsedoC euqitsitatSnoisserpmoC oraF-nonnahSednoisserpmoC namffuHednoisserpmoC xuarénéGstpecnoC 2 L’arbreseconstruitenlisantlescodesdegaucheàdroiteetenformant desnoeudsinternesjusqu’àobtenirlesfeuilles. 1 Lapropriétéd’arbreimpliquequ’unefeuillenepeutpasapparaîtredans lechemind’uneautrefeuille. SchemadePreuve Lecodeconstruitparunarbredecodageestpréfixe.Inversemment,pour toutcodepréfixe,ilexisteunarbredecodagelereprésentant. Théorème

sérédnoPserbrA sexfiérPsedoC euqitsitatSnoisserpmoC oraF-nonnahSednoisserpmoC namffuHednoisserpmoC xuarénéGstpecnoC euqitsitatSnoisserpmoCIInoisserpmoCsruoC 2 L’arbreseconstruitenlisantlescodesdegaucheàdroiteetenformant desnoeudsinternesjusqu’àobtenirlesfeuilles. 1 Lapropriétéd’arbreimpliquequ’unefeuillenepeutpasapparaîtredans lechemind’uneautrefeuille. SchemadePreuve Lecodeconstruitparunarbredecodageestpréfixe.Inversemment,pour toutcodepréfixe,ilexisteunarbredecodagelereprésentant. Théorème

sérédnoPserbrA sexfiérPsedoC euqitsitatSnoisserpmoC oraF-nonnahSednoisserpmoC namffuHednoisserpmoC xuarénéGstpecnoC euqitsitatSnoisserpmoC 1 I 0 I 0 n 10 o 0 i a 5 s 1010 b 2 c 32 d 1 e 0 s W(T)=66 e motcodepoids 5000a b c 0 0 0 1 1 03 2 2110d e10010 r où l i estlalongueurduchemindela racineàlafeuille i . p X W ( T )= l i w i i ∈ leaf ( T ) m Arbredecodagepondéré Unarbredecodagepondéréestunarbre decodagedontchaquefeuillepossèdeun poids.Lepoidsdel’arbreTestdéfinipar: o Arbredecodageoptimal Etantdonnéunensemble S demots pondérés,unarbredecodage T est optimalpourSsiW(T)estleminimumdes poidsdetouslesarbresdecodage possiblespourS. CsruoC

euqitsitatSnoisserpmoCIInoisserpmoCsruoC sérédnoPserbrA sexfiérPsedoC euqitsitatSnoisserpmoC oraF-nonnahSednoisserpmoC namffuHednoisserpmoC xuarénéGstpecnoC 10 010 0 a 5 1010 2 b 3 c 2 d 1 e 0 W(T)=66 motcodepoids 5000a b c0 0 1 0 0 1 3 2 2110d e10010 où l i estlalongueurduchemindela racineàlafeuille i . X W ( T )= l i w i i ∈ leaf ( T ) Arbredecodagepondéré Unarbredecodagepondéréestunarbre decodagedontchaquefeuillepossèdeun poids.Lepoidsdel’arbreTestdéfinipar: Arbredecodageoptimal Etantdonnéunensemble S demots pondérés,unarbredecodage T est optimalpourSsiW(T)estleminimumdes poidsdetouslesarbresdecodage possiblespourS.