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) = - log_2(x)\]

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

On l’“achète” au prix :

\[H(p) = -p \log_2(p) - (1-p) \log_2 (1-p)\]
Entropie $H(X)$ :
\[H(X) = - \sum\limits_{ x∈X(𝛺) } p_x \log (p_x)\]
Entropie conditionnelle $H(Y \mid X)$ :
\[H(X) = \sum\limits_{ x∈X(𝛺) } p_x H(Y \mid X=x) = - \sum\limits_{ x∈X(𝛺) } p_x \sum\limits_{ y∈Y(𝛺) } p_{x,y}/p_x \log (p_{x,y}/p_x) \\ = - \sum\limits_{ x,y } p_{x,y} \log (p_{x,y}/p_x)\]
\[H(X, Y) = H(X) + H(Y \mid X)\]

Entropie relative

Entropie relative / Distance de Kullback-Leibler :
\[D(p \Vert p') = - \sum\limits_{ x∈X } p_x \log(p'_x/p_{x}) = E_p(\log (p(X)/p'(X)))\]
  • ni symétrique

  • ni inégalité triangulaire

  • MAIS positive et séparée :

Avec la convexité de $-\log$

\[D(p \Vert p') ≥ - \log( \sum p'_x ) = 0\]

Avec égalité ssi $p’_x = p_x$

Information mutuelle

Information mutuelle entre $X$ et $Y$ :
\[I(X; Y) = H(X) - H(X \mid Y) = H(Y) - H(Y \mid X)\]

Or :

\[D(p_{XY} \Vert p_X p_Y) = \sum\limits_{ x, y } p_{x,y} \log(\frac{p_{x,y}}{p_x p_y}) \\ = \sum\limits_{ x, y } p_{x,y} \log(\frac{p_{y \vert x}}{p_y}) \\ = H(Y) - H(Y \vert X)\]

Entropie : maximale pour la distribution uniforme

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

  • $u$ : distribution uniforme

  • $p$ : distribution quelconque

\[0 ≤ D(p \Vert u) = - 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

  • $𝒳 ≝ \lbrace x_i \rbrace_{i∈I}$

  • $𝛴$ un alphabet de codage (usuellement : $𝛴 ≝ \lbrace 0, 1 \rbrace$)

  • $C : 𝒳 ⟶ 𝛴^\ast$ fonction de codage, qui peut être étendue à $𝒳^\ast$ par concaténation.

/!\ : Il nous faut assurer l’injectivité de la fonction étendue, pour pouvoir décoder.

Code préfixe :

$∀i≠j, C(x_i) \text{ n’est pas un préfixe de } C(x_j)$

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 :
  digraph {
    rankdir=LR;
    Émetteur -> Récepteur[label="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) ≝ \vert C(x) \vert$
  • $D ≝ \vert 𝛴 \vert$

Th (Mac-Millan) :

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

\[\sum\limits_{ x∈𝒳 } D^{-l(x)} ≤ 1\]

Réciproquement :

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

\[l(x) = \vert C(x) \vert\]

Preuve :

⟹ :

$C$ : code (injectif).

\[l_{max} ≝ \max_{x∈𝒳} l(x)\]

Soit $k≥1$.

\[\begin{align*} \left( \sum\limits_{ x∈𝒳 } D^{-l(x)} \right)^k & = \left( \sum\limits_{ x_1∈𝒳 } D^{-l(x_1)} \right) ⋯ \left( \sum\limits_{ x_k∈𝒳 } D^{-l(x_k)} \right) \\ & = \sum\limits_{ x_1, ⋯, x_k ∈𝒳 } D^{-l(x_1 ⋯ x_k)} \\ &= \sum\limits_{ m ≤ k l_{max} } a_m D^{-m} &&\text{ avec } ∀ 1≤m≤k \cdot l_{max}, a_m ≝ \vert \lbrace x_1 ⋯ x_k \mid l(x_1 ⋯ x_k) = m \rbrace \vert \\ & ≤ \sum\limits_{ m ≤ k l_{max} } D^m D^{-m} = k l_{max} &&\text{ par injectivité du code : } a_m ≤ D^m \end{align*}\]

Donc $∀k$,

\[\sum\limits_{ x∈𝒳 } D^{-l(x)} ≤ (k l_{max})^{1/k} \\ ⟹ \sum\limits_{ x∈𝒳 } D^{-l(x)} ≤ 1\]

par passage à la limite pour $k⟶+∞$

⟸ :

On numérote les $x_i$ par longueur croissante.

$𝛴 ≝ \lbrace 0, ⋯, D-1 \rbrace$

  • $C(x_i) = 0^{l(x_1)}$

  • On construit $C(x_{i+1})$ à partir de $C(x_i)$ en ajoutant $1$ au nombre en base $D$ que représente $C(x_i)$, puis en complétant par des zéros à droite pour atteindre la bonne longueur ($l(x_{i+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, \begin{cases} C(x_i)[v] = C(x_j)[v] \\ C(x_i)[u] < C(x_j)[u] \end{cases}\]

(ce qui implique $C(x_i) ≤_{lex} C(x_j)$)

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$, $𝛴≝ \lbrace 0,1 \rbrace$

$i$ 1 2 3
$l(x_i)$ 0 100 101 
  digraph {
    rankdir=LR;
    0[label="C(x_1)"];
    100[label="C(x_2)"];
    101[label="C(x_3)"];
    𝜀 -> 0[label="0"];
    𝜀 -> 1[label="1"];
    1 -> 10[label="0"];
    1 -> 11[label="1"];
    10 -> 100[label="0"];
    10 -> 101[label="1"];
    11 -> 110[label="0"];
    11 -> 111[label="1"];
    0 -> ⋯;
  }

Le sous-arbre enraciné en $x_i$ a $D^{l_{max}-l(x_i)}$ feuilles.

De plus, les feuilles issues de de $x_i$ arrivent avant les feuilles de $x_j$ 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 $x_i$ avec $i<n$ lors de l’exécution : on bloque en $(D-1)^{l(x_i)}$ ⟶ dernière feuille de l’arbre.

$l(x_i) = l_{max}$

On a donc :

\[\sum\limits_{ j ≤ i } D^{l_{max}-l(x_j)} = D^{l_{max}} \\ \sum\limits_{ j ≤ i } D^{-l(x_j)} = 1 \\ ⟹ \sum\limits_{ j ≤ n} D^{-l(x_j)} > 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 :

\[\sum\limits_{ x∈𝒳 } D^{-l(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 $x_i$ avec $i<n$ lors de l’exécution.

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

Ex :

\[a_1 ⋯ a_n \mapsto^f 0, a_1 ⋯ a_n ≝ \sum\limits_{ i≤n } a_i D^{-i}\]

On pose :

\[I_i ≝ \left[f(C(x_i)), \underbrace{f(C(x_i)) + D^{-l(x_i)}}_{≝ f(C(x_{i+1}))} \right[\]

Les $I_j$ sont contigus de longueur $D^{-k}$ : le dernier code sur lequel on bloque est $0, (D-1) ⋯ (D-1)$ ⟶ $+0, 0⋯01 = 1$, et la dernière borne est $1$.

Donc

\[\sum\limits_{ j ≤ i } D^{-l(x_j)} = 1 \\ ⟹ \sum\limits_{ j ≤ n} D^{-l(x_j)} > 1\]

contradiction

Efficacité du code

$p_i$ : probabilité d’occurrence de $x_i$.

On veut minimiser :

\[\sum\limits_{ i∈I } p_i l(x_i) = L(C) \\ = E(l(X))\]

Th : $∀C$,

\[H_D(X)≤ L(C)\]

avec égalité ssi :

\[\begin{cases} \sum\limits_{ i } D^{-l(x_i)} = 1 \\ p_i = D^{-l(x_i)} \\ \end{cases}\]

Preuve :

On pose

  • $l_i ≝ l(x_i)$
  • $C ≝ \sum\limits_{ i } D^{-l(x_i)} ≤ 1$
  • $r_i ≝ \frac{D^{-l_i}}{C}$
\[L( C ) - H_D(X) = \sum\limits_{ i }p_i \log_D\left(\frac{p_i}{D^{-l_i}}\right) \\ = \sum\limits_{ i }p_i \log_D\left(\frac{p_i}{Cr_i}\right) \\ = \underbrace{\sum\limits_{ i }p_i \log_D\left(\frac{p_i}{Cr_i}\right)}_{ = D(P \Vert r) ≥ 0 \text{ avec égalité si } p=r} + \underbrace{\log_D\left(\frac{1}{C}\right)}_{≥0 \text{ avec égalité si } C=1}\]

Codage de Shannon-Fano

Étant donnés les $p_i$, comment choisir les $l_i$ ?

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

\[p_i = D^{-l_i} \\ ⟹ l_i = \lceil -\log_D(p_i) \rceil\] \[H_D(X) ≤ L( C ) = \sum\limits_{ i } p_i \lceil -\log_D(p_i) \rceil ≤ \sum\limits_{ i } p_i ( -\log_D(p_i) +1) = H_D(X) + 1\]

Autre codage, plus fin

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

Blocs de $k$ caractères :

\[H_D(X_1, ⋯, X_k) ≤ L( C ) ≤ H_D(X_1, ⋯, X_k) + 1 \\ k H_D(X_1) ≤ L( C ) ≤ k H_D(X_1) + 1\]

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

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

Algorithme de Huffman

Ex : $𝛴 ≝ \lbrace 0, 1 \rbrace$

$x_i$ $x_1$ $x_2$ $x_3$ $x_4$ $x_5$
$p_i$ 0,25 0,25 0,2 0,15 0,15 
  graph {
    rankdir=LR;
    x_2 -- y_2[label="0"];
    x_3 -- y_2[label="1"];
    x_4 -- y_1[label="0"];
    x_5 -- y_1[label="1"];
    x_1 -- y_3[label="0"];
    y_1 -- y_3[label="1"];
    y_2 -- y_4[label="0"];
    y_3 -- y_4[label="1"];
  }

Ex2 :

Si $D = \vert 𝛴 \vert > 2$ : à chaque étape, on élimine $D-1$ caractères

Il faut que $n≡1 \mod (D-1)$

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 $x_i$ ($+D-2$ éventuellement auxquels on donne une proba nulle pour que $n≡1 \mod (D-1)$)
  • Puis, on en retire $\frac{n-1}{D-1}$

⟶ au pire : $2n$ fois ces opérations qui coûtent $\log n$

⟹ complexité amortie en $O(n \log n)$

Lemme :

  • $p_1 ≥ ⋯ ≥ p_n$
  • $n \mod (D-1) = 1$

$∃C$ préfixe optimal $\lbrace l_i \rbrace_{i≤n}$ qui vérifie :

  • Si $p_i > p_j$ alors $l_i ≤ l_j$
  • “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 à $1 \mod (D-1)$

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 $n≡1 (D-1)$

  3. Extraire $D$ événements $y_1, ⋯, y_D$ du tas min de probas $P_{y_1}, ⋯ , P_{y_D}$

  4. Créer un événement $z$ de proba $\sum_i P_{y_i}$

  5. Insérer $z$ dans le tas

  6. $z$ est père des $y_{D_i}$

Complexité : en $𝛳(n \log n)$

Correction : $∃C$ optimal

Shannon - Fano - Elias

  • $𝒳 = \lbrace 1, ⋯, n \rbrace$
  • $p_1, ⋯, p_n >0$
  • $𝛴 = \lbrace 0, 1 \rbrace$
\[F_X(x) ≝ \sum\limits_{ y ≤ x } P_y \\ F_X^-(x) ≝ \sum\limits_{ y < x } P_y = F_X(x-1)\\ \overline{F}_X(x) ≝ F_X^-(x) + P_x/2 ∈ ]0,1[\]
  41 2 3 4 53
$P_x$ 0,25 0,25 0,2 0,15 0,15
$F(x)$ 0,25 0,5 0,7 0,85 1
$\overline{F}(x)$ 0,125 0,375 0,6 0,775 0,925

Idée : “$\overline{F}(x)$” servira de codage

\[\lfloor x \rfloor_l ≝ \text{ troncature aux } l \text{ premiers bits après la virgule}\]

En base 2 :

\[1/3 = 0,01010101⋯ \\ \lfloor x \rfloor_4 = 0,0101\] \[C(x) = \lfloor \overline{F}(x) \rfloor_{\lceil -\log p(x) \rceil+1} \\ ⟹ l(C) ≤ H(X) + 2\]

Le tableau devient :

  41 2 3 4 53
$P_x$ 0,25 0,25 0,2 0,15 0,15
$F(x)$ 0,25 0,5 0,7 0,85 1
$\overline{F}(x)$ 0,125 0,375 0,6 0,775 0,925
$l(x)$ 3 3 4 4 4
$\overline{F}(x)$ en base 2 0,001 0,011 $0,1\overline{001}$ $0,110\overline{0011}$ $0,111\overline{0110}$
$C(x)$ en base 2 001 011 1001 1100 1110
\[0 ≤ \overline{F}(x) - \lfloor \overline{F}(x) \rfloor_{l(x)} < 2^{-l(x)} ≤ 2^{\log(p(x)) -1} = p(x)/2\] \[\lfloor \overline{F}(x) \rfloor_{l(x)} ∈ ]F(x-1), \overline{F}(x)] \\ \lfloor \overline{F}(x+1) \rfloor_{l(x)} ∈ ]F(x), \overline{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 $x_1, ⋯, x_i, ⋯, x_b$

  • \[F^-(x_1 ⋯ x_{i+1}) = F^-(x_1 ⋯ x_{i+1}) + p(x_1⋯x_n) F^-(x_{i+1})\]
  • \[p(x_1 ⋯ x_{i+1}) = p(x_1 ⋯ x_i) p(x_{i+1})\]
  • On a les tables statiques de $F^-$ et $p$, et on calcule dynamiquement $F^-(x_1 ⋯ x_{i+1})$ et $p(x_1 ⋯ x_{i+1})$

Décodeur

  • Décodeur : reçoit $\lfloor \overline{F}(x_1 ⋯ x_b) \rfloor_{l(x_1 ⋯ x_b)}$

  • \[F^-(x_1)< ⋯ < F^-(x_1 ⋯ x_b) < \lfloor \overline{F}(x_1 ⋯ x_b) \rfloor_{l(x_1 ⋯ x_b)} < F^-(x_1 ⋯ (x_b + 1)) < F^-(x_1 ⋯ (x_{b-1} + 1)) < ⋯ < F^-(x_1 + 1)\]

  • Le décodeur a la table des $0=F^-(1), ⋯, F^-(n+1)=1$ ⟶ avec l’encadrement précédent, il détermine $x_1$ en $O(n)$

  • Avec $F^-(x_1 x_2) = F^-(x_1) + p(x_1) F^-(x_2)$, le décodeur détermine $x_2$ en $O(n)$

Codage statique VS Codage adaptatif

Codage statique

La codeur connaît $p_1, ⋯, p_n$

  • 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 ≝ (x_1, ⋯, x_n)$

La distribution $p_1, ⋯, p_n$ 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) = \frac{\text{ nombre d'occurrences de } x}{n}\]

Avec proba 1 :

\[p^{(n)}(x) ⟶_{n \to ∞} p(x)\]

Huffmann adaptatif :

Codage $C_n$ obtenu obtenu à partir des occurrences des $n$ premières lettres pour encoder $x_{𝛼(n+1)}$

Mais ça coûte $O(n \log n)$ à 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 : $C_{n+1}$ à partir de $C_n$

$C_{n-1}(x_n)$ :

code de Huffmann obtenu à partir des fréquences d’événements $x_1, ⋯, x_{n-1}$.

Prop : $x_1, ⋯, x_n$, $p_1, ⋯, p_n$, de poids (compte d’occurrences) $w_1, ⋯, w_n$

Arbre associé à un code préfixe a $2n-1$ sommets :

CNS : $∃$ une numérotation $u_1, ⋯, u_{2n-1}$ tq

  • $∀i<j, w(u_i) ≤ w(u_j)$

  • $∀ 1 ≤ i ≤ n$, $u_{2i-1}$ et $u_{2i}$ 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.

$x_n$ apparaît :

  • on incrémente la feuille associée à $x_n$ soeur $v_{j+1}$ telle que $v_{j+1}> v_n$, et on intervertit $x_j$ et $x_n$
  • 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(C_n)⟶_{p.s} l(C)\]

où $C$ est le code de Huffmann.

Ex :

$X ≝ \lbrace a, b, c, d, e, f \rbrace$

  graph {
    rankdir=TB;
    32[label="11"];
    11[label="11 | f, 9"];
    21[label="21, 10"];
    10[label="10, 7"];
    112[label="11, 8"];
    51[label="5 | c, 3"];
    52[label="5 "];
    53[label="5 | d, 4"];
    6[label="5 | e, 6"];
    2[label="2
    | a, 1"];
    3[label="3
    | b, 2"];
    32 -- 11, 21;
    21 -- 10, 112;
    10 -- 51, 52;
    52 -- 2, 3;
    11 -- 53,6;
  }

Code arbitraire : sur $x_1, ⋯, x_n$, $c_1, ⋯, c_n$

  • Codeur $⟶^{x_3}c_3$ Décodeur
  digraph {
    rankdir=TB;
    12[label="1 | x_3"];
    0[label="0 | ?"];
    1 -> 0, 12;
  }
  • Codeur $⟶^{x_1}0c_1$ Décodeur
  digraph {
    rankdir=TB;
    12[label="1 | x_3"];
    22[label="2 | x_1"];
    0[label="0 | ?"];
    1 -> 2, 12;
    2 -> 0, 22;
  }

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 : $2\log n = O(\log n)$)

Flux : préfixe de longueur $n$

\[w_n ≝ u_1 ⋯ u_n\]
$c_i^{(n)}$ :

nombre d’occurrences de $x_i$ dans $w_n$

$X_i$ :

v.a du tirage de la lettre $i$

\[S_n ≝ - \frac 1 n \sum\limits_{ i≤n } \log (p(X_i))\]

Par la loi forte des grands nombres :

\[S_n ⟶_{p.s} H_X\]

Soit

\[m≝u_1 ⋯ u_n\] \[m = y_1 y_2 ⋯ y_{c(n)}\]

où les $y_i$ sont les mots produits par Ziv-Lempel.

\[\vert c(n) \vert≤ \lceil (\log c(n) \rceil + 1) c(n)\]
$c(l)$ :

nombre de mots de longueur $l$

LEMME :

\[\sum\limits_{l∈ℕ } c_l \log (c_l) ≤ - \sum\limits_{ i ≤n } \log (p(u_i)) \\ ⟺ \frac 1 n \sum\limits_{ 1 ≤ l≤ c(n) } c_l \log (c_l) ≤ - \frac 1 n \sum\limits_{ i ≤n } \log (p(u_i)) ⟶_{p.s} H(X)\]

Preuve : \(p(u_1 ⋯ u_k) = \prod\limits_{1 ≤ i ≤k} p(u_i)\)

\[\begin{align*}- \sum\limits_{ i ≤n } \log p(u_i) & = - \sum\limits_{ 1≤j≤c(n) } \log (p(y_j)) \\ & = - \sum\limits_{ l∈ℕ } c_l \sum\limits_{ \vert y_j \vert = l} \frac{1}{c_l} \log (p(y_j))\\ & ≥ - \sum\limits_{ l∈ℕ } c_l \log ( \frac{1}{c_l}) \sum\limits_{ \vert y_j \vert = l} p(y_j) \\ & ≥ \sum\limits_{ l∈ℕ } c_l \log (c_l) \end{align*}\]

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

Leave a comment