Partage
  • Partager sur Facebook
  • Partager sur Twitter

Exercice codage Huffman

    27 novembre 2021 à 13:39:31

    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


    • Partager sur Facebook
    • Partager sur Twitter
      27 novembre 2021 à 19:00:37

      Ç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

      • Partager sur Facebook
      • Partager sur Twitter

      Le Tout est souvent plus grand que la somme de ses parties.

        27 novembre 2021 à 19:29:35

        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
        • Partager sur Facebook
        • Partager sur Twitter
          19 décembre 2021 à 4:12:26

          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)
          • Partager sur Facebook
          • Partager sur Twitter

          Le Tout est souvent plus grand que la somme de ses parties.

          Exercice codage Huffman

          × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
          • Editeur
          • Markdown