Développement de nouvelles techniques de compression de
Compression de données
4-CS-4pdf
Mémoire de master Méthode de compression de données sans
Présentation de la compression de données
Architecture et construction
NEUFERTpdf
La construction la norme et l'architecte
GUIDE ARCHITECTE
CHAPITRE 2 : LECTURE DE PLAN BATIMENT

Next PDF List

La compressionLes fichiers sont tous numériques (son, vidéo) etles volumes sont de plus en plus importants.Il faut optimiser le stockageETla transmission,donc la taille des données.Lathéorie de l"information(Shannon) permet de formaliser leproblème de la représentation de l"information.Il y a deux grandes familles d"algorithmes de compression :1Algorithmesavec perted"information.Le reconstruction des données n"est pas parfaite.

Ces méthodessont surtout utilisées pour le codage du son, d"images et de vidéos.Ils exploitent les caractéristiques de l"oeil et de l"oreille afin quel"information perdue reste imperceptible à ces sens.Exemples :les formatmp3,JPEGetMPEG.

2) Algorithmessans perted"information.Applicables à tout type de données.

Les performances sontsouvent moins bonnes que pour les méthodes avec perte, mais onest sûr de récupérer les données initiales.G.

KoepflerNumération et LogiqueCodage, numérisation et compressionL1 2014-2015 146Codage de donnéesSoientΩ ={ω1, ,ωN}des données (lettres, sons) à coder.Uncode binaire est une application CdeΩdans l"ensemble desmots binaires de longueur finie :C: Ω-→A+=?k≥1{0,1}k={0,1,00,01,10,11, ,101001, }Propriétés :1le code doit êtreuniquement décodable:?x,y?Ω :x?=y?C(x)?=C(y), càd., queCest injective;2le code doit être uncode préfixe:aucun codeC(x)n"est le préfixe d"un autre codeC(y), pour touty?=x.Ces propriétés permettent un décodage facile.G.

KoepflerNumération et LogiqueCodage, numérisation et compressionL1 2014-2015 147Codage de donnéesExemples :ΩC1C2C3C4C5ω1000000001ω210010101101ω311000110101001ω40000011110000Seuls les codesC3,C4etC5vérifient les propriétés.La suite 0000111001010001 représenteω1ω1ω4ω3ω2ω2ω1ω2dans le codeC3,ω4ω2ω1ω1ω2ω4ω1dans le codeC5.Pourω?Ω, on notelC(ω)le nombre de bits deωdans le codeC,i.e.la longueur deC(ω).Exemple : lC3(ω1) =2,lC4(ω1) =3 etlC5(ω1) =1.G.

KoepflerNumération et LogiqueCodage, numérisation et compressionL1 2014-2015 148Codage de donnéesExemple :pour coder le texteω1ω2ω1ω1le codeC3utilise 8 bits, le codeC412 bits et le codeC55 bits.Le codeC5est donc le moins coûteux pour ce texte.Pour formaliser ceci, on affecte à chaque élémentω?Ωuneprobabilitéoufréquence d"apparitionp(ω)?[0,1],on définit alors lalongueur mo yennedu code C:L(C) =?ω?Ωp(ω)lC(ω).Exemple:Pour tout quadruplet(p1,p2,p3,p4)?(R+)4, avec4?i=1pi=1,on aL(C3) =2 etL(C4) =3.Une probablité adaptée au texteω1ω2ω1ω1est(3/4,1/4,0,0),on a alorsL(C5) =34?1+14?2=1,25.G.

KoepflerNumération et LogiqueCodage, numérisation et compressionL1 2014-2015 149Codage de données1Le modèle ci-dessus suppose que les apparitions desωsontindépendantes.Mais, par exemple en français, on peut trouver la suite de lettres"texte" mais pas "eettx".Les formatsgzipetrarutilisent des méthodes combinées, plusperformantes, qui codent en partie des suites finies deΩ.

2) Le codeC4est toujours le plus coûteux, mais il permet ladétection d"erreursde transmission.En effet,C4(ω)est déduit deC3(ω)de façon à ce que la sommedes bits soit paire.Lorsque dans un code on perd un seul bit, on détecte facilementl"erreur, mais on ne peut pas la corriger.Exemple :001 est certainement pas un mot du codeC4, il y a uneerreur de transmission.

