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
Le Tout est souvent plus grand que la somme de ses parties.
Ç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)
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é.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.