Créer un utilitaire de compression basé sur le code de Huffman en Haskell

 (lazamar.github.io)
1 points par GN⁺ 2024-07-06 | 1 commentaires | Partager sur WhatsApp
  • L’article montre, avec environ 150 lignes de Haskell, comment implémenter un compresseur Huffman capable d’encoder et de décoder des fichiers binaires arbitraires en mémoire constante.
  • Le code de Huffman attribue des séquences de bits courtes aux valeurs fréquentes et s’appuie sur la propriété de prefix-free code pour permettre au décodeur d’interpréter les bits sans ambiguïté.
  • L’implémentation construit un arbre à partir de FreqMap, HTree et CodeMap, puis génère progressivement le résultat grâce à l’évaluation paresseuse de concatMap et d’un décodeur récursif.
  • Les fichiers binaires sont manipulés via Data.ByteString.Char8, qui traite les octets comme des Char ; la sortie compressée commence par la table des fréquences, puis stocke le flux de bits avec un remplissage à l’octet.
  • Lors des tests, War and Peace passe de 3.2M à 1.9M, et le binaire ghcup de 106M descend à 84M, avec un maximum de mémoire résidente observé inférieur à 300KB.

Idée de base de la compression par code de Huffman

  • L’objectif est d’implémenter un utilitaire de compression de données en environ 150 lignes de Haskell à l’aide du Huffman coding.
  • Le code complet est publié dans un dépôt GitHub.
  • Le code de Huffman attribue une séquence de bits unique à chaque caractère ou valeur.
    • Les valeurs fréquentes utilisent des séquences de bits courtes.
    • Les valeurs rares utilisent des séquences de bits longues.
    • La compression vient du fait que les valeurs courantes sont représentées avec moins de bits que dans leur représentation d’origine.
  • Dans l’exemple aaab, si l’on pose a = 1 et b = 0, on obtient 1110.
    • C’est un exemple où une chaîne nécessitant 4 octets en UTF-8 est représentée sur un demi-octet.

Prefix-free code et arbre de Huffman

  • Pour que le décodage soit non ambigu, aucun mot de code ne doit être le préfixe d’un autre.
    • Par exemple, dans aaabc, si l’on assigne a = 1, b = 10, c = 01, alors 101 peut être ambigu entre ac et ba.
  • Un prefix-free code peut être représenté par un arbre binaire complet.
    • Toutes les valeurs sont placées sur les feuilles.
    • L’arête de gauche est étiquetée 1, celle de droite 0.
    • Le chemin de la racine jusqu’à une feuille devient le mot de code de cette valeur.
  • L’arbre de Huffman est construit en regroupant depuis le bas les valeurs les moins fréquentes.
    • On crée un nœud pour chaque caractère avec son poids, c’est-à-dire son nombre d’occurrences.
    • On regroupe en arbre les deux nœuds de plus petit poids.
    • Le poids du nouvel arbre est la somme des poids des deux nœuds.
    • On répète jusqu’à ce qu’il ne reste plus qu’un seul arbre.
  • Ce processus rapproche de la racine les valeurs les plus fréquentes, qui obtiennent ainsi des mots de code plus courts.

Structure de l’encodeur Haskell

  • Les principaux types de l’implémentation sont Bit, Code, FreqMap, CodeMap, Weight et HTree.
    • Bit vaut One ou Zero.
    • Code est [Bit].
    • FreqMap est un Map Char Int qui stocke le nombre d’occurrences par caractère.
    • CodeMap est un Map Char Code qui stocke le mot de code de chaque caractère.
    • HTree est soit Leaf Weight Char, soit Fork Weight HTree HTree.
  • HTree est rendu comparable sur la base du poids, ce qui simplifie le tri et l’insertion pendant la construction de l’arbre.
  • countFrequency calcule le nombre d’occurrences de chaque caractère dans une chaîne.
  • buildTree transforme le FreqMap en liste de feuilles, la trie, puis fusionne à répétition les deux plus petits nœuds pour construire l’arbre de Huffman.
  • buildCodes parcourt l’arbre en ajoutant One à gauche et Zero à droite afin de générer le mot de code de chaque caractère.
  • encode :: FreqMap -> String -> [Bit] construit l’arbre et la table de codes à partir du FreqMap, puis remplace chaque caractère de la chaîne d’entrée par son mot de code pour produire une liste de bits.

