Algorithmique 2 : Compression de données

Crash Course de théorie de l’information

  • e : événement aléatoire de probabilité p

  • v(p) : valeur d’un événement de probabilité p

    • v décroît
  • Supposons qu’on a deux pièces truquées :

    • p : probabilité que la première tombe sur pile
    • p : probabilité que la seconde tombe sur pile

    ⟹ comme les événements sont indépendants,

    v(pp)=v(p)+v(p)

    On peut “vendre” l’information que les deux tombent sur pile d’un coup ou séparément, au même prix

  • v(1)=0

  • v(1/2)=1 (arbitraire)

v(x)=log2(x)

X : v.a suivant un schéma de Bernoulli B(n,p)

On l’“achète” au prix :

H(p)=plog2(p)(1p)log2(1p)
Entropie H(X) :
H(X)=xX(𝛺)pxlog(px)
Entropie conditionnelle H(YX) :
H(X)=xX(𝛺)pxH(YX=x)=xX(𝛺)pxyY(𝛺)px,y/pxlog(px,y/px)=x,ypx,ylog(px,y/px)

H(X,Y)=H(X)+H(YX)

Entropie relative

Entropie relative / Distance de Kullback-Leibler :
D(pp)=xXpxlog(px/px)=Ep(log(p(X)/p(X)))
  • ni symétrique
  • ni inégalité triangulaire

  • MAIS positive et séparée :

Avec la convexité de log

D(pp)log(px)=0

Avec égalité ssi px=px

Information mutuelle

Information mutuelle entre X et Y :
I(X;Y)=H(X)H(XY)=H(Y)H(YX)

Or :

D(pXYpXpY)=x,ypx,ylog(px,ypxpy)=x,ypx,ylog(py|xpy)=H(Y)H(Y|X)

Entropie : maximale pour la distribution uniforme

Dém : X prend n valeur différentes.

  • u : distribution uniforme

  • p : distribution quelconque

0D(pu)=H(p)+H(u)

Sur , à moyenne constante (on compare les v.a qui ont la même moyenne): la loi géométrique (de moyenne 1/p) maximise l’entropie.


Codes

  • 𝒳{xi}iI

  • 𝛴 un alphabet de codage (usuellement : 𝛴{0,1})

  • C:𝒳𝛴 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 :

ij,C(xi) n’est pas un préfixe de C(xj)

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 :
%3 Émetteur Émetteur Récepteur Récepteur Émetteur->Récepteur code
  • 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 :

  • C(x) : code de x
  • l(x)|C(x)|
  • D|𝛴|

Th (Mac-Millan) :

Si C est un code, on a l’inégalité de Kraft :

x𝒳Dl(x)1

Réciproquement :

Si {l(x)}x𝒳 vérifie cette inégalité, alors il existe un code préfixe C tel que

l(x)=|C(x)|

Preuve :

⟹ :

C : code (injectif).

lmaxmaxx𝒳l(x)

Soit k1.

(x𝒳Dl(x))k=(x1𝒳Dl(x1))(xk𝒳Dl(xk))=x1,,xk𝒳Dl(x1xk)=mklmaxamDm avec 1mklmax,am|{x1xkl(x1xk)=m}|mklmaxDmDm=klmax par injectivité du code : amDm

Donc k,

x𝒳Dl(x)(klmax)1/kx𝒳Dl(x)1

par passage à la limite pour k+

⟸ :

On numérote les xi par longueur croissante.

𝛴{0,,D1}

  • C(xi)=0l(x1)

  • On construit C(xi+1) à partir de C(xi) en ajoutant 1 au nombre en base D que représente C(xi), puis en complétant par des zéros à droite pour atteindre la bonne longueur (l(xi+1))

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 i :