Mais 001 peut être le code deω1deω2oudeω3!Ainsi, si l"on reçoit le message 001 110, il peut être le code deω1ω4,ω2ω4ouω3ω4.G.

KoepflerNumération et LogiqueCodage, numérisation et compressionL1 2014-2015 150Codage de HuffmanD.A.

Huffman, 1925-1999, États-Unis, travaux en théorie del"information et codage.Codage découvert en 1951, lors d"un projet de fin d"études.L"idée du codage de Huffman est proche de celle utilisée dans lecode Morse : statistiques d"apparition des caractères.Inconvénients : il faut connaître les fréquences des caractères etfournir le code avec le texte.Avantages : siCest un codage de Huffman et˜Cun codagebinaire uniquement décodable, alorsL(C)≤L(˜C).Ceci se démontre sous l"hypothèse de données composées d"unesuite de caractères indépendants.Le codage de Huffman est peu utilisé tout seul.En général, on le combine avec d"autres méthodes, par exempledans.gzip,.png,.jpeg,.mp3.G.

KoepflerNumération et LogiqueCodage, numérisation et compressionL1 2014-2015 151Algorithme de HuffmanDonnées : Lettres{ω1, ,ωN}et probabilités associées{p1, ,pN}.

1) Créer une liste des lettres classée dans l"ordre des probabilitésdécroissantes.Chaque lettre est une feuille de l"arbre.

2) Tant qu"il a plus d"un élément dans la liste, répéter :2.1associer les deux noeuds de plus petite probabilité, la probabilitédu nouveau noeud est la somme des probabilités des enfants;2.2supprimer de la liste les deux noeuds réunis et les remplacer par lenouveau noeud;2.3réordonner la nouvelle liste.

3) Le dernier noeud de la liste sera la racine de l"arbre. 4) Associer le code "1" à la branche de gauche et le code "0" à labranche de droite.

5) Remonter l"arbreà par tirde la r acine,en ajoutant à chaque f oisau code un "0" ou un "1", suivant la branche suivie.En arrivant à la feuille, on a le code binaire de la lettre associée.G.

KoepflerNumération et LogiqueCodage, numérisation et compressionL1 2014-2015 152Algorithme de HuffmanL"arbre est habituellement représenté la racine en haut et lesfeuilles en bas :on lit le code en allant de la racine vers la feuille.C"est le fait d"aller de la racine vers les feuilles qui permetd"obtenir un code préfixe.L"arbre, et donc le code, que l"on obtient n"est pas unique.Pourdécoder à par tirde l"arbre ,il suffit de remonter depuis la racine jusqu"au feuilles, en suivant les branches en fonction de lasuite des "0" et "1".Exemple 1: On considère les lettresΩ ={A, B, C, D}auxquelles on associe les probabilitésp1=0,55,p2=0,25,p3=0,15 etp4=0,05.G.

KoepflerNumération et LogiqueCodage, numérisation et compressionL1 2014-2015 153Algorithme de Huffman.

Exemple 11Trier la liste. 2) Relier les noeuds deux à deux en regroupant les fréquencesd"apparition les plus faibles. Dans cet exemple, l"ordre ne change pas. 4) Coder les branches, p.ex. "1" à gauche et "0" à droite.

5) Lire lescodes , de la racine vers les feuilles :Code(A)=1, Code(B)=01, Code(C)=001 et Code(D)=000.G.

KoepflerNumération et LogiqueCodage, numérisation et compressionL1 2014-2015 154Algorithme de Huffman.

Exemple 1On a Code(A)=1, Code(B)=01, Code(C)=001 et Code(D)=000C"est un code préfixe à longueur variable, uniquement décodablepour l"ensemble de lettresΩ ={A,B,C,D}.Exemplede décodage 1011001 = 1 01 1 001ce qui est le code de ABACLa longueur moyenne du code estL(Code) =0,55?1+0,25?2+0,15?3+0,05?3=1,65Un code de longueur fixe aura une longueur moyenne de 2.D"où une compression moyenne de 17,5% .Soit le code définie parCode2(A)=00, Code2(B)=01, Code2(C)=10 et Code2(D)=11.Pour ABAC on a le codage sur 8 bits 00010010,ce qui fait une compression réelle de 12,5% .Que peut-on dire des mots AA et DC?G.

