Compression de données universelle

Compression de données universelle

Un compresseur sans perte universel ne peut pas exister. Plus précisément, pour tout compresseur sans perte, on est certain que :

  1. il est impossible de compresser strictement tous les mots ;
  2. s'il existe un mot qui est strictement compressé alors il existe un autre mot dont la version compressée est strictement plus grande que le mot lui-même ;
  3. pour n'importe quel mot de départ auquel on applique de manière répétée le compresseur, on est nécessairement dans l'un des cas de figure suivants
  • soit une suite de mots se répète infiniment,
  • soit les mots successifs obtenus atteignent des tailles arbitrairement grandes.

Ces propriétés sont démontrées ci-après. Cependant, elles n'enlèvent rien à l'intérêt des compresseurs sans perte. En effet, dans la pratique, les mots, messages ou fichiers que l'on souhaite compresser ne sont pas quelconques et choisis aléatoirement parmi tous les mots, messages ou fichiers possibles. Les compresseurs se servent de leurs particularités. Des compresseurs seront alors très bons avec certains types de données, et très mauvais avec d'autres.

Ainsi pour ces types de compresseurs spécialisés, l'information fournie par le contexte est utilisée pour la compression (voir théorie de l'information).

Sommaire

Expérimentation

On peut aisément vérifier expérimentalement cette impossibilité. Voici un script shell qui crée un fichier comportant 100 fois la ligne "blabla" puis qui effectue 100 compressions successives de ce fichier à l'aide du compresseur gzip et enfin affiche les tailles successives obtenues :

for i in `seq 1 100`; do echo "blabla" >> toto001; done
for i in `seq 1 100`; do gzip -c "toto`printf "%03d" $i`" > "toto`printf "%03d" $((i+1))`"; done
wc -c toto*

On vérifie souvent en pratique qu'un fichier qui est déjà le résultat d'une compression se compresse mal, voire grossit par application du compresseur. D'ailleurs, gzip refuse par défaut de compresser les fichiers comportant l'extension ".gz" qui est le signe d'une précédente application de ce compresseur.

Preuve mathématique

Un compresseur sans perte peut être vu comme une injection des mots dans les mots, c'est-à-dire une fonction C telle que

C(u) = C(v) implique u = v.

On vérifie alors aisément que, pour tout mot u, l'un des deux cas suivants est vérifié :

  1. la suite (Cn(u))n est périodique,
  2. la suite (Cn(u))n ne contient jamais deux fois le même mot et donc pour tout entier N \in \mathbb{N} il existe un entier k tel que le mot Ck(u) est de taille supérieure à N.

Ceci montre la troisième propriété de l'impossibilité énoncée ci-dessus. Les deux premières en découlent car, s'il y a compression stricte, c'est-à-dire s'il existe un mot u plus grand que sa version compressée C(u), alors :

  • soit u est dans un cycle de longueur k et il existe i\leq k-1 tel que le mot Ci(u) est strictement plus petit que sa version compressée Ci + 1(u),
  • soit la suite (Cn(u))n ne contient jamais deux fois le même mot donc elle contient un mot strictement plus petit que sa version compressée (car on ne peut pas avoir une suite infinie décroissante, au sens large, de mots tous distincts).

On peut remarquer par ailleurs qu'il est impossible de compresser strictement tous les mots d'une taille N donnée : en effet il y a aN mots de taille N pour un alphabet à a lettres et seulement \frac{a^N-1}{a-1} mots avec strictement moins de N lettres.

Voir aussi

Articles connexes

Liens externes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Compression de données universelle de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • COMPRESSION DES DONNÉES — On peut chercher à rendre minimale la longueur d’un message en codant celui ci. Si, après décodage, on retrouve exactement le message initial, on dit que le code est réversible, ou bijectif. Ce type de codage est nécessaire pour des messages de… …   Encyclopédie Universelle

  • Compression de données — La compression de données ou codage de source est l opération informatique qui consiste à transformer une suite de bits A en une suite de bits B plus courte, contenant les mêmes informations, en utilisant un algorithme particulier. Il s agit d… …   Wikipédia en Français

  • Liste des normes de l'Union internationale des télécommunications — Les normes et recommandations principales de l UIT T sont : Sommaire 1 A Organisation du travail de l UIT T 2 B Signification des expressions : définitions, symboles, classification 3 C Statist …   Wikipédia en Français

  • Recommandations CCITT — Liste des normes de l Union internationale des télécommunications Les normes et recommandations principales de l UIT T sont : Sommaire 1 A Organisation du travail de l UIT T 2 B Signification des expressions : définitions, symboles,… …   Wikipédia en Français

  • Recommandations ITU — Liste des normes de l Union internationale des télécommunications Les normes et recommandations principales de l UIT T sont : Sommaire 1 A Organisation du travail de l UIT T 2 B Signification des expressions : définitions, symboles,… …   Wikipédia en Français

  • V.23 — Liste des normes de l Union internationale des télécommunications Les normes et recommandations principales de l UIT T sont : Sommaire 1 A Organisation du travail de l UIT T 2 B Signification des expressions : définitions, symboles,… …   Wikipédia en Français

  • V.42 — Liste des normes de l Union internationale des télécommunications Les normes et recommandations principales de l UIT T sont : Sommaire 1 A Organisation du travail de l UIT T 2 B Signification des expressions : définitions, symboles,… …   Wikipédia en Français

  • Machine De Turing — Pour les articles homonymes, voir Turing (homonymie). Une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur et sa mémoire, créé par Alan Turing en vue de donner une définition précise …   Wikipédia en Français

  • Machine de turing — Pour les articles homonymes, voir Turing (homonymie). Une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur et sa mémoire, créé par Alan Turing en vue de donner une définition précise …   Wikipédia en Français

  • Automate cellulaire — À gauche, une règle locale simple : une cellule passe d un état (i) au suivant (i+1) dans le cycle d états dès que i+1 est présent dans au moins 3 cellules voisines. À droite, le résultat (complexe) de l application répétée de cette règle… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”