Bonjour, je n'arrive pas à coder ma fonction de décodage avec la technique de Huffman, mon code ressemble à cela :

from huffman_tree import *

"""
pour créer un arbre Huffman utiliser la fonction :
arbre1 = create_huffman_tree(dico) # dico est dictionnaire représentant la table de fréquences d'un texte ou fichier  

les méthodes de la classe HuffmanTree utilisées pour ce projet sont :
getSymbol() # return le symbole d'une feuille de l'arbre lorsqu'on est sur une feuille 
getLeft()   # return arbre fils gauche
getRight()  # return arbre fils droite   
"""

#*****************************************************************************
# Fonction table_frequence() : Construction d'une table de fréquences
# Entrée: un texte
# Sortie: un dictionnaire qui associe chaque symbole présent à sa fréquence
#*****************************************************************************
def table_frequences(texte):
    dico={}
    for k in texte:
        if (k in dico)==False:
            dico[k]=1
        else:
            dico[k]=dico[k]+1
    dico=sorted(dico.items(),reverse=True, key=lambda t:t[1])
    dicoTrie={}
    for k,v in dico:
        dicoTrie[k]=v
    return dicoTrie

dico=table_frequences("abracadabra")
print(dico)

arbre1=create_huffman_tree(dico)
print(arbre1)

#********************************************************************************************
# Fonction creerTableHuffman() : produit une table de codage Huffman des symboles  correspondant aux feuilles de 
# l'arbre binaire fourni. La méthode ou algorithme employé est le parcourt récursif prefixe d'un arbre binaire
# Entrée: un arbre binaire portant des symboles aux feuilles, table des codes vide et un mot binaire vide pour 
#               les besoins de traitement récursif
# Sortie: un dictionnaire qui associe à chaque valeur de feuille le code correspondant (mot binaire=chaine 
#             de caractères composée des 0 et 1)
#********************************************************************************************

def creerTableHuffman(arbre,tabCode={},motBinaire=""):
    if arbre.isLeaf():
        #print(arbre.getSymbol(),"--> ",bits)
        tabCode[arbre.getSymbol()] = motBinaire
        motBinaire = ''   #pour réinitialiser le mot binaire       
    if not arbre.isLeaf():
        creerTableHuffman(arbre.getLeft(),tabCode,motBinaire+'0')
        creerTableHuffman(arbre.getRight(),tabCode,motBinaire+'1')
    return tabCode

print(creerTableHuffman(arbre1,{},""))

def coderHuffman(texte):
    table=creerTableHuffman(arbre1)
    texteCode=""
    for lettre in texte:
        texteCode=texteCode+table[lettre]
    return texteCode

print(coderHuffman("abracadabra"))
txtc=coderHuffman("abracadabra")

def decoderHuffman(arbre,texteCode,texteDecode=[]):
    for k in texteCode:
        if arbre.isLeaf():
            texteDecode.append(arbre.getSymbol())
        if not arbre.isLeaf():
            if k=='0':
                decoderHuffman(arbre.getLeft(),texteCode[1:],texteDecode)
            else:
                decoderHuffman(arbre.getRight(),texteCode[1:],texteDecode)
    return texteDecode        
        
print(decoderHuffman(arbre1,txtc))

et mon prof nous a donné ce fichier annexe "huffman_tree.py" pour la gestion de l'arbre

'''
Binary tree implementation that can be used as a Huffman tree.

@author FIL - IEEA - Univ. Lille (août 2015)
'''

import os