i,j,u;v<u,{C(xi)[v]=C(xj)[v]C(xi)[u]<C(xj)[u]

(ce qui implique C(xi)lexC(xj))

Preuve : Si la propriété est vraie jusqu’à i : pour tout k<i, on vérifie aisément qu’elle le reste à l’étape i+1

Ex : D=2, 𝛴{0,1}

i 1 2 3
l(xi) 0 100 101
%7 0 C(x_1) 0->⋯ 100 C(x_2) 101 C(x_3) 𝜀 𝜀 𝜀->0 0 1 1 𝜀->1 1 10 10 1->10 0 11 11 1->11 1 10->100 0 10->101 1 110 110 11->110 0 111 111 11->111 1

Le sous-arbre enraciné en xi a Dlmaxl(xi) feuilles.

De plus, les feuilles issues de de xi arrivent avant les feuilles de xj si i<j et si on lit les feuilles de haut en bas (comme sur le dessin).

Par l’absurde : s’il y a un blocage, en xi avec i<n lors de l’exécution : on bloque en (D1)l(xi) ⟶ dernière feuille de l’arbre.

l(xi)=lmax

On a donc :

jiDlmaxl(xj)=DlmaxjiDl(xj)=1jnDl(xj)>1

contradiction

Complexité de l’algo : en O(n+l) avec complexité amortie ⟶ cf. l’exemple du compteur dans le cours d’algo 1.


Si 𝒳 est dénombrable :

x𝒳Dl(x)1

est toujours une condition nécessaire, en appliquant Mac-Millan aux sommes partielles.


M2 :

Par l’absurde : s’il y a un blocage, en xi avec i<n lors de l’exécution.

On prend des réels dans [0,1[ écrits en base D.

Ex :

a1anf0,a1aninaiDi

On pose :

Ii[f(C(xi)),f(C(xi))+Dl(xi)f(C(xi+1))[

Les Ij sont contigus de longueur Dk : le dernier code sur lequel on bloque est 0,(D1)(D1)+0,001=1, et la dernière borne est 1.

Donc

jiDl(xj)=1jnDl(xj)>1

contradiction


Efficacité du code

pi : probabilité d’occurrence de xi.

On veut minimiser :

iIpil(xi)=L(C)=E(l(X))

Th : C,

HD(X)L(C)

avec égalité ssi :

{iDl(xi)=1pi=Dl(xi)

Preuve :

On pose

  • lil(xi)
  • CiDl(xi)1
  • riDliC
L(C)HD(X)=ipilogD(piDli)=ipilogD(piCri)=ipilogD(piCri)=D(Pr)0 avec égalité si p=r+logD(1C)0 avec égalité si C=1

Codage de Shannon-Fano

Étant donnés les pi, comment choisir les li ?

⟶ Avec le théorème précédent :

pi=Dlili=logD(pi) HD(X)L(C)=ipilogD(pi)ipi(logD(pi)+1)=HD(X)+1

Autre codage, plus fin

L’alphabet n’est plus 𝒳 mais 𝒳k :

Blocs de k caractères :

HD(X1,,Xk)L(C)HD(X1,,Xk)+1kHD(X1)L(C)kHD(X1)+1

Donc le codage d’un caractère est compris entre HD(X) et HD(X)+1/k

Problème : taille de l’alphabet est exponentielle.

Algorithme de Huffman

Ex : 𝛴{0,1}

xi x1 x2 x3 x4 x5
pi 0,25 0,25 0,2 0,15 0,15
%27 x_2 x_2 y_2 y_2 x_2--y_2 0 y_4 y_4 y_2--y_4 0 x_3 x_3 x_3--y_2 1 x_4 x_4 y_1 y_1 x_4--y_1 0 y_3 y_3 y_1--y_3 1 x_5 x_5 x_5--y_1 1 x_1 x_1 x_1--y_3 0 y_3--y_4 1

Ex2 :

Si D=|𝛴|>2 : à chaque étape, on élimine D1 caractères

Il faut que n1mod(D1)

Complexité de l’algorithme :

On utilise un tas binaire, pour pouvoir récupérer le min en O(log(n)), et insérer un élément en O(log(n))

  • On insère les n événements xi (+D2 éventuellement auxquels on donne une proba nulle pour que n1mod(D1))
  • Puis, on en retire n1D1

⟶ au pire : 2n fois ces opérations qui coûtent logn

⟹ complexité amortie en O(nlogn)


Lemme :

  • p1pn
  • nmod(D1)=1

C préfixe optimal {li}in qui vérifie :

  • Si pi>pj alors lilj
  • “Les” (s’ils existent) D mots les plus plus longs (événements de proba les plus faibles) ont même longueur (maximale)
  • D mots associés aux probabilités les plus faibles partagent le même père

Preuve :

  • on vérifie aisément que tout C optimal vérifie la première condition par contraposée.

  • k<D mots les plus longs :

    Peut-on avoir k=1 ? 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 1<k<D

Scolie : Un arbre dont tous les sommets internes ont D fils a un nombre de feuille congru à 1mod(D1)

Preuve : Par récurrence sur la taille de l’arbre.

⟶ on peut se ramener au fait que les D mots les plus longs ont même longueur, quitte à rajouter des fils (feuilles) aux noeuds internes qui n’ont pas D fils.


Algorithme de Huffmann :

  1. Insertion dans tas min des événements (poids = proba)

  2. On rajoute des événements fictifs de proba nulle jusqu’à ce que n1(D1)

  3. Extraire D événements y1,,yD du tas min de probas Py1,,PyD

  4. Créer un événement z de proba iPyi

  5. Insérer z dans le tas

  6. z est père des yDi

Complexité : en 𝛳(nlogn)

Correction : C optimal

Shannon - Fano - Elias

  • 𝒳={1,,n}
  • p1,,pn>0
  • 𝛴={0,1}
FX(x)yxPyFX(x)y<xPy=FX(x1)FX(x)FX(x)+Px/2]0,1[
  41 2 3 4 53
Px 0,25 0,25 0,2 0,15 0,15
F(x) 0,25 0,5 0,7 0,85 1
F(x) 0,125 0,375 0,6 0,775 0,925

Idée : “F(x)” servira de codage

xl troncature aux l premiers bits après la virgule

En base 2 :

1/3=0,01010101x4=0,0101 C(x)=F(x)logp(x)+1l(C)H(X)+2

Le tableau devient :

  41 2 3 4 53
Px 0,25 0,25 0,2 0,15 0,15
F(x) 0,25 0,5 0,7 0,85 1
F(x) 0,125 0,375 0,6 0,775 0,925
l(x) 3 3 4 4 4
F(x) en base 2 0,001 0,011 0,1001 0,1100011 0,1110110
C(x) en base 2 001 011 1001 1100 1110
0F(x)F(x)l(x)<2l(x)2log(p(x))1=p(x)/2 F(x)l(x)]F(x1),F(x)]F(x+1)l(x)]F(x),F(x+1)]

⟶ 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 b caractères x1,,xi,,xb

  • F(x1xi+1)=F(x1xi+1)+p(x1xn)F(xi+1)
  • p(x1xi+1)=p(x1xi)p(xi+1)
  • On a les tables statiques de F et p, et on calcule dynamiquement F(x1xi+1) et p(x1xi+1)

Décodeur

  • Décodeur : reçoit F(x1xb)l(x1xb)

  • F(x1)<<F(x1xb)<F(x1xb)l(x1xb)<F(x1(xb+1))<F(x1(xb1+1))<<F(x1+1)
  • Le décodeur a la table des 0=F(1),,F(n+1)=1 ⟶ avec l’encadrement précédent, il détermine x1 en O(n)

  • Avec F(x1x2)=F(x1)+p(x1)F(x2), le décodeur détermine x2 en O(n)

Codage statique VS Codage adaptatif

Codage statique

La codeur connaît p1,,pn

  • 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.

X(x1,,xn)

La distribution p1,,pn existe, mais le codeur ne la connaît pas.

Kolmogorov : loi forte des grands nombres.

Pour un mot

x𝛼(1)x𝛼(n)

on pose

p(n)(x)= nombre d’occurrences de xn

Avec proba 1 :

p(n)(x)np(x)

Huffmann adaptatif :

Codage Cn obtenu obtenu à partir des occurrences des n premières lettres pour encoder x𝛼(n+1)

Mais ça coûte O(nlogn) à chaque lettre ⟶ trop coûteux :

Solutions :

  1. Première idée : utiliser un codage de Huffmann associé au nombre d’occurrences

  2. Deuxième idée : Cn+1 à partir de Cn

Cn1(xn) :

code de Huffmann obtenu à partir des fréquences d’événements x1,,xn1.

Prop : x1,,xn, p1,,pn, de poids (compte d’occurrences) w1,,wn

Arbre associé à un code préfixe a 2n1 sommets :

CNS : une numérotation u1,,u2n1 tq

  • i<j,w(ui)w(uj)

  • 1in, u2i1 et u2i 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.

xn apparaît :

  • on incrémente la feuille associée à xn soeur vj+1 telle que vj+1>vn, et on intervertit xj et xn
  • 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é : n), alors que pour les père : hauteur de l’arbre (logarithmique dans le cas équidistribué).

l(Cn)p.sl(C)

C est le code de Huffmann.

Ex :

X{a,b,c,d,e,f}

%45 32 11 11 11 | f, 9 32--11 21 21, 10 32--21 53 5 | d, 4 11--53 6 5 | e, 6 11--6 10 10, 7 21--10 112 11, 8 21--112 51 5 | c, 3 10--51 52 5 10--52 2 2    | a, 1 52--2 3 3    | b, 2 52--3

Code arbitraire : sur x1,,xn, c1,,cn

  • Codeur x3c3 Décodeur
%67 12 1 | x_3 0 0 | ? 1 1 1->12 1->0
  • Codeur x10c1 Décodeur
%73 12 1 | x_3 22 2 | x_1 0 0 | ? 1 1 1->12 2 2 1->2 2->22 2->0

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 0
2 01
3 010

Ex :

0/1/00/01/10/11

numéro de l’entrée mot
0 𝜀
1 0
2 1
3 00
4 01
5 10
6 11

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 : 2logn=O(logn))

Flux : préfixe de longueur n

wnu1un
ci(n) :

nombre d’occurrences de xi dans wn

Xi :

v.a du tirage de la lettre i

Sn1ninlog(p(Xi))

Par la loi forte des grands nombres :

Snp.sHX

Soit

mu1un m=y1y2yc(n)

où les yi sont les mots produits par Ziv-Lempel.

|c(n)|(logc(n)+1)c(n)
c(l) :

nombre de mots de longueur l

LEMME :

lcllog(cl)inlog(p(ui))1n1lc(n)cllog(cl)1ninlog(p(ui))p.sH(X)

Preuve : p(u1uk)=1ikp(ui)

inlogp(ui)=1jc(n)log(p(yj))=lcl|yj|=l1cllog(p(yj))lcllog(1cl)|yj|=lp(yj)lcllog(cl)

Liv-Zempel est très fort : il atteint l’entropie sans même la connaître !

Leave a comment