Compression Statistique

pages

Français

Documents

Écrit par
Frederic Koriche

Publié par
Shuwyur

Lire

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

pages

Français

Documents

Lire

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

Publié par

Shuwyur

Nombre de lectures

100

Langue

Français

Compression Statistique
Frederic Koriche
Cours Théorie de l’Information
Compression: partie II
Université Montpellier II, France
Frederic.Koriche@lirmm.frConcepts Généraux Compression Statistique
Compression de Huffman Codes Préﬁxes de Shannon Faro Arbres Pondérés
Outline
1 Concepts Généraux
Compression Statistique
Codes Préﬁxes
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 StatistiqueConcepts Généraux Compression Statistique
Compression de Huffman Codes Préﬁxes 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éﬁxe de la source qui
tienne compte de la probabilité
d’occurrence de chaque mot.
Cours Compression II Compression StatistiqueConcepts Généraux Compression Statistique
Compression de Huffman Codes Préﬁxes 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 ...

Voir

Publié par

Shuwyur

Nombre de lectures

100

Langue

Français

CompressionStatistiqueFredericKoricheCoursThéoriedel’InformationCompression:partieIIUniversitéMontpellierII,FranceFrederic.Koriche@lirmm.fr

3CompressiondeShannon-FaroL’algorithmePropriétés2CompressiondeHuffmanL’algorithmePropriétésConceptsGénérauxCompressionStatistiqueCodesPréﬁxesArbresPondé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éﬁxedelasourcequitiennecomptedelaprobabilité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éﬁxedelasourcequitiennecomptedelaprobabilité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éﬁxedelasourcequitiennecomptedelaprobabilitéd’occurrencedechaquemot.amffuHednoisserpmoCxuarénéGstpecnoCeuqitsitatSnoisserpmoCIInoisserpmoCsruoCsérédnoPserbrAsexﬁérPsedoCeuqitsitatSnoisserpmoCoraF-nonnahSednoisserpabracadabraSourcemmotpoidscode05a012bdc111100101112rCodagepréﬁxeo

sérédnoPserbrAsexﬁérPsedoCeuqitsitatSnoisserpmoCoraF-nonnahSednoisserpmoCnamffuHednoisserpmoCxuarénéGstpecnoCeuqitsitatSnoisserpmoCIInoisserpmoCsruoCtomabcdeedoc000100010110001100100a01cb01edCodePréﬁxeLecodaged’unensembledemotsSestappelécodepréﬁxesiaucuncoded’unmotdeSn’estlepréﬁxeducoded’unautremotdeS.ArbredecodageUnarbredecodagepourunensembledemotsSestunarbrebinairevériﬁantlespropriétéssuivantes:chaquebrancheestétiquetéepar0oupar1,chaquefeuilleestétiquetéeparunmotdeS,lecodecorrespondantàunefeuilledeSestlecheminparcourudepuislaracinejusqu’àlafeuille.

sérédnoPserbrAsexﬁérPsedoCeuqitsitatSnoisserpmoCoraF-nonnahSednoisserpmoCnamffuHednoisserpmoCxuarénéGstpecnoCeuqitsitatSnoisserpmoCIInoisserpmoCsruoCtomabcdeedoc000100010110001100100a01cb10edCodePréﬁxeLecodaged’unensembledemotsSestappelécodepréﬁxesiaucuncoded’unmotdeSn’estlepréﬁxeducoded’unautremotdeS.ArbredecodageUnarbredecodagepourunensembledemotsSestunarbrebinairevériﬁantlesproprié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éﬁxe.Inversemment,pourtoutcodepréﬁxe,ilexisteunarbredecodagelereprésentant.Théorème

sérédnoPserbrAsexﬁérPsedoCeuqitsitatSnoisserpmoCoraF-nonnahSednoisserpmoCnamffuHednoisserpmoCxuarénéGstpecnoCeuqitsitatSnoisserpmoCIInoisserpmoCsruoC2L’arbreseconstruitenlisantlescodesdegaucheàdroiteetenformantdesnoeudsinternesjusqu’àobtenirlesfeuilles.1Lapropriétéd’arbreimpliquequ’unefeuillenepeutpasapparaîtredanslechemind’uneautrefeuille.SchemadePreuveLecodeconstruitparunarbredecodageestpréﬁxe.Inversemment,pourtoutcodepréﬁxe,ilexisteunarbredecodagelereprésentant.Théorème

sérédnoPserbrAsexﬁérPsedoCeuqitsitatSnoisserpmoCoraF-nonnahSednoisserpmoCnamffuHednoisserpmoCxuarénéGstpecnoCeuqitsitatSnoisserpmoC1I0I0n10o0ia5s1010b2c32d1e0sW(T)=66emotcodepoids5000abc000110322110de10010roùliestlalongueurduchemindelaracineàlafeuillei.pXW(T)=liwii∈leaf(T)mArbredecodagepondéréUnarbredecodagepondéréestunarbredecodagedontchaquefeuillepossèdeunpoids.Lepoidsdel’arbreTestdéﬁnipar:oArbredecodageoptimalEtantdonnéunensembleSdemotspondérés,unarbredecodageTestoptimalpourSsiW(T)estleminimumdespoidsdetouslesarbresdecodagepossiblespourS.CsruoC

euqitsitatSnoisserpmoCIInoisserpmoCsruoCsérédnoPserbrAsexﬁérPsedoCeuqitsitatSnoisserpmoCoraF-nonnahSednoisserpmoCnamffuHednoisserpmoCxuarénéGstpecnoC100100a510102b3c2d1e0W(T)=66motcodepoids5000abc001001322110de10010oùliestlalongueurduchemindelaracineàlafeuillei.XW(T)=liwii∈leaf(T)ArbredecodagepondéréUnarbredecodagepondéréestunarbredecodagedontchaquefeuillepossèdeunpoids.Lepoidsdel’arbreTestdéﬁnipar:ArbredecodageoptimalEtantdonnéunensembleSdemotspondérés,unarbredecodageTestoptimalpourSsiW(T)estleminimumdespoidsdetouslesarbresdecodagepossiblespourS.

Voir