« Compression de données/Introduction » : différence entre les versions
Contenu supprimé Contenu ajouté
m sans explication (comme dans l'article ad hoc) ce schéma est incompréhensible |
m →Taux de compression : Ajout de la démonstration d'existence des fichiers non-compressibles |
||
Ligne 200 :
{{Article détaillé|Taux de compression de données}}
Le taux de compression
'''Exemple :''' <
▲:τ = 1 - (250/550) = 54 %.
L'algorithme utilisé pour transformer <math>A</math> en <math>B</math> est destiné à obtenir un résultat <math>B</math> de taille inférieure à <math>A</math>. Il peut paradoxalement produire parfois un résultat de taille supérieure : dans le cas des compressions sans pertes, il existe ''toujours'' des données incompressibles, pour lesquelles le flux compressé est de taille supérieure ou égale au flux d'origine.
{{Démonstration/début|titre=Démonstration de l'existence de fichiers non-compressibles avec un algorithme de compression sans pertes}}
Ceci se démontre par l'[[Raisonnement par l'absurde|absurde]] :
* Considérons un algorithme de compression '''sans pertes''' <math>C</math>.
* Considérons l'ensemble <math>F</math> de tous les flux de taille <math>N</math> : <math>F : \forall A \in F_N, Sz(A)=N</math> (avec <math>Sz(A)</math> la fonction de calcul de taille d'un flux).
* L'algorithme étant sans pertes, il y a une [[bijection]] entre les flux d'origine <math>F_N</math> et les flux compressés <math>C(F_N)</math>.
** En effet, si l'algorithme n'était pas bijectif, alors il existerait deux flux <math>A</math> et <math>A'</math> ayant le même flux compressé <math>B</math>.
** À la décompression, il n'est pas possible de savoir s'il faut restituer le flux <math>A</math> ou <math>A'</math> : ceci réclamerait au minimum un bit pour être codé.
** Donc, soit l'algorithme <math>C</math> est soit avec pertes (impossible par exemple de restituer le flux <math>A'</math>), soit les deux flux <math>A</math> et <math>A'</math> n'ont pas la même image compressée <math>B</math>, car l'algorithme produira deux flux compressés différents d'au moins un bit.
** En conséquence, un algorithme <math>C</math> sans pertes ne peut être qu'une [[bijection]] de <math>F_N</math> vers <math>C(F_N)</math>, c'est à dire qu'aucune image ne possède deux antécédents distincts : <math>\forall B \in C(F_N),\exist! A \in F_N / C(A)=B</math>.
** De plus, <math> \forall (A,A') \in F_N^2, ( A=A' \Rightarrow C(A)=C(A') ) \and ( A \neq A' \Rightarrow C(A) \neq C(A') )</math>.
* 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^0=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.
* L'hypothèse <math>H</math> est donc fausse, donc son opposé logique est vrai : <math>\exist A \in F_N / Sz(C(A))\ge Sz(A)</math>.
Donc, quelle que soit la taille de flux utilisée ou la nature des données, il existera toujours au moins un flux compressé plus grand que son original, donc un flux non-compressible.
A noter qu'en prenant le cas extrême d'un flux d'un seul octet, le raisonnement est trivial (le flux compressé ne peut faire zéro octet de longueur), mais ne permet pas de généraliser la démonstration à toutes les tailles de fichier possibles, ni d'être indépendant de la nature des données du flux.
'''ATTENTION :''' Ceci n'est vrai '''que''' pour les algorithmes de compression <u>sans pertes</u>. En utilisant un algorithme avec pertes, on peut garantir au contraire que <math>card(C(F_N))<card(F_N)</math> et donc que tout fichier est compressible, au prix justement d'une perte d'information plus ou moins importante lors de la compression/décompression du flux.
{{Démonstration/fin}}
== Codage conjoint source-canal ==
| |||