KoepflerNumération et LogiqueCodage, numérisation et compressionL1 2014-2015 155Algorithme de Huffman.

Exemple 2On considère l"ensembleΩ={ espace, A, C, D, E, R, S, T }avec les probabilitésωespaceACDERSTp(ω)0,260,060,150,040,240,080,120,051Ordonner la liste de façon décroissante :0,26(esp) 0,24(E) 0,15(C) 0,12(S) 0,08(R) 0,06(A) 0,05(T) 0,04(D)2.

1) Créer un nouveau noeud, de probabilité la somme des anciennesprobabilités :0,26(esp) 0,24(E) 0,15(C) 0,12(S) 0,08(R) 0,06(A) 0,05(T) 0,04(D)0,09 (T-D)2.2-3Supprimer les anciens noeuds et réordonner la liste :0,26(esp) 0,24(E) 0,15(C) 0,12(S) 0,09(T-D) 0,08(R) 0,06(A)G.

KoepflerNumération et LogiqueCodage, numérisation et compressionL1 2014-2015 156Algorithme de Huffman.

Exemple 22Créer le nouveau noeud, supprimer les anciens, réordonner :0,26(esp) 0,24(E) 0,15(C) 0,12(S) 0,09(T-D) 0,08(R) 0,06(A)0,14 (R-A)2Créer le nouveau noeud, supprimer les anciens, réordonner :0,26(esp) 0,24(E) 0,15(C) 0,14 (R-A) 0,12(S) 0,09(T-D)0,21 (S-(T-D))2Créer le nouveau noeud, supprimer les anciens, réordonner :0,26(esp) 0,24(E) 0,21(S-(T-D)) 0,15(C) 0,14 (R-A)0,29 (C-(R-A))G.

KoepflerNumération et LogiqueCodage, numérisation et compressionL1 2014-2015 157Algorithme de Huffman.

Exemple 22Créer le nouveau noeud, supprimer les anciens, réordonner :0,29(C-(R-A)) 0,26(esp) 0,24(E) 0,21(S-(T-D))0,45 (E-(S-(T-D)))2Créer le nouveau noeud, supprimer les anciens, réordonner :0,45 (E-(S-(T-D))) 0,29(C-(R-A)) 0,26(esp)0,55 ((C-(R-A))-esp)2Créer le nouveau noeud, supprimer les anciens, réordonner :0,55 ((C-(R-A))-esp) 0,45 (E-(S-(T-D)))1 (racine= (((C-(R-A))-esp)-(E-(S-(T-D)))) )G.

KoepflerNumération et LogiqueCodage, numérisation et compressionL1 2014-2015 158Algorithme de Huffman.

Exemple 2La racine est composée de (((C-(R-A))-esp)-(E-(S-(T-D))))On construit l"arbre binaire, à partir de la racine, en interprétant(G)-(D) comme étant un noeud ayant comme enfant gauche (G) etcomme enfant droit (D) :Une fois l"arbre binaire obtenu, on code les branches :"1" à gauche et "0" à droite.Pour obtenir les codes des éléments deΩil suffit de lire l"arbre de la racine vers les feuilles.G.

KoepflerNumération et LogiqueCodage, numérisation et compressionL1 2014-2015 159Algorithme de Huffman.

Exemple 2L"arbre binaire avec lescodes binaires et lettres/probabilités .G.

KoepflerNumération et LogiqueCodage, numérisation et compressionL1 2014-2015 160Algorithme de Huffman.

Exemple 2ωespaceACDERSTp(ω)0,260,060,150,040,240,080,120,05code10110011100000111010010001La longueur moyenne du code est 2,730=2?(0,26+0,24) +3?(0,15+0,12) +4?(0,08+0,06+0,05+0,04)En théorie de l"information, on montre que la borne inférieurethéorique de la longueur moyenne d"un code pourΩest l"entropiedeΩ, définie parH(Ω) =-?ω?Ω,p(ω)>0p(ω)log2(p(ω)).Or iciH(Ω) =2,714, l"algorithme de Huffman s"approche donctrès bien de cette valeur optimale.G.

