Algorithme de compression sans perte
Techniques de compression sans perte De Wikipédia, l'encyclopédie libre
Techniques de compression sans perte De Wikipédia, l'encyclopédie libre
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 .
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 :
Les standards ouverts les plus courants sont décrits dans plusieurs RFC :
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