Traitement progressif grâce à l’évaluation paresseuse

  • La transformation clé de l’encodage est concatMap codeFor str.
    • Conceptuellement, on transforme [Char] en [[Bit]], puis on aplatit le tout en [Bit].
    • Grâce à l’évaluation paresseuse de Haskell, cela ne consiste pas à encoder toute l’entrée d’abord, puis à la concaténer ensuite.
  • Les petites listes sont aplaties de gauche à droite dans une grande liste de sortie.
    • La queue de la liste de sortie reste un thunk non encore évalué.
    • La partie suivante n’est calculée que lorsqu’elle est demandée.
  • Le décodeur génère lui aussi le résultat progressivement.
    • decode :: FreqMap -> [Bit] -> String se déplace à gauche ou à droite dans l’arbre en fonction des bits.
    • Quand il atteint une feuille, il émet le caractère puis repart de la racine.
    • Il répète jusqu’à ce que le nombre total de caractères décodés soit égal au poids de l’arbre de Huffman.
  • Le décodeur s’arrête non pas à la fin de la liste de bits en entrée, mais en fonction du nombre de caractères.
    • En effet, l’étape de sérialisation ajoute à la fin des bits de remplissage pour aligner sur l’octet.
  • Dans la fonction go, lorsqu’une feuille est atteinte, la tête de la liste est connue et la queue est fournie par un appel récursif, ce qui permet d’évaluer le résultat avant la fin de toute la récursion.

Traitement des fichiers binaires et sérialisation

  • Les données binaires peuvent être vues comme la répétition de l’un des 256 octets possibles.
  • Data.ByteString.Char8 permet de manipuler un ByteString avec des opérations sur Char, chaque Char étant tronqué à 8 bits.
    • Grâce à cette propriété, le codeur initialement pensé pour du texte peut être appliqué à des données binaires sans modification majeure.
  • Le fichier compressé commence par le FreqMap nécessaire au décodage, suivi du flux de bits encodé.
  • serializeFreqMap écrit la table des fréquences au format suivant.
    • La longueur de la map est stockée en Word8, en soustrayant 1 pour s’adapter à la plage représentable.
    • Chaque entrée stocke la clé en Word8 et la fréquence en entier 64 bits big-endian.
  • serialize utilise la monade Put du package binary pour générer un ByteString.
    • Les bits sont lus un à un pour remplir un octet.
    • Une fois 8 bits accumulés, ils sont écrits avec putWord8.
    • Le dernier octet est complété avec des Zero si nécessaire.

Désérialisation et stratégie en mémoire constante

  • deserializeFreqMap lit la table des fréquences sérialisée avec Data.Binary.Get.
    • Il lit d’abord la longueur, puis ajoute 1 pour retrouver le nombre réel d’entrées.
    • Il lit ensuite, pour chaque entrée, la clé Word8 et la fréquence 64 bits afin de reconstruire le FreqMap.
  • Le reste de l’entrée n’est pas traité avec Get : on récupère la partie du ByteString après l’offset, puis on la convertit en liste de bits.
  • deserialize renvoie (FreqMap, [Bit]), où [Bit] est une liste paresseuse qui n’est pas entièrement calculée immédiatement.
    • Il faut éviter de demander la longueur de cette liste, car cela forcerait son évaluation complète.
  • Si l’entrée entière n’est pas traitée via Get, c’est parce que le bind de la monade impose un ordre strict.
    • On se retrouverait alors avec une structure qui ne peut renvoyer la liste qu’une fois tout le traitement de l’entrée terminé.
  • La stratégie en mémoire constante consiste à n’évaluer que la petite portion suivante de l’entrée à chaque écriture de bits de sortie.
    • Une portion du ByteString est évaluée et le fragment de fichier correspondant est lu.
    • La sortie traitée est écrite dans le fichier.
    • Les fragments d’entrée et les listes de bits qui ne sont plus référencés peuvent être récupérés par le garbage collector.
  • Le FreqMap contient au maximum 256 entrées au niveau des octets, ce qui maintient un surcoût de taille constante.