class HuffmanTree:
    '''
    Manages Huffman trees
    '''
    
    left = None
    right = None
    occurrences = 0
    symbol = None

    def __init__(self, symbol=None, occurrences=None, left=None, right=None):
        """
        Creates a Huffman tree consisting of either:
        - one leaf (in that case `symbol` and `occurrences` must be provided)
        - a node with two subtrees.

        :param symbol: The symbol to store in the leaf
        :type symbol: str
        :param occurrences: The number of occurrences of the given symbol
        :type occurrences: int
        :param left: The left subtree
        :type left: huffman_tree.HuffmanTree
        :param right: The right subtree
        :type right: huffman_tree.HuffmanTree
        :UC: Either symbol and occurrences are given, or left and right.
        The number of occurrences must be positive.
        
        Example:
        >>> HuffmanTree('a', 1)
        ▮ 'a':1
        >>> HuffmanTree(left = HuffmanTree('a', 1), right = HuffmanTree('b', 1)) # doctest: +NORMALIZE_WHITESPACE
        /--▮ 'b':1
        ◯ 'a, b':2
        \--▮ 'a':1
        <BLANKLINE>
        """
        if symbol is None:
            assert (occurrences is None), "The symbol is missing"
            assert (left is not None and right is not None), "Both subtrees must be provided"
            self.left = left
            self.right = right
            self.occurrences = left.occurrences + right.occurrences
            self.symbol = ', '.join([str(left.symbol), str(right.symbol)])
        else:
            assert (occurrences is not None), "The symbol's number of occurrences must be given"
            assert (left is None and right is None), "The subtrees must not be given with the symbol"
            self.symbol = symbol
            self.occurrences = occurrences

    def children(self, left, right):
        self.left = left
        self.right = right

    def isLeaf(self):
        return self.left is None

    def __repr__(self):
        return self.huffman_representation()

    def __lt__(self, other):
        return self.occurrences < other.occurrences

    def __eq__(self, other):
        return self.occurrences == other.occurrences
    
    def huffman_representation(self, path=''):
        representation = ''
        if not self.isLeaf():
            representation += self.right.huffman_representation(path+'1')

        for i in range(len(path)-1):
            if path[i] == path[i+1]:
                representation += 3 * ' '
            else:
                representation += '|  '
        if len(path) >= 1:
            if path[-1] == '1':
                representation += '/--'
            else:
                representation += '\--'
                
        representation += ('◯' if not self.isLeaf() else '▮') + ' '
        if self.symbol is not None:
            representation += repr(self.symbol)
        if self.occurrences is not None:
            representation += ':{}'.format(self.occurrences)
        if not self.isLeaf() or len(path) > 0:
            representation += os.linesep
        
        if not self.isLeaf():
            representation += self.left.huffman_representation(path+'0')
        return representation
        
    #************************************************************************
    #☺    test ballouki
    #************************************************************************
    def isEmpty(self):
        '''Teste la vacuité de l'arbre'''
        return False
    
    def getSymbol(self):
        '''Donne la valeur du symbol à la racine'''
        #assert(self.isEmpty()==False)
        return self.symbol
    
    def getOccurrences(self):
        '''Donne la valeur de l'occurence à la racine'''
        #assert(self.isEmpty()==False)
        return self.occurrences
    
    def getLeft(self):
        '''Donne le sous-arbre gauche'''
        assert(self.isEmpty()==False)
        return self.left
    
    def getRight(self):
        '''Donne le sous-arbre droit'''
        assert(self.isEmpty()==False)
        return self.right
    




"""
Les fonctions pour créer des arbres Huffman à partir d'un dictionnaire de symbols et d'occurences
"""
def create_forest(occurrences):
    '''
    Create the initial list of Huffman trees based on the dictionary of
    symbols given in parameter.
    
    :param occurrences: Number of occurrences of each symbol.
    :type occurrences: dict
    :return: A list sorted in ascending order on the number of occurrences\
    and on the symbols of Huffman trees of all symbols provided in\
    `occurrences`.
    :Examples: 

    >>> create_forest({'a': 4, 'c': 2, 'b': 1})
    [▮ 'b':1, ▮ 'c':2, ▮ 'a':4]
    >>> create_forest({'e': 1, 'f': 1, 'g': 1, 'h': 1, 'a':2})
    [▮ 'e':1, ▮ 'f':1, ▮ 'g':1, ▮ 'h':1, ▮ 'a':2]
    '''
    sorted_occs = sorted(occurrences.items(), key=lambda item: (item[1], item[0]))
    forest = [HuffmanTree(leaf[0], leaf[1]) for leaf in sorted_occs]
    return forest

def pop_least_element(list1, list2):
    '''
    Get and remove the lowest element from two lists sorted in ascending order.

    :param list1: First list sorted in ascending order
    :type list1: list
    :param list2: Second list sorted in ascending order
    :type list2: list
    :return: The lowest element among the two lists
    :UC: The two lists are sorted in ascending order and there is at least\
    one element among the two lists.
    :Examples:

    >>> pop_least_element([1], [2])
    1
    >>> pop_least_element([2], [1])
    1
    >>> pop_least_element([], [1])
    1
    >>> pop_least_element( [1], [])
    1
    '''
    assert(len(list1) + len(list2) >= 1)
    if len(list1) == 0:
        return list2.pop(0)
    if len(list2) == 0:
        return list1.pop(0)
    if list2[0] < list1[0]:
        return list2.pop(0)
    return list1.pop(0)

