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

Un livre de Wikilivres.
Contenu supprimé Contenu ajouté
imported>Mastermatt29
Ligne 1 : Ligne 1 :
[[de:Datenkompression]] [[en:Data compression]] [[es:Compresión de datos]] [[ko:데이터 압축]] [[id:Kompresi data]] [[hu:Adattömörítés]] [[nl:Datacompressie]] [[ja:データ圧縮]] [[pl:Kompresja]] [[pt:Compressão de dados]] [[simple:Data compression]] [[fi:Pakkausohjelma]] [[sv:Datakompression]] [[th:การบีบอัดข้อมูล]]
[[de:Datenkompression]] [[en:Data compression]] [[es:Compresión de datos]] [[ko:데이터 압축]] [[id:Kompresi data]] [[hu:Adattömörítés]] [[nl:Datacompressie]] [[ja:データ圧縮]] [[pl:Kompresja]] [[pt:Compressão de dados]] [[simple:Data compression]] [[fi:Pakkausohjelma]] [[sv:Datakompression]] [[th:การบีบอัดข้อมูล]]


[[Catégorie:Théorie de l'information|Compression de donnees]] [[Catégorie:Informatique]]
[[Catégorie:Théorie de l'information|Compression de donnees]] [[Catégorie:Format de données numériques]]


La '''compression de données''' traite de la manière dont on peut réduire la quantité de symboles utilisés pour représenter une information quelconque. En cela, elle se rattache donc à la [[théorie de l'information]].
La '''compression de données''' traite de la manière dont on peut réduire la quantité de symboles utilisés pour représenter une information quelconque. En cela, elle se rattache donc à la [[théorie de l'information]].

Version du 15 mars 2005 à 14:55


La compression de données traite de la manière dont on peut réduire la quantité de symboles utilisés pour représenter une information quelconque. En cela, elle se rattache donc à la théorie de l'information.

La compression peut concerner un flux d'information transmis ou un ensemble statique de données (par exemple un fichier). Dans le premier cas, on réduit ce qui est à transporter dans l'espace. Dans le second, ce qui doit être transporté dans le temps.

Compression sans perte

La compression est dite sans perte lorsqu'il n'y aucune perte de données sur l'information d'origine. Il y a autant d'information après la compression qu'avant, elle est seulement réécrite d'une manière plus concise (c'est par exemple le cas de la compression gzip). La compression sans perte est dite aussi compactage.


L'information à compresser est vue comme la sortie d'une source de symboles qui produit des textes finis selon certaines règles. Le but est de réduire la taille moyenne des textes obtenus après la compression tout en ayant la possibilité de retrouver exactement le message d'origine (on trouve aussi la dénomination codage de source en opposition au codage de canal qui désigne le codage correcteurs d'erreurs).

Les formats de fichier de compression sans perte les plus courants sont :

  • gzip, gz
  • bz, bz2
  • rar
  • Z (sur stations sun)
  • zoo
  • zip
  • lzh
  • arj
  • arc

Les standards ouverts les plus courants sont décrits dans plusieurs RFCs :

  • RFC 1950 (ZLIB, flux de données compressées)
  • RFC 1951 (système de compression par blocs « DEFLATE », utilisé par zip et gz)
  • RFC 1952 (format de fichier compressé GZIP)

Codage Huffman

L'idée qui préside au codage de Huffman est voisine de celle utilisée dans le code Morse : coder ce qui est fréquent sur peu de place, et coder en revanche sur des séquences plus longues ce qui revient rarement. En morse le e, lettre très fréquente, était codé par un simple point, le plus bref de tous les signes.

L'originalité de David A. Huffman est qu'il fournit un procédé d'agrégation objectif permettant de constituer son code dès lors qu'on possède les statistiques d'utilisation de chaque caractère.

Le Macintosh d'Apple codait les textes dans un système inspiré de Huffman : les 15 lettres les plus fréquentes (dans la langue utilisée) étaient codées sur 4 bits, et la 16e combinaison était un code d'échappement indiquant que la lettre était codée en ASCII sur les 8 bits suivants. Ce système permettait une compression des textes voisine en moyenne de 30% à une époque où la mémoire était extrêmement chère par rapport aux prix actuels (compter un facteur 1000).

Codage RLE

Les lettres RLE signifient Run-length encoding. Il s'agit d'un mode de compression parmi les plus simples : toute suite de bits ou de caractères identiques est remplacée par un couple (nombre d'occurrences ; bit ou caractère répété).

Lempel-Ziv

La compression Lempel-Ziv est dite de type dictionnaire. Elle est basée sur le fait que des succession de caractère ce retrouve plus souvent que d'autre et quel l'on va le remplacer par un nouveaux caractère. Le dictionnaire est construit dinamiquement d'après les caractère rencontré.

Voir à LZW

Compression avec pertes

Utilisée pour compresser des photos, des bandes musicales, des films, ...

Cette technique est fondée sur une idée simple : seul un sous-ensemble très faible de toutes les images possibles (à savoir celles que l'on obtiendrait par exemple en tirant les valeurs de chaque pixel par un générateur aléatoire) possède un caractère exploitable et informatif pour l'œil. Ce sont donc ces images-là qu'on va s'attacher à coder de façon courte. Dans la pratique, l'œil a besoin pour identifier des zones qu'il existe des corrélations entre pixels voisins, c'est-à-dire qu'il existe de zones contiguës de couleurs voisines. Les programmes de compression s'attachent à découvrir ces zones et à les coder de la façon aussi compacte que possible. Le JPEG2000, par exemple, arrive typiquement à coder des images photographiques sur 1 bit par pixel sans perte visible de qualité sur un écran, soit une compression d'un facteur 24 à 1.

De même, seul un sous-ensemble très faible de sons possibles est exploitable par l'oreille, qui a besoin de régularités engendrant elles-mêmes une redondance (coder avec fidélité un bruit de souffle n'aurait pas grand intérêt). Un codage éliminant cette redondance et la restituant à l'arrivée reste donc acceptable, même si le son restitué n'est pas en tout point identique au son d'origine.

Une compression avec pertes suivie de décompression déjoue également les risques de stéganographie.

Il y a moins d'information après la compression qu'avant, l'information retranchée étant sélectionnée d'après des critères fixés selon le type de données traitées. La compression d'une image en format jpeg est un exemple de compression avec perte. Puisque l'œil ne perçoit pas nécessairement tous les détails d'une image, il est possible de retrancher des données, dans l'espace des fréquences, de telle sorte que le résultat soit très ressemblant à l'original, voire pareil, pour l'œil. Le tout est de savoir quelles données retrancher. L'image finale n'étant pas, numériquement parlant, identique à l'image initiale, il s'agit d'une compression avec perte.

On peux determiner deux grande famille de compressions avec perte:

Récapitulatif

Domaines sans pertes avec pertes
Huffmann Dictionnaire Autre DCT Ondelette Autre
Général
binaires/données
LZW, Z, gzip, bzip2, zip RLE (Run-Length Encoding)
Audio FLAC MP3, Ogg Vorbis, Speex
Image GIF, PNG, TIFF PCX (RLE), ILBM? (ou IFF), IMG?, TGA? JPEG JPEG2000, SPIHT
Vidéo MJPEG, MPEG, MPEG-2? MPEG.4?

Note : certains algorithmes peuvent être brevetés.

Voir aussi

Modèle:Informatique et Internet