Algorithme de compression sans perte
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
[modifier | modifier le code]Le modèle statique lit et code en utilisant la probabilité d'apparition de chaque caractère. Sa forme la plus simple utilise une table de probabilités statiques. La génération d'une arborescence de Huffman remplie de données présente un coût de calcul important, par conséquent, celle-ci n'est pas toujours générée, mais des blocs de données représentatifs sont analysés, ce qui donne lieu à un tableau de fréquences caractéristique. À partir de là, une arborescence de Huffman est générée, généralisée au reste des données, donnant lieu à un modèle statique. Cependant l'utilisation d'un modèle statique a ses limites. Si un flux d'entrée ne correspond pas bien aux statistiques précédemment accumulées, le taux de compression se dégraderait, au point que le flux de données sortant était aussi long que le flux entrant (voire plus long). Par conséquent, la prochaine amélioration évidente consistait à créer une table construite à la réception du flux d'entrée[3].
Le modèle basé sur un dictionnaire utilise un code simple pour remplacer des chaînes de symboles ; les modèles statiques codent généralement un symbole à la fois. Le schéma de compression basé sur un dictionnaire utilise un concept différent. Il consiste en la lecture d'une entrée de données et en l'observation par groupes de symboles qui apparaissent dans le dictionnaire. Si une chaîne correspond, un indicateur ou un index du dictionnaire peut apparaître à la place du code de symbole.
Quelques exemples d'algorithme de compression sans perte sont les algorithmes Lempel-Ziv, qui incluent LZ77 LZ78 et LZW .
Ce système de compression est utilisé dans les archiveurs de fichiers (RAR, gzip, bzip2, ZIP, 7z, ARJ, Lha) et de DAR ; également pour les images (PNG, RLE) et dans certains formats audio (FLAC, Monkey's Audio). En vidéo, son utilisation est moins courante. Il peut être utilisé pour la capture et l'édition, mais pas commercialisé pour la reproduction domestique.
Il existe différentes méthodes de compression sans perte. Par exemple, il existe une compression RLE ou un codage de longueur d'exécution (utilisé pour les fichiers BMP), qui prend des séquences de données (données provenant d'éléments consécutifs avec des valeurs identiques) et les stocke dans une valeur unique plus son compte. Ceci convient mieux aux graphiques simples, où il existe de longues séries d'éléments de données identiques.
Toutefois, il n'existe pas d'algorithme de compression universel, c'est-à-dire capable de comprimer tout type de donnée ; en effet il existera au moins toujours un type de donnée qui ne sera pas comprimé significativement, voire agrandi, par une méthode capable de comprimer au moins un type de données efficacement[1].
Formats de fichier de compression sans perte
[modifier | modifier le code]Les formats de fichier de compression sans perte sont connus 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 :
- RFC 1950[4] (ZLIB, flux de données compressées)
- RFC 1951[5] (système de compression par blocs « Deflate », utilisé par Zip et gz)
- RFC 1952[6] (format de fichier compressé gzip)
Voir aussi
[modifier | modifier le code]- 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 | modifier le code]- « La compression de données - Les deux types », sur igm.univ-mlv.fr (consulté le )
- (en) « Universal lossless data compression algorithms »
- « History of Lossless Data Compression Algorithms — ETHW », sur ethw.org (consulté le )
- (en) Request for comments no 1950
- (en) Request for comments no 1951
- (en) Request for comments no 1952
