Algorithmique 2 : Compression de données
Crash Course de théorie de l’information
-
: événement aléatoire de probabilité -
: valeur d’un événement de probabilité décroît
-
Supposons qu’on a deux pièces truquées :
: probabilité que la première tombe sur pile : probabilité que la seconde tombe sur pile
⟹ comme les événements sont indépendants,
On peut “vendre” l’information que les deux tombent sur pile d’un coup ou séparément, au même prix
-
-
(arbitraire)
On l’“achète” au prix :
- Entropie
: -
- Entropie conditionnelle
: -
Entropie relative
- Entropie relative / Distance de Kullback-Leibler :
-
- ni symétrique
-
ni inégalité triangulaire
- MAIS positive et séparée :
Avec la convexité de
Avec égalité ssi
Information mutuelle
- Information mutuelle entre
et : -
Or :
Entropie : maximale pour la distribution uniforme
Dém :
X prend
-
: distribution uniforme -
: distribution quelconque
Sur
Codes
-
-
un alphabet de codage (usuellement : ) -
fonction de codage, qui peut être étendue à par concaténation.
/!\ : Il nous faut assurer l’injectivité de la fonction étendue, pour pouvoir décoder.
- Code préfixe :
-
NB :
- un code préfixe est évidemment injectif.
- les codes préfixes sont décodables en temps réel, alors que codes injectifs seulement ⟶ il faut attendre la fin du texte pour décoder.
- Différents types de transmission :
-
- transmission d’informations :
- fichier ⟶ avantage par rapport au précédent, entre autres : on connaît la fréquence d’apparition des lettres
Théorème de Mac-Millan
Nous donne une condition nécessaire et suffisante pour fabriquer un code.
Notations :
: code de
Th (Mac-Millan) :
Si
est un code, on a l’inégalité de Kraft : Réciproquement :
Si
vérifie cette inégalité, alors il existe un code préfixe tel que
Preuve :
⟹ :
Soit
Donc
par passage à la limite pour
⟸ :
On numérote les
-
-
On construit
à partir de en ajoutant au nombre en base que représente , puis en complétant par des zéros à droite pour atteindre la bonne longueur ( )
Attention : cet algorithme peut s’interrompre en cours d’exécution (si on ne peut plus incrémenter par exemple sans changer le nombre de chiffres).
Supposons que l’algo termine, et qu’ont ait la propriété suivante à l’étape
(ce qui implique
Preuve : Si la propriété est vraie jusqu’à
Ex :
1 | 2 | 3 | |
---|---|---|---|
0 | 100 | 101 |
Le sous-arbre enraciné en
De plus, les feuilles issues de de
Par l’absurde : s’il y a un blocage, en
On a donc :
contradiction
Complexité de l’algo : en
avec complexité amortie ⟶ cf. l’exemple du compteur dans le cours d’algo 1.
Si
est toujours une condition nécessaire, en appliquant Mac-Millan aux sommes partielles.
M2 :
Par l’absurde : s’il y a un blocage, en
On prend des réels dans
Ex :
On pose :
Les
Donc
contradiction
Efficacité du code
On veut minimiser :
Th :
, avec égalité ssi :
Preuve :
On pose
Codage de Shannon-Fano
Étant donnés les
⟶ Avec le théorème précédent :
Autre codage, plus fin
L’alphabet n’est plus
Blocs de
Donc le codage d’un caractère est compris entre
⟶ Problème : taille de l’alphabet est exponentielle.
Algorithme de Huffman
Ex :
0,25 | 0,25 | 0,2 | 0,15 | 0,15 |
Ex2 :
Si
Il faut que
Complexité de l’algorithme :
On utilise un tas binaire, pour pouvoir récupérer le min en
- On insère les
événements ( éventuellement auxquels on donne une proba nulle pour que ) - Puis, on en retire
⟶ au pire :
⟹ complexité amortie en
Lemme :
préfixe optimal qui vérifie :
- Si
alors - “Les” (s’ils existent)
mots les plus plus longs (événements de proba les plus faibles) ont même longueur (maximale) mots associés aux probabilités les plus faibles partagent le même père
Preuve :
-
on vérifie aisément que tout
optimal vérifie la première condition par contraposée. -
mots les plus longs :Peut-on avoir
? Non, car on aurait un fils tout seul, et on améliore le code en prenant le codage de son père.Donc on peut supposer
Scolie : Un arbre dont tous les sommets internes ont
fils a un nombre de feuille congru à
Preuve : Par récurrence sur la taille de l’arbre.
⟶ on peut se ramener au fait que les
Algorithme de Huffmann :
-
Insertion dans tas min des événements (poids = proba)
-
On rajoute des événements fictifs de proba nulle jusqu’à ce que
-
Extraire
événements du tas min de probas -
Créer un événement
de proba -
Insérer
dans le tas -
est père des
Complexité : en
Correction :
Shannon - Fano - Elias
41 | 2 | 3 | 4 | 53 | |
---|---|---|---|---|---|
0,25 | 0,25 | 0,2 | 0,15 | 0,15 | |
0,25 | 0,5 | 0,7 | 0,85 | 1 | |
0,125 | 0,375 | 0,6 | 0,775 | 0,925 |
Idée : “
En base 2 :
Le tableau devient :
41 | 2 | 3 | 4 | 53 | |
---|---|---|---|---|---|
0,25 | 0,25 | 0,2 | 0,15 | 0,15 | |
0,25 | 0,5 | 0,7 | 0,85 | 1 | |
0,125 | 0,375 | 0,6 | 0,775 | 0,925 | |
3 | 3 | 4 | 4 | 4 | |
0,001 | 0,011 | ||||
001 | 011 | 1001 | 1100 | 1110 |
⟶ intervalles disjoints ⟹ code préfixe
Code arithmétique = Shannon-Fano-Elias par bloc.
Comment éviter des stocker la table des blocs ?
Codeur
-
Codeur : voit un bloc de
caractères -
-
- On a les tables statiques de
et , et on calcule dynamiquement et
Décodeur
-
Décodeur : reçoit
-
-
Le décodeur a la table des
⟶ avec l’encadrement précédent, il détermine en - Avec
, le décodeur détermine en
Codage statique VS Codage adaptatif
Codage statique
La codeur connaît
- adapté aux fréquences de lettres dans un fichier
- pas adapté pour les streams ⟶ on ne connaît pas la proba d’occurrence
Codage adaptatif
On utilisera un alphabet de codage binaire.
La distribution
Kolmogorov : loi forte des grands nombres.
Pour un mot
on pose
Avec proba 1 :
Huffmann adaptatif :
Codage
Mais ça coûte
Solutions :
-
Première idée : utiliser un codage de Huffmann associé au nombre d’occurrences
-
Deuxième idée :
à partir de
:-
code de Huffmann obtenu à partir des fréquences d’événements
.
Prop :
, , de poids (compte d’occurrences) Arbre associé à un code préfixe a
sommets : CNS :
une numérotation tq
, et ont le même père
Observation 1 : L’algo de Huffmann produit une telle numérotation.
Observation 2 : L’algo de Huffmann peut construire cet arbre en suivant la numérotation.
- on incrémente la feuille associée à
soeur telle que , et on intervertit et - on incrémente le père et on itère
NB : opération coûteuse : en gras, car on doit parcourir tous les frères (dans le cas équidistribué :
où
Ex :
Code arbitraire : sur
- Codeur
Décodeur
- Codeur
Décodeur
Lempel-Ziv
numéro de l’entrée | mot |
---|---|
0 |
On veut coder 001010
-
Premier caractère : 0
- on passe 0, 0 (index d plus grand préfixe qu’on a déjà dans notre tableau, nouveau caractère)
- on actualise la table en ajoutant le mot précédemment codé (préfixe connu + nouveau caractère)
numéro de l’entrée | mot |
---|---|
0 | |
1 | |
2 | |
3 |
Ex :
0/1/00/01/10/11
numéro de l’entrée | mot |
---|---|
0 | |
1 | |
2 | |
3 | |
4 | |
5 | |
6 |
Codes envoyés:
- 0, 0
- 0, 1
- 1, 0
- 1, 1
- 2, 0
- 2, 1
On ajoute l’information de la longueur du flux
NB :
- si on veut encoder/faire passer 1101 en binaire ⟶ on fait passer 111110110 (longueur :
)
Flux : préfixe de longueur
:-
nombre d’occurrences de
dans :-
v.a du tirage de la lettre
Par la loi forte des grands nombres :
Soit
où les
:-
nombre de mots de longueur
LEMME :
Preuve :
Liv-Zempel est très fort : il atteint l’entropie sans même la connaître !
Leave a comment