CLI de compression et décompression de fichiers

  • compress lit le fichier d’entrée deux fois.
    • Le premier passage construit le FreqMap.
    • Le second encode les données à partir de ce FreqMap.
  • Si l’on ne lisait le fichier qu’une seule fois pour transmettre la même référence à encode, il faudrait conserver la référence à l’ensemble du fichier en mémoire même après la création de la table des fréquences.
  • La lecture en deux passes permet de libérer progressivement la mémoire traitée, aussi bien lors de la construction de la table des fréquences que pendant l’encodage.
  • decompress lit le fichier compressé, obtient FreqMap et liste de bits via deserialize, puis écrit dans un fichier le résultat de decode.
  • La CLI accepte les arguments suivants.
    • compress FILE FILE
    • decompress FILE FILE
  • Comme seuls les packages inclus avec GHC sont utilisés, on peut compiler avec ghc -O2 Main.hs -o main sans cabal.

Résultats d’exécution et utilisation mémoire

  • Lors d’un test sur le fichier texte War and Peace de Tolstoï, le résultat après compression puis décompression est identique selon diff.
    • Original WarAndPeace.txt : 3.2M
    • Fichier compressé : 1.9M
    • Fichier décompressé : 3.2M
    • La taille diminue d’environ 40 %.
  • La compression et la décompression fonctionnent aussi sur un fichier binaire plus volumineux, ghcup.
    • Original ghcup : 106M
    • Fichier compressé : 84M
    • Fichier décompressé : 106M
    • Le temps de compression est d’environ 15.173 secondes, et celui de décompression d’environ 14.555 secondes.
  • D’après +RTS -s, la taille maximale de resident set size pendant le traitement de ghcup reste inférieure à 300KB.
  • Les deux processus utilisent moins de 10MB de mémoire à l’exécution.
  • La répartition du temps est visible dans un profil séparé.

Pistes d’amélioration

  • L’objectif de cette implémentation était de produire un utilitaire de compression aussi simple et clair que possible ; pour améliorer l’efficacité, une implémentation plus complexe serait nécessaire.
  • Voici quelques pistes possibles.
    • Multithreading : décoder en parallèle des segments de fichier, mais comme on ne peut pas connaître les frontières des mots de code à une position arbitraire, il faudrait ajouter au début du fichier compressé une table des frontières de segments et de la taille décodée attendue.
    • Encodage en un seul passage : partir d’une table de fréquences initiale où tous les octets ont la fréquence 1, puis encoder chaque octet avant de mettre à jour la table lorsqu’il apparaît.
    • Canonical Huffman codes : au lieu de parcourir l’arbre en O(log n) au décodage, on pourrait utiliser les codes comme index dans un vecteur pour viser un accès en O(1) ; voir Canonical Huffman code.
    • Génération de codes plus rapide : dans un encodage en un seul passage, la construction du CodeMap devrait être bien plus rapide, et il existe des méthodes plus efficaces pour générer les mots de code sans construire l’arbre.
  • À terme, l’utilisation d’une approche par dictionnaire adaptatif comme LZ77, combinée aux codes de Huffman, permettrait d’implémenter gzip.

À lire aussi

