Algorithme de compression sans perte

vignette|Comparaison de la compression d'image entre les formats JPG (à gauche) et PNG (à droite). PNG utilise une 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. 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.