KoepflerNumération et LogiqueCodage, numérisation et compressionL1 2014-2015 161Algorithme de Huffman.

Exemple 2Décodage facile quand l"arbre est donné : il suffit de descendre dela racine de l"arbre vers une feuille, en suivant les bits.Décodez le message suivant :00000100111111001101000101001100001110111001110110000001001100111111001101000100110On obtient : DESCARTES TRACES DES ECARTSLe décodage se fait sans ambiguïté car aucun code n"est lepréfixe d"un autre.Le décodage peut être fait au fur et à mesure, sans attendre la findu message.Si les "poids" des lettres représentent leur fréquence d"apparitiondans le texte, la construction garantit que les symboles de plusforte probabilité ont les codes les plus courts.G.

KoepflerNumération et LogiqueCodage, numérisation et compressionL1 2014-2015 162Codage de GrayFrank Gray, Etats-Unis, brevet déposé en 1951.Le code de Gray est également appelécode binaire réfléchi.C"est un codage binaire dans lequel deux valeurs successives ontdes codes qui diffèrent que d"un seul bit.décimal : 0 1 2 3 4 5 6 7binaire : 000 001 010 011 100 101 110 111code de Gray : 000 001 011 010 110 111 101 100Utilité :lorsque l"on transmet des données dont les valeurs ne varient qued"une unité, le code de Gray permet un codage très facile.En effet, on ne change qu"un bit à la fois eton peut détecter s"il y a des erreurs de transmission.G.

KoepflerNumération et LogiqueCodage, numérisation et compressionL1 2014-2015 163Codage de GrayApplications :1L"ingénieur Émile Baudot a utilisé un codage de ce type dès 1878en télégraphie.

2) F. Gray voulait coder des signaux analogiques en digital etminimiser les erreurs lors de la conversion. 3) Dans les convertisseurs analogique/digital actuels, on utilisetoujours le code de Gray.

4) On représente les états de capteurs de positions : règlesoptiques, roues codeuses, souris mécaniques.

5) Tables de Karnaugh.

6) Permet la résolution de problèmes telslesTours de HanoiouJeu du baguenaudier (anneaux chinois) G.

KoepflerNumération et LogiqueCodage, numérisation et compressionL1 2014-2015 164Codage de GrayLe code de Gray surnbits se construit à partir de l"hypercube deRndont les sommets sont les mots binaires de longueurn.Pourn=3 on a :G.

KoepflerNumération et LogiqueCodage, numérisation et compressionL1 2014-2015 165Codage de GrayPourn=4 :G.

KoepflerNumération et LogiqueCodage, numérisation et compressionL1 2014-2015 166Calculer sans retenueRappel : pour représenter un nombre en baseb, on utilisel"alphabet{0,1, ,b-1}.On faisant la somme de deux chiffres, on est en général obligéd"utiliser le principe de position pour représenter le résultat.Exemples :en baseb=10, on a 7+8=15,en baseb=2, 1+1=10.En utilisant le 0 et le principe de position, on peut noter n"importequel entier grâce aux chiffres{0,1, ,b-1}.Mais dans certaines applications, il faut tenir compte de lapériodicité de ce qui est représenté.

On compte1les heures de la journée de 1h à 24h;2les jours de la semaine de lundi (1) à dimanche (7);3les angles sont mesurés de 0◦à 360◦;4le signal d"un phare passe de façon périodique toutes lesxsec.;5une roue mécanique àmdents a fait un tour entier quand lesmdents se retrouvent dans leur position initiale; G.

