« Compression de données/Introduction » : différence entre les versions

Contenu supprimé Contenu ajouté
Mac LAK (discussion | contributions)
m →‎Taux de compression : Ajout de la démonstration d'existence des fichiers non-compressibles
Mac LAK (discussion | contributions)
m →‎Taux de compression : retouche de la modification précédente
Ligne 220 :
* Prenons l'hypothèse <math>H</math> que tout flux compressé est plus petit que le flux d'origine : <math>\forall A \in F_N, Sz(C(A))<Sz(A)</math>
** En prenant comme unité de taille l'octet (<math>2^8=256</math> valeurs distinctes), le nombre total de fichiers distincts de taille <math>N</math> est <math>card(F_N)=256^N</math>.
** Le nombre total de fichiers de taille au plus égale à <math>(N-1)</math> est <math>card(C(F_N))=\sum_{i=1}^N 256^i</math>, ce qui correspond à une [[série géométrique]] : la valeur recherchée est donc <math>(\frac{256^N-1}{256-1})-1</math><ref>On retranche ''256^0256⁰=1'' de la somme car aucun flux compressé ne peut être de taille nulle.</ref>.
** On constate de façon triviale que <math>(\frac{256^N-1}{256-1})-1 < 256^N</math> : donc, il y a '''strictement''' moins de fichiers de taille <math>1</math> à <math>(N-1)</math> que de fichiers de taille <math>N</math>.
** Or, l'algorithme <math>C</math> est bijectif : donc, <math>card(F_N)=card(C(F_N))</math>. Or, l'inégalité précédente donne <math>card(C(F_N))<card(F_N)</math>, ce qui est absurde.