Compression Statistique
33 pages
Français
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Compression Statistique

-

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
33 pages
Français

Description

Compression Statistique
Frederic Koriche
Cours Théorie de l’Information
Compression: partie II
Université Montpellier II, France
Frederic.Koriche@lirmm.fr 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

Informations

Publié par
Nombre de lectures 164
Langue Français

Exrait

CompressionStatistiqueFredericKoricheCoursThéoriedel’InformationCompression:partieIIUniversitéMontpellierII,FranceFrederic.Koriche@lirmm.fr
3CompressiondeShannon-FaroL’algorithmePropriétés2CompressiondeHuffmanL’algorithmePropriétésConceptsGénérauxCompressionStatistiqueCodesPréfixesArbresPondérés1OutlineeuqitsitatSnoisserpmoCIInoisserpmoCsruoCsérédnoPserbrAsexérPsedoCeuqitsitatSnoisserpmoCoraF-nonnahSednoisserpmoCnamffuHednoisserpmoCxuarénéGstpecnoC
abracadabraSourceSourceEnsembledemotsS.Leplussouventlesmotssontdeschar(8bits).p(x)=f|(Sx|)TabledefréquencesTablequiassocieàtoutmotdelasourcesonnombred’occurrencesdanslasource.Lenombred’occurrencesf(x)peutêtreremplacéparlaprobabilitéd’occurrence:CompressionStatistiqueTrouveruncodagepréfixedelasourcequitiennecomptedelaprobabilitéd’occurrencedechaquemot.sérédnoPserbrAsexérPsedoCeuqitsitatSnoisserpmoCoraF-nonnahSednoisserpmoCnamffuHednoisserpmoCxuarénéGstpecnoCeuqitsitatSnoisserpmoCIInoisserpmoCsruoC
abracadabraSourcemotpoids5a2b1c1d2rTabledefréquencesSourceEnsembledemotsS.Leplussouventlesmotssontdeschar(8bits).TabledefréquencesTablequiassocieàtoutmotdelasourcesonnombred’occurrencesdanslasource.Lenombred’occurrencesf(x)peutêtreremplacéparlaprobabilitéd’occurrence:p(x)=f(x)|S|CompressionStatistiqueTrouveruncodagepréfixedelasourcequitiennecomptedelaprobabilitéd’occurrencedechaquemot.euqitsitatSnoisserpmoCIInoisserpmoCsruoCsérédnoPserbrAsexérPsedoCeuqitsitatSnoisserpmoCoraF-nonnahSednoisserpmoCnamffuHednoisserpmoCxuarénéGstpecnoC
SourceEnsembledemotsS.Leplussouventlesmotssontdeschar(8bits).CTabledefréquencesTablequiassocieàtoutmotdelasourcesonnombred’occurrencesdanslasource.Lenombred’occurrencesf(x)peutêtreremplacéparlaprobabilitéd’occurrence:p(x)=f(x)|S|nCompressionStatistiqueTrouveruncodagepréfixedelasourcequitiennecomptedelaprobabilitéd’occurrencedechaquemot.amffuHednoisserpmoCxuarénéGstpecnoCeuqitsitatSnoisserpmoCIInoisserpmoCsruoCsérédnoPserbrAsexérPsedoCeuqitsitatSnoisserpmoCoraF-nonnahSednoisserpabracadabraSourcemmotpoidscode05a012bdc111100101112rCodagepréfixeo
sérédnoPserbrAsexérPsedoCeuqitsitatSnoisserpmoCoraF-nonnahSednoisserpmoCnamffuHednoisserpmoCxuarénéGstpecnoCeuqitsitatSnoisserpmoCIInoisserpmoCsruoCtomabcdeedoc000100010110001100100a01cb01edCodePréfixeLecodaged’unensembledemotsSestappelécodepréfixesiaucuncoded’unmotdeSn’estlepréfixeducoded’unautremotdeS.ArbredecodageUnarbredecodagepourunensembledemotsSestunarbrebinairevérifiantlespropriétéssuivantes:chaquebrancheestétiquetéepar0oupar1,chaquefeuilleestétiquetéeparunmotdeS,lecodecorrespondantàunefeuilledeSestlecheminparcourudepuislaracinejusqu’àlafeuille.
sérédnoPserbrAsexérPsedoCeuqitsitatSnoisserpmoCoraF-nonnahSednoisserpmoCnamffuHednoisserpmoCxuarénéGstpecnoCeuqitsitatSnoisserpmoCIInoisserpmoCsruoCtomabcdeedoc000100010110001100100a01cb10edCodePréfixeLecodaged’unensembledemotsSestappelécodepréfixesiaucuncoded’unmotdeSn’estlepréfixeducoded’unautremotdeS.ArbredecodageUnarbredecodagepourunensembledemotsSestunarbrebinairevérifiantlespropriétéssuivantes:chaquebrancheestétiquetéepar0oupar1,chaquefeuilleestétiquetéeparunmotdeS,lecodecorrespondantàunefeuilledeSestlecheminparcourudepuislaracinejusqu’àlafeuille.
euqitsitatSnoisserpmoCIInoisserpmoCsruoCsérédnoPserbrAsexérPsedoCeuqitsitatSnoisserpmoCoraF-nonnahSednoisserpmoCnamffuHednoisserpmoCxuarénéGstpecnoC2L’arbreseconstruitenlisantlescodesdegaucheàdroiteetenformantdesnoeudsinternesjusqu’àobtenirlesfeuilles.1Lapropriétéd’arbreimpliquequ’unefeuillenepeutpasapparaîtredanslechemind’uneautrefeuille.SchemadePreuveLecodeconstruitparunarbredecodageestpréfixe.Inversemment,pourtoutcodepréfixe,ilexisteunarbredecodagelereprésentant.Théorème
sérédnoPserbrAsexérPsedoCeuqitsitatSnoisserpmoCoraF-nonnahSednoisserpmoCnamffuHednoisserpmoCxuarénéGstpecnoCeuqitsitatSnoisserpmoCIInoisserpmoCsruoC2L’arbreseconstruitenlisantlescodesdegaucheàdroiteetenformantdesnoeudsinternesjusqu’àobtenirlesfeuilles.1Lapropriétéd’arbreimpliquequ’unefeuillenepeutpasapparaîtredanslechemind’uneautrefeuille.SchemadePreuveLecodeconstruitparunarbredecodageestpréfixe.Inversemment,pourtoutcodepréfixe,ilexisteunarbredecodagelereprésentant.Théorème
sérédnoPserbrAsexérPsedoCeuqitsitatSnoisserpmoCoraF-nonnahSednoisserpmoCnamffuHednoisserpmoCxuarénéGstpecnoCeuqitsitatSnoisserpmoC1I0I0n10o0ia5s1010b2c32d1e0sW(T)=66emotcodepoids5000abc000110322110de10010rliestlalongueurduchemindelaracineàlafeuillei.pXW(T)=liwiileaf(T)mArbredecodagepondéréUnarbredecodagepondéréestunarbredecodagedontchaquefeuillepossèdeunpoids.Lepoidsdel’arbreTestdéfinipar:oArbredecodageoptimalEtantdonnéunensembleSdemotspondérés,unarbredecodageTestoptimalpourSsiW(T)estleminimumdespoidsdetouslesarbresdecodagepossiblespourS.CsruoC
euqitsitatSnoisserpmoCIInoisserpmoCsruoCsérédnoPserbrAsexérPsedoCeuqitsitatSnoisserpmoCoraF-nonnahSednoisserpmoCnamffuHednoisserpmoCxuarénéGstpecnoC100100a510102b3c2d1e0W(T)=66motcodepoids5000abc001001322110de10010liestlalongueurduchemindelaracineàlafeuillei.XW(T)=liwiileaf(T)ArbredecodagepondéréUnarbredecodagepondéréestunarbredecodagedontchaquefeuillepossèdeunpoids.Lepoidsdel’arbreTestdéfinipar:ArbredecodageoptimalEtantdonnéunensembleSdemotspondérés,unarbredecodageTestoptimalpourSsiW(T)estleminimumdespoidsdetouslesarbresdecodagepossiblespourS.