KoepflerNumération et LogiqueCalcul modulaireL1 2014-2015 168Calcul modulairePour formaliser ces problèmes, on utilise lathéorie de nombres,plus précisément l"arithmétique modulaire, encore appelée lecalcul modulaire.En Europe ce sontEuclide(approx. de -325 à -265) etDiophanted"Alexandrie(approx. de 210 à 284) et en ChineSun Zi(vers 300)etQin Jiushao(approx. de 1202 à 1261), qui étudient desproblèmes de ce type.Applications aujourd"hui :Calcul de clés de contrôle, codes correcteurs, cryptographie, Définitions: soient aetbdeux entiers relatifs, on dit que1aetbsontpremiers entre eux si leur plus g randcomm undiviseur est 1.

On notepgcd(a,b) =1;2adivisebs"il existek?Ztel queb=ka. On notea|b.G.

KoepflerNumération et LogiqueCalcul modulaireL1 2014-2015 169Calcul modulaire : exempleHorloge avec une aiguille et 12 graduations de 1 à 12 :Ici 12 est identique à 0h et 24h,tandis que 18h est identifié à 6h, De façon générale, pourr? {1, ,12},r représenteles entiers de la formen=r+12koùk?Z.En remplaçant 12 par 0, donc pourr? {0,1, ,11},on peut dire querreprésente les entiersntels que le reste de ladivision euclidienne denpar 12 estr.

C"est l"ensemble{ ,r-48,r-36,r-24,r-12,r,r+12,r+24,r+36,r+48, }G.

KoepflerNumération et LogiqueCalcul modulaireL1 2014-2015 170Calcul modulaire : propriétésSoitp?N\ {0,1}, alors1aetbsontcong rusmodulo p, si et seulement sia-best un multiple dep, c"est-à-dire sip|(a-b).On notea≡bmodp.

2) On aa≡bmodpsi et seulement siaetbont le même reste dans la division euclidienne parp.Soitrce reste, alorsa=kp+rpourk?Zetr≡amodp.

3) Sia≡bmodpet sib≡cmodp, alorsa≡cmodp.

4) Sia1≡b1modpeta2≡b2modp, alorsa1+a2≡b1+b2modp,a1a2≡b1b2modp,et pour tout entiern?Z,na≡nbmodp.

5) Tout entierm?Za unreprésentantdansFp={0,1, ,p-1}.Les calculs modulopsur les entiers peuvent ainsi se ramener auxcalculs modulopdansFp.G.

KoepflerNumération et LogiqueCalcul modulaireL1 2014-2015 171Calcul modulaireExemple :calculerx≡236mod 7 ety≡2336mod 7, or236=148035889=7?21147984+1 et 2336=160005726539569!mais modulo 7 on a : 236≡26=23·23≡1·1On représente les opérations dansFpgrâce à des tableaux :Pourp=2,F2={0,1}et +0 100 111 0*0 100 010 1Pourp=3,F3={0,1,2}et +0 1 200 1 211 2 022 0 1*0 1 200 0 010 1 220 2 1Pourp=4,F4={0,1,2,3}et+0 1 2 300 1 2 311 2 3 022 3 0 133 0 1 2*0 1 2 300 0 0 010 1 2 320 2 0 230 3 2 1G.

KoepflerNumération et LogiqueCalcul modulaireL1 2014-2015 172Calcul modulaire : clé de sécuritéPour éviter de erreurs lors de la saisie d"un numéro, comme unchiffre erroné ou la permutation de chiffres, on adjoint souventuneclé de sécurité.Exemple :numéro INSEE ou "numéro de sécurité sociale»Il est composé de 13 chiffres,s=s12s11 s0,et permet de coder le sexe, l"année, le mois, le département denaissance,etc.d"un individuet d"une clé de sécuritéc(s)à deux chiffres calculé comme suitc(s) =97-(smod 97)? {1, ,97}.Le calcul modulo le nombre premier 97 permet de détecter deserreurs de saisie danss(cf.TD).D"autres exemples sont les codes barres EAN 13, le codeISBN, G.

KoepflerNumération et LogiqueCalcul modulaireL1 2014-2015 173Calcul modulaire : Algorithme RSAProposé par Rivest, Shamir et Adleman en 1977.Algorithme de cryptographie asymétrique,très utilisé dans le commerce électronique (protocole SSL).C"est un algorithme à clé publiqueCPub pour chiffrer et à clé privé