Codage et compression de données
Emmanuel SARI - LSI3
11/11/2008 Emmanuel SARI – LSI3 2
Codage et compression de données
Introduction
I. Méthodes statistiques Shannon-Fano Huffman
II. Méthodes dictionnaires LZ77 LZ78 LZW
III.Utilisations
IV.Autre : méthode anti-dictionnaire
11/11/2008 Emmanuel SARI – LSI3 3
Introduction
Besoin : réduire le volume des données Gain en stockage Gain en temps de transmission
Solution : Utiliser les capacités des processeurs plutôt qu’augmenter les
espaces de stockage et bandes passantes Pouvoir compresser et décompresser les données
11/11/2008 Emmanuel SARI – LSI3 4
Introduction
Deux approches : Compression sans perte
• Texte• Programmes
Compression avec perte• Images• Son• Vidéo
11/11/2008 Emmanuel SARI – LSI3 5
I. Méthodes statistiques
Principe Basé sur la fréquence d’apparition d’un symbole On attribue un code plus court à un symbole plus fréquent Exemple : le code Morse
11/11/2008 Emmanuel SARI – LSI3 6
I. Méthodes statistiques
Codages de différentes tailles
Exemple :Alphabet = {A, B, C, D}Fréquence d’apparition : A=60%, B=30%, C=5% et D=5%Codage potentiel : A 0, B 00, C 01, D 10⇒ ⇒ ⇒ ⇒Message : ‘000010’.Interprétation : AAACA ? ABCA ? BACA ? AAAAD ? BBD ?
Risque d’ambiguïté
11/11/2008 Emmanuel SARI – LSI3 7
I. Méthodes statistiques
Solution : utilisation de codages préfixes Aucun code n’est préfixe d’un autre. Pas d’ambiguïté possible
Code préfixe sur l’exemple précédent : A 0, B 10, C 110, D 111.⇒ ⇒ ⇒ ⇒
11/11/2008 Emmanuel SARI – LSI3 8
I. Méthodes statistiques
Compression de Shannon-Fano :1. Classer les symboles par ordre croissant sur les fréquences.2. Partitionner la table en deux sous-tables de fréquences
proches. Recommencer jusqu’à ce que toute fréquence soit isolée.
3. À chaque niveau de subdivision, attribuer la valeur 0 à la première sous-table, 1 à la seconde.
4. Associer à chaque symbole le code correspondant aux bits de description de l’arborescence.
Décodage en parcourant l’arbre de codage avec les bits du message
11/11/2008 Emmanuel SARI – LSI3 9
I. Méthodes statistiques
Exemple :Alphabet = {A,B,C,D,E}.Fréquences : A=15, B=7, C=6, D=6, E=5
Résultat :A 00, B 01, C 10, D 110, E 111.⇒ ⇒ ⇒ ⇒ ⇒
11/11/2008 Emmanuel SARI – LSI3 10
I. Méthodes statistiques
Compression de Huffman Principe similaire à Shannon-Fano Construction depuis les feuilles vers la racine cette fois-ci
11/11/2008 Emmanuel SARI – LSI3 11
I. Méthodes statistiques
Reprise de l’exemple précédent :Alphabet = {A,B,C,D,E}.Fréquence : A=15, B=7, C=6, D=6, E=5
Résultat :A 0, B 100, C 101, D 110, E 111.⇒ ⇒ ⇒ ⇒ ⇒
11/11/2008 Emmanuel SARI – LSI3 12
I. Méthodes statistiques
Avantages : Arbre de codage toujours oprimal Meilleur que Shannon-Fano
Inconvénients : Transmission de l’arbre Codage bit à bit
11/11/2008 Emmanuel SARI – LSI3 13
II. Méthodes dictionnaires
Principe : Ne plus faire du codage bit à bit Profiter du fait que certains motifs sont récurrents
• Les indexer• Coder uniquement leur position
Compression de Lempel-Ziv
11/11/2008 Emmanuel SARI – LSI3 14
II. Méthodes dictionnaires
LZ77 Parcours avec une fenêtre de codage Codage sous forme de triplets : (Distance, Longueur, Car) « Fausse méthode dictionnaire »
11/11/2008 Emmanuel SARI – LSI3 15
II. Méthodes dictionnaires
Exemple :Codage de la chaîne : abcdefgcdefgcdabcdgcgcgcTaille de la fenêtre : 24 caractères
abcdefg(5,7)(14,4)gc(2,4)
Résultat :(0,0,a)(0,0,b)(0,0,c)(0,0,d)(0,0,e)(0,0,f)(0,0,g)(5,7,a)(14,4,g)(0,0,c)(0,0,g)(2,4)
11/11/2008 Emmanuel SARI – LSI3 16
II. Méthodes dictionnaires
Peu efficace sur cet exemple car texte trop court
Avantages : Plus efficace que les méthodes statistiques Codage/décodage symétriques
Inconvénients : Coût en temps de calcul Gestion délicate de la fenêtre de codage
• Fenêtre trop petite compression moins bonne⇒• Fenêtre trop grande temps de calcul rallongé⇒
11/11/2008 Emmanuel SARI – LSI3 17
II. Méthodes dictionnaires
LZ78 Palie au défaut du fenêtrage Utilisation d’un véritable dictionnaire Plus efficace que LZ77
Dictionnaire réduit : Plus de champ ‘Longueur’ Remplacement de ‘Distance’ par l’index
• 0 si nouvelle entrée• Index ordonné de 1 à 255 sinon
11/11/2008 Emmanuel SARI – LSI3 18
II. Méthodes dictionnaires
Exemple :Codage de la chaîne : abcdefgcdefgcdabcdgcgcgcTaille de la fenêtre : 24 caractères.
11/11/2008 Emmanuel SARI – LSI3 19
II. Méthodes dictionnaires
LZW : Lempel-Ziv-Welch Codage sur 12 bits uniquement par des index
• De 1 à 255 : ASCII• Après 256 : motifs rencontrés
Plus efficace que LZ78
11/11/2008 Emmanuel SARI – LSI3 20
II. Méthodes dictionnaires
Exemple :Codage de la chaîne : abcdefgcdefgcdabcdgcgcgcTaille de la fenêtre : 24 caractères.
Résultat :abcdefg[258][260][262]d[256][258][262][269]c
11/11/2008 Emmanuel SARI – LSI3 21
III. Utilisations
LZ78 et LZW anciennement brevetés Gif Tiff(optionnel)
LZ77 + Huffman DEFLATE⇒ Zip Gzip Png HTTP SSH
11/11/2008 Emmanuel SARI – LSI3 22
III. Utilisations
Nombreuses variantes : LZSS, LZWL, LZO, LZMA, LZX, LZJB, LZT…
Nombreux formats : Bzip2, 7z, Rzip, Lzop…
11/11/2008 Emmanuel SARI – LSI3 23
IV. Autre : méthode anti-dictionnaire
Idée : Si on sait que le facteur 1011 n’apparaît pas dans le texte, cela
veut dire qu’à chaque fois que le facteur 101 est présent, il sera suivi par 0
Définition : On se place dans un alphabet binaire. ω : un mot fini. F(ω) : l’ensemble des facteurs de ω. Anti-dictionnaire de ω :
AD(ω)= ensemble de facteurs n’appartenant pas à ω
Exemple : ω = 1010.AD(ω) = {00,11}
11/11/2008 Emmanuel SARI – LSI3 24
IV. Autre : méthode anti-dictionnaire
Exemple (compression) : ω = 01101010 AD(ω) = {00, 111, 1011}
11/11/2008 Emmanuel SARI – LSI3 25
IV. Autre : méthode anti-dictionnaire
Exemple (décompression) : γ(ω) = 01101010 AD(ω) = {00, 111, 1011}
11/11/2008 Emmanuel SARI – LSI3 26
IV. Autre : méthode anti-dictionnaire
Construction de l’anti-dictionnaire : Recherche des facteurs de la phrase de longueur donné k. Recherche des facteurs interdits minimaux de taille ≤ k.
Exemple: ω = 01101010 K = 5
11/11/2008 Emmanuel SARI – LSI3 27
Codage et compression de données
Des questions ?
Sources : Codage et compression de données - Erwan le Scanff Codage et compression de données - Jérôme Dumas, Fabien Harrang Wikipedia.org Compression de données utilisant les anti-dictionnaires - Sarah Maarek