"Mettre en lumière un ou plusieurs projets autour des notions étudiées dans les TDs et en CM", donc concrètement on fait ce qu'on veut tant qu'il y a un peu de récursivité, d'arbres, de MinMax ou de postfixe.
Cela fait un moment que je comptais m'intéresser aux algorithmes de compression et de chiffrage de fichier, donc je pourrais commencer à travailler sur le codage de Huffman.
Le principe est pas si compliqué à comprendre : pour compresser un texte, on donne une valeur binaire plus courte pour les lettres les plus fréquentes.
Même si les lettres moins fréquentes on un code plus long qu'à l'origine, vu qu'il y en a moins que de lettres au code plus court on a économisé de la place au final.
Sauf que trier les lettres par nombre d'occurences décroissant et assigner une valeur correspondante, honnêtement c'est pas rigolo.
Les professionnels de la compression (autrement dit monsieur Huffman, sans qui WinRar serait peut-être gratuit mais probablement moins efficace) ont trouvé plus pertinent de construire un arbre contenant toutes les lettres du texte, et de faire en sorte que les plus fréquentes soient plus proches de la racine.
Comme ça, quand on parcours l'arbre à partir de la racine jusqu'à la lettre qu'on veut coder en notant un 1 quand on prend la branche de gauche et un 0 pour la branche de droite, on finis avec un code binaire plus court pour les lettres que l'on retrouve souvent.
En plus, il se trouve que cette méthode est sans préfixe, ça veut dire qu'aucun code binaire d'une lettre est le préfixe d'un autre code, mais ça je le savais pas vu que j'avais lu la feuille du TD en diagonale. C'est surtout à cause de ça que c'est parti en cacahuète.
On a même droit à une animation en ligne qui affiche le procédé de construction de l'arbre.
Vu comme ça, ça a l'air encore pas trop dur à faire sur le papier :
Donc "sur le papier" c'est pas dur. C'est même encore plus intéressant d'étendre ce principe à des octets plutôt que des lettres, comme ça on pourrait compresser tout et n'importe quoi. Mais en faire un programme, ça risque d'être différent... déjà comment on stocke un arbre dans un langage de programmation?
D'ailleurs, quel langage?
Les exemples des TDs sont données en VBA, mais est-ce qu'on a vraiment besoin d'Excel?
Ça peut être sympa pour afficher l'arbre, mais sans plus, et je compte pas l'afficher de toute façon (spoiler : en fait je l'ai fait parce que sinon c'est relou à déboguer).
Du C alors? Certainement pas, j'ai pas envie de devoir réinventer la roue à chaque ligne, même pour des actions basiques.
C'est peut-être performant, mais si j'y arrive ce sera illisible, et je suis même pas sûr d'y arriver.
Il me faut un langage pas trop dur à écrire et facile à lire, et qui propose plein de méthode pour manier des lettre, des octets et des bits, quitte à ce que ce soit un peu moins performant.
Autrement dit du Python quoi.
Bon, on a notre langage, mais ça nous fait pas un programme ça. Avant même de commencer à construire un arbre, comment on va le stocker dans une variable?
Il faudrait une sorte de liste, mais où on puisse référer chaque feuille par son nom plutôt que par un indice numérique.
Ça ça existe en Python, ça s'appelle un dictionnaire.
Et leur nom alors? Pour les feuilles de l'arbre ça peut correspondre à l'octet qu'elles représentent, mais les noeuds intermédiaires?
Là j'ai eu une idée extraordinaire qui m'a permis de naviguer dans l'arbre bien plus facilement plus tard : le nom des noeuds intermédiaires serait la concaténation des noms des enfants.
Il se trouve que le type de variable byte fonctionne à peu près comme un string, on peut les concaténer dans une seule variable, et même rechercher dedans.
Enfin, dans chaque noeud on va stocker quoi?
Il va falloir au moins le nombre d'occurences et les deux noeuds enfants (celui de gauche et celui de droite).
J'ai choisi de stocker aussi le rang du noeud, techniquement c'est possible de le retrouver en le calculant mais ça pourrait vraiment ralentir le programme de calculer des rangs sans arrêt, vu qu'on va en avoir besoin souvent.
Au final ça ressemble un peu à une liste chainée, sauf que chaque noeud contient deux adresses (ou aucune si c'est une feuille en bout de branche).
Ça y est, j'ai un plan. On ouvre un fichier en mode octet, on en calcule un tableau du nombre d'occurence de chaque octet (pour un fichier binaire, on se rapproche donc des 256 valeurs possibles), puis on en fait un arbre.
Après on calcule les 2 minimums du rang 1, et on créée une nouvelle feuille dont les enfants sont ces 2 minimums, sans oublier d'incrémenter le rang de tous les enfants de ces derniers.
Tiens ça c'est une bonne occasion de faire un peu de récursivité.
Une petite fonction pour incrémenter le rang de tous les enfants à partir d'un noeud, rien de plus simple : on incrémente le rang du noeud en question, puis celui de l'enfant de droite, puis celui de l'enfant de gauche (ah ces gosses...). J'en ai même profité pour faire une seconde fonction du même style, mais qui compte juste le nombre de noeuds. Bah oui, en cas d'égalité dans le calcul des deux minimums il faut prendre l'arbre avec le moins de noeuds, donc une petite fonction sera nécessaire.
Bon c'est sympa de compresser des fichiers (enfin, essayer...) mais faudrait pouvoir les décompresser aussi.
Un des problèmes avec Huffman (à part que c'est un 'ricain) c'est que pour pouvoir décompresser des données, il faut connaitre la structure de l'arbre qui a servi à les compresser.
Pour faire simple, il faudrait transmettre l'arbre au programme de décompression, d'une manière où d'une autre.
Sauf qu'on a pas besoin de tout l'arbre en fait, si on transmet juste un tableau de correspondance entre un octet et son codage de Huffman, le programme pourra le faire dans l'autre sens.
Ce tableau sera une table de traduction, une pierre de rosette mais en un peu moins bien.
Mais comment on va le transmette à un autre programme?
On peut évidemment passer par un fichier, mais un dictionnaire Python c'est pas un fichier.
On peut le convertir en texte et l'écrire dans un fichier texte, mais reconvertir un texte en objet c'est pas une bonne idée.
Quand on convertit un objet de type byte en texte, si l'octet peut être représenté en caractère ASCII alors il l'est, donc il va y avoir un paquet de caractères aléatoires qui se baladent dans le fichier.
Et avec ça, il y a 11 chances sur 10 que ça marche pas.
J'ai cherché des moyens de transmettres des objets Python par des fichiers, et j'ai trouvé le module JSON, qui permet d'écrire des fichiers... JSON.
Sauf que, comme de par hasard, ce module marche pas quand on essaye de transmettre des bytes, donc va falloir trouver autre chose.
Un autre module est assez populaire pour ça, le module Pickle qui permet de sérialiser (convertir à peu près n'importe quoi en octets et inversement) et écrire dans un fichier (même si ça on sait faire).
La grosse différence avec le JSON c'est que le fichier sera en binaire, et donc illisible par les autres moyens que Python. Mais je trouve que ça fait classe.
Par contre, quand il sera désérialisé ça peut poser problème.
Si ce dernier contient du code mal intentionné injecté par quelqu'un qui m'aime pas trop (je sais pas, un prof énervé de la basse qualité de mon compte-rendu...), ce code sera exécuté et pourra faire des trucs malhonnêtes.
Ce genre de failles de sécurité s'appelle "Arbitrary Code Execution", et même si ça peut faire des trucs amusants (j'ai entendu parler de développeurs qui ont utilisé ça pour faire un Pong dans Super Mario World), quand on est le dev du programme original on est sensé boucher les failles de sécurité.
Bon en vrai j'ai juste vérifié si le fichier sortait bien un dictionnaire, on est pas là pour coder un Fort Knox virtuel.
Et si on codait du Huffman (enfin)?
À ce niveau là, il reste plus qu'à parcourir l'arbre comme la méthode donnée au début.
Et tant qu'à faire, j'ai même passé une 3ème couche de récursivité avec cette fonction de codage, car l'action de "écrire un 1 (ou un 0) puis prendre à gauche (ou à droite)" peut se répéter de manière récursive jusqu'à trouver l'octet qu'on cherchait.
Ensuite, plus qu'à écrire chaque octet codé dans un nouveau fichier, et on est bon.
Du moins j'y ai crû, jusqu'à ce que je remarque que mon fichier """compressé""" est en fait PLUS GROS que mon fichier original.
J'ai d'abord crû que mon arbre était foireux, sauf que vérifier qu'une liste contenant 2 fois chaque octet possible mais pas dans l'ordre est correcte c'était pas possible.
Un import tkinter as tk plus tard, je me suis lançé dans un affichage rapide mais un peu plus graphique de l'arbre.
J'ai même fait une navigation à la souris et un zoom, vu que la quantité d'information à afficher est quand-même assez imposante.
Un petit bémol est que Canvas.scale() fonctionne pas sur le texte, donc pour faire un zoom un peu plus correct il faudrait calculer la taille du texte en fonction du grossisement.
Il est aussi possible que le zoom décale un peu la zone atteignable par la caméra, mais de toute façon cet affichage était juste conçu pour tester l'arbre.
Et au final l'arbre était correct.
J'ai fini par comprendre que Python écrit les fichiers binaire octet par octet, donc si on écrit un nombre de bits non multiple de 8, il va boucher automatiquement le dernier octet avec des 0.
Vu que mon rang maximal pour un arbre d'un fichier binaire se rapprochera de 9, il y a un peu moins d'un octet sur 2 constitué de zéros inutiles, donc on va se rapprocher du double de la taille originale.
Là j'ai un peu paniqué, mais c'est de ma faute. Je savais que je devais m'affranchir de l'alignement des octets, donc j'ai trouvé un module tout fait qui sert exactement au maniement de chaine de bits : Bitstring.
Seulement j'avais oublié que le codage de Huffman était sans préfixe, donc j'ai eu peur que sans le repère des octets je ne puisse plus reséparer le fichiers compressé en octets.
Je me suis donc mis en quête d'un codage qui puisse prendre du binaire ou n'importe quelle représentation d'un nombre, et en sortir un code qui ne présente aucun schéma du style 11 sauf entre les octets codés...
Attendez, est-ce que ce serait pas exactement du codage de Fibonacci?
Donc oui, je me suis embêté à réencoder du Huffman en Fibonacci, mais ça avait l'air cool sur le moment.
J'ai commencé par faire mes deux fonctions, une pour coder, une pour décoder, toutes deux ayant besoin de la suite de Fibonacci évidemment.
Le TD sur le codage de Fibonacci proposait une version récursive du calcul de la suite, mais pour des raisons de performance j'ai préféré la faire un peu plus classique.
Faut avouer que Python rend ça extrèmement simple à faire aussi.
Il se trouve que la fonction de codage utilise toujours la suite dans l'ordre décroissant donc je l'ai juste inversée dès le début, encore une fois pour tenter de gagner du temps d'exécution.
La fonction de décodage l'utilise dans le sens croissant, donc la suite n'est jamais inversée dans le programme de décompression.
Une fois ces fonctions faites, il ne restait plus qu'à ajouter la case "Fibonacci" entre Huffman et le fichier compressé (on reconvertis le codage binaire de Huffman en entier décimal).
En gros, chaque octet codé terminera toujours par un 1, et il n'y a jamais deux 1 d'affilée.
Si on rajoute un 1 entre chaque octet, les seules occurences de 11 seront entre chaque octet (même si le premier 1 appartiendra à l'octet précédent).
Le seul petit détail qui m'a posé pas mal de problèmes lors de la décompression, c'est que quand on code 0 par Fibonacci, on obtient... 0.
Ça parait totalement normal mais ça casse tout, car 0 ne termine pas par 1 donc si on rajoute un 1 après, il n'y aura pas de 11.
La solution que j'ai trouvé est d'ajouter 1 à l'entier que l'on code par Fibonacci, et de retirer 1 à la décompression.
Je sais, ça vole pas haut, mais faut savoir rester simple (et c'est peut-être ce que j'aurais dû me dire avant de commencer le codage de Fibonacci).
Et la décompression dans tout ça, bah c'est pas très compliqué.
Je commence par importer la table de traduction, et j'en inverse le sens.
C'est-à-dire qu'au lieu de lui donner un octet et elle renvoie son codage de Huffman, je peux lui donner un codage et elle renverra un octet.
Plus qu'à gérer le décodage de Fibonacci, et encore une fois il reste plus grand chose à faire.
J'utilise ici un BitStream, qui permet d'utiliser une suite de bits de la même façon qu'un fichier, à la manière d'un generator.
Je me contente de lire la série de bits de la position de lecture jusqu'à la prochaine occurence de 11, et d'ajouter ça à une liste en retirant le dernier 1 qui correspond à celui qu'on a ajouté à la compression.
La position de lecture sera automatiquement incrémentée, donc je peux répéter ça jusqu'à ce que je rencontre une exception qui indique qu'aucune occurence n'a été trouvée.
J'atteins pas forcément la fin de la liste de bits car la liste d'origine n'avait pas forcément une longeur multiple de 8, et il reste donc peut-être quelques 0s à la fin qui ne font pas réellement partie des données.
Ne restait alors qu'un dernier ennemi, un de ceux que l'on sait présent, mais on attend la toute fin pour réaliser son envergure. Je parle évidemment du temps d'exécution.
Je savais très bien que le Python n'était pas particulièrement rapide, surtout comparé au C, mais quand il a fallu plus d'une heure pour décompresser un fichier de 1 641 kilo-octets, j'ai vite compris qu'un peu plus d'optimisation était nécessaire.
Malheureusement je n'ai pas pu y faire grand-chose.
J'ai essayé d'exploiter au mieux les possibilités des modules utilisés, mais je n'ai jamais atteint le niveau de performance que j'espérait, même si j'ai quand-même bien descendu à moins de 10 minutes pour que ce soit utilisable pour des petits fichiers.
J'ai par exemple essayé les méthodes BitString.findall() et BitString.split(), qui renvoient les emplacement de toutes les occurences d'un schéma et toutes les suites de bits commençant par un schéma, respectivement.
Le problème, c'est qu'elles renvoient un generator ce qui rend le programme plus dur à manier, notamment la longeur d'un générateur est absolument inefficace à calculer.
Au final c'est encore lent mais gérable, et au moins le fichier compressé puis décompressé est identique au fichier original.
L'avantage, c'est que ça marche sur n'importe quel fichier binaire, donc absolument n'importe lequel.
L'inconvénient c'est que des fois le fichier compressé est plus gros que le fichier original... ça doit probablement venir du codage de Fibonacci.
Mais je peux pas dire que je l'ai pas cherché.
Note : j'ai utilisé Python 3.8.7 64 bit sur Windows pendant le développement, et je n'ai pas fait du tout de test sur d'autres versions et systèmes.