def create_huffman_tree(occurrences):
    '''
    Return a Huffman tree of the symbols given in `occurrences`.
    
    :param occurrences: Number of occurrences of each symbol.
    :type occurrences: dict
    :return: Return a single Huffman tree (obtained with Huffman algorithm)\
    of the symbols in `occurrences`.
    :rtype: huffman_tree.HuffmanTre
    :Examples:
    
    >>> create_huffman_tree({'a': 1, 'b': 1, 'c': 2}) # doctest: +NORMALIZE_WHITESPACE
       /--▮ 'b':1
    /--◯ 'a, b':2
    |  \--▮ 'a':1
    ◯ 'c, a, b':4
    \--▮ 'c':2
    <BLANKLINE>
    >>> create_huffman_tree({'a': 4, 'b': 1, 'c': 2}) # doctest: +NORMALIZE_WHITESPACE
    /--▮ 'a':4
    ◯ 'b, c, a':7
    |  /--▮ 'c':2
    \--◯ 'b, c':3
       \--▮ 'b':1
    <BLANKLINE>
    >>> create_huffman_tree({97: 4, 98: 1, 99: 2}) # doctest: +NORMALIZE_WHITESPACE
    /--▮ 97:4
    ◯ '98, 99, 97':7
    |  /--▮ 99:2
    \--◯ '98, 99':3
       \--▮ 98:1
    <BLANKLINE>
    '''
    symbol_list = create_forest(occurrences)
    tree_list = []

    while len(tree_list) + len(symbol_list) != 1:
        (elem1, elem2) = (pop_least_element(symbol_list, tree_list),\
                          pop_least_element(symbol_list, tree_list))
        new_tree = HuffmanTree(left = elem1, right=elem2)
        tree_list.append(new_tree)

    if len(tree_list) == 1:
        return tree_list[0]
    return symbol_list[0]

Voilà si quelqu'un arrive à comprendre pourquoi ma fonction decoderHuffman ne marche pas je suis preneuse

Ça fait beaucoup de code à vérifier (je suppose que le code du prof est correct ...)
Essaies avec des exemples simples. Je pense qu'il y en a dans ce lien:
https://fr.wikipedia.org/wiki/Codage_de_Huffman

-
Edité par PierrotLeFou 27 novembre 2021 à 19:02:03

PierrotLeFou a écrit:

Ça fait beaucoup de code à vérifier (je suppose que le code du prof est correct ...)
Essaies avec des exemples simples. Je pense qu'il y en a dans ce lien:
https://fr.wikipedia.org/wiki/Codage_de_Huffman

-
Edité par PierrotLeFou il y a 25 minutes

Il n'y a pas à vérifier la code du prof oui, ni les fonctions codé avant decoderHuffman
J'ai seulement besoin d'aide pour la fonction decoderHuffman

Je vois que tu n'as pas reçu d'autre réponse.
Je trouvais ton code assez gros et celui du prof probablement assez compliqué.
J'ai d'abord codé l'algorithme en C, puis je l'ai traduit en Python.
Je ne fais pas la compression 8 bits par octet. Mon but était seulement de vérifier l'algo.
-
from collections import Counter
class Node:
    def __init__(self, code='', occur=0, left=None, right=None):
        self.code=code
        self.occur=occur
        self.left=left
        self.right=right
def setTree(node, convert, bits):
    if node.left is not None:
        setTree(node.left, convert, bits+[1])
        setTree(node.right, convert, bits+[0])
    else:
        convert[ord(node.code)] = bits
text1="this is an example of a huffman tree"
frequency = [Node(code=c, occur=o) for c, o in sorted(Counter(text1).items(), key=lambda t: (-t[1], t[0]))]
while len(frequency) > 1:
    root = Node(left=frequency[-2], right=frequency[-1], occur=frequency[-2].occur+frequency[-1].occur)
    frequency=frequency[:-2]
    frequency.insert(min(i for i, node in enumerate(frequency+[root]) if root.occur >= node.occur), root)
convert = [[] for _ in range(256)]
setTree(root, convert, [])
memory = []
for c in text1:
        memory.extend(convert[ord(c)])
text2=""
node = root
while len(memory):
        if node.left is None:
            text2+=node.code
            node = root
        node = (node.right, node.left)[memory.pop(0)]
text2+=node.code
print(text2)