Développement d’un utilitaire de compression de données basé sur le code de Huffman avec Haskell

Implémentation d’un programme de compression de données utilisant le codage de Huffman

• Qu’est-ce que le code de Huffman ?
  • Il permet de compresser des données en associant chaque caractère à une séquence de bits unique
  • Les caractères fréquents sont associés à des séquences de bits courtes, tandis que les caractères rares sont associés à des séquences plus longues
  • Exemple : pour la chaîne aaab, a est associé à 1 et b à 0, ce qui donne la compression 1110

Code sans préfixe

• Qu’est-ce qu’un code sans préfixe ?
  • Aucun mot de code ne doit être le préfixe d’un autre mot de code
  • Exemple : pour aaabc, a est associé à 1, b à 00 et c à 01, ce qui donne la compression 1110001

Génération d’un code sans préfixe

• Méthode de génération d’un code sans préfixe
  • Placer tous les caractères comme feuilles d’un arbre binaire complet
  • Étiqueter la branche de gauche avec 1 et celle de droite avec 0
  • Le chemin de la racine jusqu’à une feuille décrit le mot de code de chaque caractère

Écriture de l’encodeur

• Définition des types

  • Définition des types Bit, Code, FreqMap, CodeMap, Weight, HTree
  • HTree est composé de Leaf et Fork

• Fonction d’encodage

  • Fonction qui convertit une chaîne en bits
  • Calcule la fréquence de chaque caractère à l’aide de FreqMap, puis génère l’arbre de Huffman sur cette base
  • Génère le mot de code de chaque caractère à partir de l’arbre de Huffman

• Fonction de décodage

  • Fonction qui reconvertit les bits en chaîne d’origine
  • Décode séquentiellement les bits à l’aide de l’arbre de Huffman

Intégration avec les fichiers binaires

• Encodage de données binaires
  • Lit les octets comme des caractères à l’aide du module Data.ByteString.Char8
  • Encode les données binaires en utilisant l’encodeur de texte

Sérialisation

• Fonction de sérialisation
  • Convertit FreqMap et les bits en octets réels, puis les enregistre dans un fichier
  • Utilise la monade Put pour générer efficacement un ByteString

Désérialisation

• Fonction de désérialisation
  • Convertit les données lues depuis le fichier en FreqMap et en bits
  • Utilise la monade Get pour désérialiser FreqMap

Intégration complète du code

• Fonctions de compression et de décompression de fichiers
  • Fonction compress : lit un fichier, génère la table de fréquences, encode les données, puis les enregistre dans un fichier compressé
  • Fonction decompress : lit un fichier compressé, décode les données, puis les enregistre dans le fichier d’origine

Améliorations

• Multithreading

  • Décode en parallèle les différentes sections du fichier
  • Ajoute une table indiquant les limites des sections et la taille attendue après décodage afin de permettre le traitement parallèle

• Encodage en un seul passage

  • Génère la table de fréquences en temps réel pendant l’encodage
  • Il n’est pas nécessaire d’inclure la table de fréquences au début du fichier

• Code de Huffman canonique

  • Décode en complexité temporelle O(1) en indexant un vecteur au lieu de parcourir l’arbre

• Génération de code plus rapide

  • Si l’on tente un encodage en un seul passage, il faut accélérer la génération de la table de codes

Avis de GN⁺

• Avantages du codage de Huffman

  • Il permet une compression efficace des données en associant les caractères fréquents à des séquences de bits courtes
  • Il permet de traiter de gros volumes de données tout en minimisant l’usage mémoire

• Avantages de Haskell

  • Il permet d’écrire un code modulaire en tirant parti des avantages de la programmation fonctionnelle
  • L’évaluation paresseuse permet d’optimiser l’utilisation de la mémoire

• Projets aux fonctionnalités similaires

  • Il existe divers outils de compression de données comme gzip et bzip2
  • Il est important de comparer les avantages et les inconvénients de chaque outil pour choisir le plus adapté

• Points à considérer lors de l’adoption de nouvelles technologies

  • Il faut choisir un algorithme adapté en tenant compte des performances et de l’usage mémoire
  • L’application de techniques d’optimisation comme l’encodage en un seul passage peut améliorer l’efficacité

[GN⁺]

Avis Hacker News

• Il existe des algorithmes in-place basés sur des tableaux, ce qui réduit le besoin d’allouer des arbres et de suivre des pointeurs

  • À l’université, en apprenant l’approche basée sur les arbres, je ne savais pas qu’il existait d’autres méthodes
  • L’approche par arbre est intuitive et pédagogique, mais lorsqu’il faut traiter rapidement beaucoup de données, utiliser un tableau in-place est plus pertinent
  • Référence : "In-Place Calculation of Minimum-Redundancy Codes" (Moffat, Katajainen, 1995)

• Dire qu’il faut empêcher qu’un mot de code soit le préfixe d’un autre mot de code n’est pas techniquement exact

  • La classe des codes uniquement décodables est un sur-ensemble des codes préfixes
  • Par exemple, l’inverse d’un code préfixe reste décodable sans ambiguïté
  • Exemple de code :

    a 1
    b 00
    c 10
    

  • Le code de a est un préfixe du code de c, mais si on le traite à l’envers, il reste décodable sans ambiguïté

• Je me demande s’il existe des tutoriels similaires qui abordent des fonctionnalités plus avancées pour écrire des programmes Haskell (transformateurs de monades, lenses, etc.)

• Le cours de programmation fonctionnelle de Coursera (Scala) propose un exercice similaire sur le codage de Huffman

  • Lien : Coursera Scala Functional Programming

• J’ai utilisé des codes de Huffman pour exécuter un programme de macros du processeur MICMAC avec un minimum de microcycles et de micro-instructions

  • J’ai établi un histogramme des macro-instructions, puis écrit un programme de microcode à décodage progressif sur cette base
  • En pratique, cela aurait probablement été lent et peu pratique
  • L’avantage des codes de Huffman est qu’ils permettent d’ajuster la profondeur des préfixes en fonction de la distribution des valeurs
  • Il fallait gérer la prédiction de branchement dans un modèle de processeur sans pipeline super-scalaire

• Informations supplémentaires sur le codage de Huffman : Rosetta Code Huffman Coding

• Question pour les programmeurs Haskell : je me demande ce que vaut Haskell en matière de performances pour les développeurs qui cherchent à écrire du code optimisé

  • Je m’intéresse en particulier aux performances en calcul numérique, notamment pour les opérations matricielles et l’usage du SIMD

• Un commentaire pour remercier du partage

• Il y a une coquille dans le tableau de la section "Creating prefix-free codes"

  • D devrait être 0010 (il est actuellement indiqué à tort comme 0110)
  • À part ça, c’était une excellente lecture

• Le codage arithmétique est meilleur sur presque tous les plans

  • Il peut être implémenté avec moins de RAM et moins de code
  • Il offre de meilleurs taux de compression et de décompression
  • Il est plus facile de mettre à jour dynamiquement la probabilité d’apparition d’autres symboles au fil du flux
  • Le codage de Huffman a été utilisé parce qu’il a été inventé plus tôt et que le codage arithmétique était sous brevet
  • Maintenant que les brevets ont expiré, il faudrait utiliser une meilleure conception