1 commentaires

 
GN⁺ 2024-07-06
Avis sur Hacker News

  • Il existe pour cette tâche un algorithme en place basé sur des tableaux qui réduit l’allocation d’arbres et le suivi de pointeurs.
    Quand j’ai appris l’approche fondée sur les arbres à l’université, je ne savais pas qu’il existait une autre méthode, et je me demande si c’était aussi le cas d’autres personnes.
    La méthode avec arbre est intuitive et aide à comprendre, mais les situations où la compression compte le plus sont généralement celles où il y a beaucoup de données et où l’on veut que ça s’exécute vite ; manipuler le tout en place dans des tableaux peut donc être plus logique.
    In-Place Calculation of Minimum-Redundancy Codes, Moffat, Katajainen, 1995
    http://hjemmesider.diku.dk/~jyrki/Paper/WADS95.pdf

    • Plus généralement, On the Implementation of Minimum Redundancy Prefix Codes de Moffat et Turpin mérite aussi d’être consulté.
      Charles Bloom l’a fortement recommandé et y a ensuite ajouté des explications.
      https://cbloomrants.blogspot.com/2010/08/08-12-10-lost-huffm...
    • Comme cet algorithme est décrit sous forme d’organigramme dans la norme JPEG ITU T.81 (1992), il semble que les connaissances sur Huffman basé sur des tableaux étaient déjà, dans une certaine mesure, connues dans les années 80.
    • C’est mentionné à la fin de l’article, et laissé en exercice au lecteur.
    • La phrase « je me demande si c’était aussi le cas pour quelques-uns d’entre vous » sonne comme une compréhension de liste.

  • Dire que « pour éviter toute ambiguïté, aucun mot de code ne doit être le préfixe d’un autre mot de code » n’est pas strictement exact.
    Les codes dits à décodage unique ne sont pas ambigus, et forment un sur-ensemble des codes préfixes.
    Un exemple simple est un code obtenu en inversant un code préfixe. Avec l’exemple de l’article, cela donnerait a 1, b 00, c 10.
    Le code de a est un préfixe du code de c, mais si l’on traite la suite de codes en sens inverse, on peut toujours la décoder sans ambiguïté. Il serait intéressant de voir des codes à décodage unique qui ne soient ni des codes préfixes ni leur version inversée.

    • En composant un code préfixe et un code suffixe, on peut produire de tels codes sans qu’ils soient inutilement inefficaces.
      Si l’on prend A 0, B 01, C 11, puis a A 0, b BA 010, c BB 0101, d BC 0111, e C 11, on obtient {a=0,b=010,c=0101,d=0111,e=11}.
      On peut manifestement le décoder de façon unique : d’abord depuis la fin avec des règles comme 0->A, puis de nouveau depuis le début avec des règles comme A->a.
      En termes de longueurs, c’est identique au code préfixe optimal {a=0,b=110,c=1110,d=1111,e=10}, donc c’est l’un des codes optimaux pour la même distribution de probabilités.
      En même temps, à cause de a=0 et b=010, ce n’est ni un code préfixe ni un code suffixe. En fait, en général, le décodage progressif est impossible dans les deux sens : pour distinguer cee...ee? de bee...ee?, ou ?cc...cca de ?cc...ccb, il peut falloir une anticipation infinie même pour identifier un symbole.
      Je ne sais pas si composer un code préfixe optimal indépendamment et un code suffixe optimal indépendamment préserve toujours l’optimalité, mais dans les cas les plus simples auxquels j’ai pensé, hormis les codes dégénérés 1:1, cela fonctionnait bien.
    • C’est un problème plus intéressant qu’il n’y paraît. Pour commencer, comme réponse adversariale, on peut donner un exemple comme a 101, b 1.
      Mais c’est un mauvais code, puisqu’il est toujours préférable de prendre a=1, b=0.
      L’inégalité de Kraft indique quels ensembles de longueurs de code peuvent être rendus à décodage unique, et le codage de Huffman permet d’atteindre tous ces ensembles. Donc, si l’on fait du codage de symboles, il n’y a aucune raison d’utiliser un code non préfixe, sauf à passer à une autre méthode comme ANS ou le codage arithmétique.
      En revanche, je ne sais pas s’il existe un code à décodage unique qui ait le même ensemble de longueurs qu’un code de Huffman optimal, tout en n’étant ni un code préfixe ni son inverse, un code suffixe.
      Si j’y consacrais du temps, je regarderais https://en.wikipedia.org/wiki/Sardinas-Patterson_algorithm et j’essaierais soit de trouver un contre-exemple par force brute, soit de dégager une preuve à partir du fonctionnement de l’algorithme.
    • C’est un exemple bizarre, mais que penser de a 1, b 101 ?
      Ce n’est ni préfixe libre ni suffixe libre, mais chaque apparition de 0 correspond à l’apparition de b.
      Bien sûr, c’est manifestement inefficace ; au final, la question est donc de savoir s’il existe un code optimal qui ne soit ni préfixe libre ni suffixe libre.
      En cherchant, j’ai vu que https://blog.plover.com/CS/udcodes.html donne l’exemple d’un code à décodage unique a 0011, b 011, c 11, d 1110.
      La seule relation de préfixe est que c est un préfixe de d, donc il est « presque » préfixe libre. Si un message commence par 1, il semble qu’il suffise de trouver le premier 0 et de regarder si le nombre de 1 qui le précèdent est pair ou impair ; je comprends donc pourquoi il est à décodage unique.
      En revanche, mes connaissances en théorie du codage sont trop rouillées pour que je me souvienne comment montrer pour quelle distribution de probabilités il est optimal.
    • C’est intéressant, mais la raison pour laquelle on n’utilise généralement pas cela est probablement qu’il peut falloir lire une très longue suite de bits avant d’atteindre le bit qui lève l’ambiguïté.
      Par exemple, avec 100000000000000001, pour savoir si le premier code est a ou c, il faut lire tous les zéros jusqu’à l’endroit où ils s’arrêtent.

  • Je me demande s’il existe, parmi les tutoriels similaires qui construisent progressivement un programme Haskell comme cet article, des ressources couvrant des fonctionnalités plus avancées comme les transformateurs de monades ou les lentilles.

    • Je recommande le livre Haskell in Depth. Les transformateurs de monades sont traités au chapitre 6, et les lentilles aux chapitres 3 et 14.
      Il couvre aussi d’autres fonctionnalités avancées comme Template Haskell et la concurrence, ainsi qu’un chapitre sur la manipulation de bases de données SQL en Haskell.
    • https://github.com/turion/rhine-koans vaut le détour.
      C’est un tutoriel pour la bibliothèque FRP Rhine, avec de bons commentaires et tests.

  • Le cours de programmation fonctionnelle basé sur Scala de Coursera propose aussi un exercice de codage de Huffman assez similaire, avec un correcteur automatique, ce qui est pratique pour celles et ceux qui veulent s’y essayer
    https://www.coursera.org/learn/scala-functional-programming?...

  • La dernière fois que j’ai utilisé un code de Huffman, c’était pour le macroprogramme du processeur MICMAC, autrement dit pour exécuter du texte assembleur avec un minimum de microcycles et de micro-instructions
    Je suis parti de l’histogramme des macro-instructions exécutées et, si je me souviens bien, j’ai d’abord écrit un interpréteur en C pour compter combien de fois chaque instruction était exécutée
    Ensuite, j’ai créé un programme de microcode à décodage progressif implémentant toutes les macro-opérations ISA nécessaires. Il me semble que l’ISA de macro-instructions obtenue était orientée bit plutôt que byte
    Dans la réalité, cela aurait probablement été lent et peu pratique, mais l’intérêt du code de Huffman est qu’il permet d’ajuster la profondeur des préfixes en fonction de la distribution des valeurs, sans devoir créer un code biaisé d’un côté à cause d’un préfixe sur 1 bit
    De plus, le microprogramme était un modèle de processeur pipeline non superscalaire, il fallait donc aussi gérer la prédiction de branchement. En cas de mauvaise prédiction, des cycles étaient perdus à cause d’un arrêt du pipeline pendant que le bon branchement se propageait vers l’avant

  • https://rosettacode.org/wiki/Huffman_coding

  • Comme il va probablement y avoir des programmeurs Haskell ici, j’aimerais poser une question : aujourd’hui, à quel point Haskell est-il rapide quand il est utilisé par un programmeur qui se soucie de l’optimisation ?
    Je suis particulièrement curieux des performances sur des tâches qui bénéficient du SIMD et du calcul numérique, comme les opérations matricielles.

    • Les performances de Haskell peuvent rivaliser avec celles des langages système, mais il faut garder à l’esprit que son principal atout est la facilité d’abstraction.
      L’essentiel, c’est qu’il est facile d’assembler différentes parties en un programme cohérent et bien structuré. C’est important pour l’ensemble du programme, pas seulement pour des boucles très serrées.
      Haskell dispose d’un bon FFI, donc les parties qui nécessitent intrinsèquement une optimisation impérative peuvent descendre vers un langage sans garbage collection. Si l’on encapsule ces parties dans une bibliothèque avec de bons types, on peut exploiter ces performances natives depuis n’importe quel code Haskell dont les types correspondent.
      C’est ce que nous faisions chez Meta pour créer des applications Haskell hautes performances. Nous écrivions de grands programmes Haskell beaux et rapides, en y intégrant des composants C++ pour certaines parties spécialisées. 99 % du temps était consacré côté Haskell à composer le tout en une application plus utile.
    • Pour les tâches quotidiennes de backend, web et CLI, les performances de Haskell me conviennent. Mais quand j’écris du code centré sur les performances, je descends vers Rust.
      Cela dit, Haskell n’est pas spécialement lent. On peut prendre l’exemple d’un petit programme qui compte le nombre de bits à 1 dans un fichier.
      Compilé avec -msse4.2, il utilise correctement l’instruction matérielle popcount et traite un fichier d’entrée de 1 Go en 0m0,090s. En arrondissant au Mo, il utilise 0 de heap.
      Compilé sans -msse4.2, il prend 0m0,293s.
      Je n’ai pas testé le calcul matriciel moi-même, mais comme point de départ je regarderais repa, accelerate et massiv.
      https://hackage.haskell.org/package/repa
      https://hackage.haskell.org/package/accelerate
      https://hackage.haskell.org/package/massiv
    • J’ai rencontré Sam Derbyshire à ZuriHac, et il m’a dit que tout le gros travail d’architecture pour la prise en charge de SIMD était terminé.
      https://gitlab.haskell.org/ghc/ghc/-/issues/7741
      Cela pourrait arriver dans GHC 9.12. Cela dit, cela ne vise que les vecteurs 128 bits et, sauf contributions d’autres personnes, ce sera probablement surtout axé sur les opérations en virgule flottante.
      Le patch est ici :
      https://gitlab.haskell.org/ghc/ghc/-/merge_requests/12860
    • De façon réaliste, quel que soit le langage, C compris, le code optimisé par le compilateur ne peut pas être aussi rapide que du code optimisé à la main dans des bibliothèques comme BLAS.
      À un certain niveau, le choix du langage hôte n’a pas beaucoup d’importance. Si l’on prend vraiment la performance au sérieux, on finira de toute façon par déléguer les calculs à l’extérieur.
      C’est aussi pour cela que le code d’IA, qui représente probablement l’un des plus gros consommateurs de ressources de calcul au monde, peut être écrit en Python en dehors des bibliothèques de calcul bas niveau.
      Pour répondre directement : le compilateur GHC est très bon. Le code haut niveau fonctionne plutôt bien, et dans la plupart des applications réalistes, le goulot d’étranglement de performance n’est pas une question d’opérations scalaires contre SIMD, mais une question d’architecture. La « qualité asymptotique architecturale » de Haskell est assez avantageuse.
      Je crois que GHC a, ou est en train d’acquérir, une prise en charge de SIMD, mais je ne me concentrerais pas là-dessus pour évaluer les performances.
      Je n’écrirais pas moi-même un algorithme de multiplication matricielle en Haskell, mais si je prenais vraiment la vitesse au sérieux, je ne l’écrirais pas non plus moi-même en Rust ou en C.
      On considère souvent le calcul numérique comme un indicateur de performance, mais en pratique très peu de gens y ont leur goulot d’étranglement ; et si c’est le cas, le choix du langage haut niveau compte assez peu.
    • Haskell brille vraiment quand on veut écrire du code déclaratif de haut niveau.
      Les performances de ce style sont généralement suffisantes pour des tâches CLI ou des backends web. Il existe aussi des outils pour écrire du code bas niveau assez rapide, mais ils sont un peu rugueux ; si c’est tout ce que l’on veut faire, ce n’est probablement pas le meilleur outil.
      En revanche, quand on a quelques hotspots bien localisés à optimiser, c’est plutôt correct.
      Les outils de profiling CPU sont bons, donc trouver et optimiser les hotspots CPU est relativement agréable. En revanche, traquer les fuites mémoire étranges, plus susceptibles d’apparaître à cause de l’évaluation paresseuse, peut être très frustrant.
      Si l’on regarde les résultats du benchmarks game, les implémentations Haskell les plus rapides sont en général 2 à 5 fois plus lentes que les versions C les plus rapides, et elles sont écrites dans un style très impératif.
      https://benchmarksgame-team.pages.debian.net/benchmarksgame/...

  • Il semble y avoir une coquille dans le tableau de la section « Creating prefix-free codes ». D devrait être 0010, pas 0110.

    • J’ai donc passé un bon moment à me demander comment 0110 pouvait ne pas être ambigu, mais maintenant je comprends.

  • Je me demande ce qu’il y a sur le t-shirt de la femme dans l’image.
    Lien direct : https://lazamar.github.io/images/data-compressor.svg