Algorithme de compression sans perte

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].

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
• 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)

• 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

• Les algorithmes de compression sans perte
• La compression sans perte