Compression de texte : le codage de Huffman

Télécharger et extraire l'archive zip qui contient un dossier codage_huffman avec :

un fichier partie1.py qui contient ce qu'on a déjà fait sur capytale + la fonction de décodage
un fichier partie2.py qu'on va compléter dans ce TP avec les autres fonctions nécessaires
un fichier binaryfiles.py qui permettra de lire et écrire des fichiers en binaire
petitprince.txt, le texte complet du livre Le Petit Prince qu'on va compresser
exemple_encode.py et exemple_decode.py dans lesquels on fera la compression et décompression de ce livre

Ouvrez tout le dossier dans VSCodium.

Complétez dans partie2.py la fonction calcule_frequence qui à partir d'un texte renvoie le dictionnaire qui à chaque caractère associe le nombre de fois où il apparaît.

Solution

Écrire cette fonction pourrait être un exercice d'épreuve pratique au bac.

def calcule_frequence(message : str) -> dict:
    frequence = {}
    for caractere in message:
        if caractere in frequence:
            frequence[caractere] = frequence[caractere] + 1 # ou bien += 1
        else:
            frequence[caractere] = 1
    return frequence

Puis dans exemple_encode.py, appelez cette fonction sur le texte du petit prince et affichez le dictionnaire obtenu pour vérifier si la fonction marche.
Pour l'algorithme de Huffman on a besoin de fusionner des arbres binaires. Écrire dans partie2.py la fonction fusionne qui prend deux arbres en paramètres, en crée un nouveau qui les fusionne et le renvoie.

Pour faire un petit test, créez deux arbres avec un seul caractère dans a1 et a2, appelez la fonction pour obtenir la fusion dans a3, et affichez a3 à l'aide de treeviz(a3).view().

Une fois que ça fonctionne, supprimez ce test du fichier.

Ajoutez dans partie2.py la fonction extrait_min suivante :

def extrait_min(liste_arbres : list):
    """
    liste_arbres est une liste de paires (valeur, arbre)
    cette fonction enlève l'élément de la liste avec la plus petite valeur
    et renvoie cet élément
    """
    min_val = liste_arbres[0][0]
    min_index = 0
    for i in range(1, len(liste_arbres)):
        val = liste_arbres[i][0]
        if val < min_val:
            min_val = val
            min_index = i
    return liste_arbres.pop(min_index)

Complétez la fonction fabrique_huffman en utilisant la docstring et les fonctions fusionne et extrait_min qu'on vient de créer.

Testez-la dans exemple_encode.py avec le dictionnaire de frequences obtenu à la partie 1.

Affichez l'arbre de codage obtenu avec treeviz(votre_arbre).view().

Quels sont les caractères les plus en haut de l'arbre ? Sur combien de bits sont-ils codés ?

Et ceux les plus en bas de l'arbre ? Vérifiez que ça vous semble cohérent.
Dans exemple_encode.py toujours, créer le dictionnaire de codage associé à l'arbre grâce à la fonction de partie1.py faite la fois précédente.

Puis coder le texte avec ce dictionnaire.

Affichez le résultat avec print. Sur combien de bits est le texte ?

Comparez avec le résultat de la commande du -b petitprince.txt dans le terminal qui donne la taille en octet du fichier.
Décoder le texte avec la fonction de décodage présente dans partie1.py.

Vérifiez que vous retombez bien sur le même texte que celui du fichier de départ, au caractère près.
Pour l'instant on a écrit des chaînes de caractères avec des "0" et des "1", ce n'est pas la même chose que d'écrire directement du binaire car chaque caractère est stocké en ASCII et prend en fait 8 bits en mémoire !

Ouvrez le fichier binaryfiles.py : il y a une partie if __name__ == '__main__' qui n'est exécutée que si le fichier est lancé directement, mais pas si on l'importe avec import binaryfiles ou from binaryfiles import *. Cela est une technique courante pour écrire des tests ou exemples qui n'ont pas vocation à être exécutés à chaque fois.

À cet endroit, utilisez la fonction write_to_file pour écrire dans un fichier ("test.bin" par exemple) "1011111010". Vérifiez dans le terminal avec du -b test.bin la taille en octet du fichier, et affichez son contenu binaire avec xxd -b test.bin. Notre suite binaire était de taille 10, donc devrait occuper 1 octet + deux bits. Que s'est-il passé dans le résultat que vous voyez ?
Dans exemple_encode.py, utilisez la même fonction pour écrire la version binaire du petit prince compressé dans un fichier.

Que manque-t-il pour pouvoir le décoder à partir de ce fichier binaire ?

Solution

Il manque l'arbre de codage qu'on a utilisé. Le module pickle de python permet d'écrire et relire en binaire n'importe quelle valeur python, vous pouvez donc le stocker dans un autre fichier avec pickle.dump(arbre_code, open("arbre.bin", "wb"))
Dans exemple_decode.py, récupérez le texte codé depuis le fichier à l'aide de la fonction read_from_file et l'arbre de codage avec arbre_code = pickle.load(open("arbre.bin", "rb")). Utilisez la fonction decode pour le décoder, et affichez-le simplement avec print.

Est-ce que ça fonctionne ?
Dans le terminal dans le bon dossier, vous pouvez lancer la commande linux du -b * qui vous donnera la taille de tous les fichiers en octets. De combien de pourcents a-t-on réduit le fichier de départ ? (il faut compter à l'arrivée la taille de l'arbre et du fichier avec le texte compressé)
Dans le terminal, utilisez zip petitprince.zip petitprince.txt pour compresser le texte avec l'algorithme ZIP. Comparez les tailles obtenues avec ce qu'on a fait.