On appelle algorithme de compression sans perte toute procédure de codage ayant pour objectif de représenter une certaine quantité d'information en utilisant ou en occupant un espace plus petit, permettant ainsi une reconstruction exacte des données d'origine. C'est-à-dire que la compression sans perte englobe les techniques permettant de générer un duplicata exact du flux de données d'entrée après un cycle de compression/expansion. Pour cette raison, la compression sans perte est utilisée pour compresser des fichiers contenant des données qui ne peuvent pas être dégradées ou perdues, tels que des fichiers textes, images et son[1],[2].
Ce type de compression est basé sur les concepts de la théorie de l'information, tels que la redondance et l'entropie des données et est généralement implémenté à l'aide d'un ou deux types de modèles différents : statique et basé sur dictionnaire.
Méthodes de compression
modifierLe modèle statique encode les données à partir de probabilités prédéfinies d'apparition des symboles. Dans sa forme la plus simple, il repose sur une table de fréquences fixe. La construction d'un arbre de Huffman complet peut être coûteuse en calcul ; des échantillons représentatifs des données sont donc souvent analysés afin d'établir une table de fréquences utilisée pour générer l'arbre appliqué au reste des données. Toutefois, un modèle statique présente des limites : si les caractéristiques du flux d'entrée diffèrent des statistiques initialement établies, le taux de compression peut diminuer, voire produire un fichier plus volumineux que les données d'origine. Des modèles adaptatifs ont ainsi été développés afin de construire les tables dynamiquement lors du traitement du flux de données[3].
Les méthodes fondées sur un dictionnaire remplacent des séquences de symboles par des références plus courtes. Contrairement aux modèles statiques, qui codent généralement les symboles individuellement, ces méthodes recherchent des groupes de symboles déjà présents dans un dictionnaire et les remplacent par un indice ou un pointeur correspondant.
Parmi les principaux algorithmes de compression sans perte figurent les algorithmes Lempel-Ziv, notamment LZ77 et LZ78[4], ainsi que LZW[5].
La compression sans perte est utilisée dans de nombreux archiveurs de fichiers, tels que RAR, gzip, bzip2, ZIP, 7z, ARJ et Lha. Elle est également employée pour certains formats d'image, comme PNG ou le RLE, ainsi que pour des formats audio tels que FLAC et Monkey's Audio. En vidéo, son usage reste plus limité en raison des volumes de données, mais elle peut être utilisée lors de la capture ou du montage.
Il existe plusieurs méthodes de compression sans perte. Le codage RLE (run-length encoding), par exemple, remplace des séquences répétitives de valeurs identiques par une valeur unique accompagnée du nombre de répétitions. Cette méthode est particulièrement adaptée aux graphiques simples comportant de longues suites de données identiques.
Il n'existe cependant pas d'algorithme de compression universel capable de compresser efficacement tous les types de données. Toute méthode de compression sans perte comporte des cas où les données sont peu compressées, voire augmentées en taille[1].
Formats de fichier de compression sans perte
modifierLes formats de fichier de compression sans perte sont identifiés grâce à l'extension ajoutée à la fin du nom de fichier (« nomdefichier.ZIP » par exemple), d'où leur dénomination très abrégée. Les formats les plus courants sont :
- 7z
- ACE
- ARC
- APE (pour les flux audio)
- ARJ
- bz, bz2 (tar peut être utilisé pour créer les archives de ce type)
- CAB, utilisé par Microsoft
- FLAC (pour les flux audio)
- FFV1 (pour les flux vidéo)
- gzip, gz (qui est un fichier à une seule entrée, tar peut être utilisé pour créer les archives de ce type)
- lzh
- RAR
- RK
- UHA
- XZ implémenté par XZ Utils
- Z (surtout sous Unix)
- ZIP
- zoo
Les standards ouverts les plus courants sont décrits dans plusieurs RFC :
Voir aussi
modifier- Analyse en graphe de puissance, forme d'algorithme de compression sans perte
- Algorithme de compression avec perte
- Wavelets
- zip
- PDM
- CAB
- LHA
- DGCA
- GCA
- Catégorie:Algorithme_de_compression_sans_perte
Notes et références
modifier- « La compression de données - Les deux types », sur igm.univ-mlv.fr (consulté le 28 mars 2019)
- ↑ (en) « Universal lossless data compression algorithms »
- ↑ « History of Lossless Data Compression Algorithms », sur ETHW (consulté le 28 mars 2019)
- ↑ Jacob Ziv et Abraham Lempel, « A Universal Algorithm for Sequential Data Compression », IEEE Transactions on Information Theory, vol. 23, no 3, mai 1977, p. 337-343 (DOI 10.1109/TIT.1977.1055714, lire en ligne [PDF])
- ↑ Terry A. Welch, « A Technique for High-Performance Data Compression », IEEE Computer, vol. 17, no 6, juin 1984, p. 8-19 (DOI 10.1109/MC.1984.1659158)
- ↑ (en) Request for comments no 1950
- ↑ (en) Request for comments no 1951
- ↑ (en) Request for comments no 1952
