La compression sans pertes ou codage entropique désigne un ensemble de méthodes de mathématiques discrètes pour réduire le volume occupé par des données (par exemple un fichier de texte) en réduisant la redondance statistique présente dans les données. La méthode la plus utilisée consiste à utiliser des représentations codées à longueur variable, le code étant d’autant plus court que l’élément à coder est fréquent. Cette technique s’applique directement aux fichiers de données que l’on veut comprimer sans erreur mais elle peut aussi s’appliquer en s’ajoutant à des techniques de compression avec perte (compression de son, d’images, de vidéo) de façon à améliorer les performances. La mesure théorique de compression s’effectue à l’aide d’un outil de théorie de l’information appelé l’entropie qui représente le taux minimum en deçà duquel on ne plus comprimer l’information sans perte. Les algorithmes standard de compression utilisent trois techniques fondamentales: codage de Huffman, codage de Lempel-Ziv, codage arithmétique.
Tout système de traitement numérique de signaux (son, parole, image, vidéo)
Résultats attendus (à adapter en fonction des besoins)
Connaissances : codage à longueur variable, codes de Fano-Shannon, codes de Huffman, codage de Lemel-Ziv, codage arithmétique, entropie et théorème de Shannon.
Compétence : comprendre la problématique de la compression sans pertes et et être capable de mettre en oeuvre un algorithme de codage adaptatif à longueur variable.
Livrable : pseudo-code / code commenté et structuré de manière à être lisible; tests sur des sources académiques avec ou sans mémoire.
