Comment puis-je créer un arbre de Huffman codage et de décodage?

Pour ma mission, je dois faire un encodage et de décodage pour arbres de huffman. J'ai un problème de la création de mon arbre, et je suis coincé.

N'avez pas l'esprit de l'impression des états - ils sont juste pour me tester et voir ce que la sortie est alors que ma fonction s'exécute.

Pour la première boucle for, j'ai eu toutes les valeurs et index dans le fichier texte que j'ai utilisé dans mon bloc principal pour les tests.

Dans la deuxième boucle for, j'ai inséré tous les trucs dans la file d'attente de priorité.

Je suis donc coincé sur où aller - je suis en train de faire des nœuds, mais je suis confus sur la façon de progresser. Quelqu'un peut-il me dire si je suis en train de faire de ce droit?

def _create_code(self, frequencies):
    '''(HuffmanCoder, sequence(int)) -> NoneType
    iterate over index into the sequence keeping it 256 elements long, '''
    #fix docstring
    p = PriorityQueue()
    print frequencies

    index = 0 
    for value in frequencies:
        if value != 0:
            print value #priority
            print index #elm
            print '-----------'       
        index = index + 1


    for i in range(len(frequencies)):
        if frequencies[i] != 0:
            p.insert(i, frequencies[i])  
            print i,frequencies[i]
            if p.is_empty():
                a = p.get_min()
                b = p.get_min()
                n1 = self.HuffmanNode(None, None, a)
                n2 = self.HuffmanNode(None, None, b)
                print a, b, n1, n2
    while not p.is_empty():
        p.get_min()

J'ai inséré manuellement les deux premiers pour commencer mon arbre, est-ce correct?

Comment dois-je continuer? Je sais que l'idée de celui-ci, juste au niveau du code, je suis très coincé.

C'est à l'aide de python, par la manière. J'ai essayé de regarder sur Wikipedia, je connais les étapes, j'ai juste besoin d'aide sur le code et comment je dois continuer, merci!

La HuffmanNode vient de cette classe imbriquée:

class HuffmanNode(object):

    def __init__(self, left=None, right=None, root=None):
        self.left = left
        self.right = right
        self.root = root

Je le ferais de manière récursive.
comment alors ?la récursivité est donc source de confusion pour moi, peut-u sorta de me guider dans le ventre?
En fait, je pense qu'une solution itérative est assez simple. Voici deux de ces algorithmes donnés sur la wikipedia article le Codage Huffman.

OriginalL'auteur xevaaa | 2012-07-20

L'algorithme de Huffman dans Wikipedia vous dit exactement comment créer un nœud de l'arbre, de sorte que votre programme peut être basé sur l'algorithme, ou une autre comme elle. Voici un programme en Python avec des commentaires montrant le correspondant de wikipédia étape de l'algorithme. Les données de test des fréquences des lettres de l'alphabet dans un texte en anglais.

Une fois que le nœud de l'arbre est créé, vous avez besoin de marcher vers le bas pour attribuer des codes de Huffman pour chaque symbole dans votre jeu de données. Puisque c'est les devoirs, c'est à vous, mais un algorithme récursif est la plus simple et la plus naturelle façon de le gérer. C'est seulement six lignes de code.

import queue
class HuffmanNode(object):
def __init__(self, left=None, right=None, root=None):
self.left = left
self.right = right
self.root = root     # Why?  Not needed for anything.
def children(self):
return((self.left, self.right))
freq = [
(8.167, 'a'), (1.492, 'b'), (2.782, 'c'), (4.253, 'd'),
(12.702, 'e'),(2.228, 'f'), (2.015, 'g'), (6.094, 'h'),
(6.966, 'i'), (0.153, 'j'), (0.747, 'k'), (4.025, 'l'),
(2.406, 'm'), (6.749, 'n'), (7.507, 'o'), (1.929, 'p'), 
(0.095, 'q'), (5.987, 'r'), (6.327, 's'), (9.056, 't'), 
(2.758, 'u'), (1.037, 'v'), (2.365, 'w'), (0.150, 'x'),
(1.974, 'y'), (0.074, 'z') ]
def create_tree(frequencies):
p = queue.PriorityQueue()
for value in frequencies:    # 1. Create a leaf node for each symbol
p.put(value)             #    and add it to the priority queue
while p.qsize() > 1:         # 2. While there is more than one node
l, r = p.get(), p.get()  # 2a. remove two highest nodes
node = HuffmanNode(l, r) # 2b. create internal node with children
p.put((l[0]+r[0], node)) # 2c. add new node to queue      
return p.get()               # 3. tree is complete - return root node
node = create_tree(freq)
print(node)
# Recursively walk the tree down to the leaves,
#   assigning a code value to each symbol
def walk_tree(node, prefix="", code={}):
return(code)
code = walk_tree(node)
for i in sorted(freq, reverse=True):
print(i[1], '{:6.2f}'.format(i[0]), code[i[1]])

Lorsqu'il est exécuté sur l'alphabet de données, le Huffman codes sont:

e  12.70 100
t   9.06 000
a   8.17 1110
o   7.51 1101
i   6.97 1011
n   6.75 1010
s   6.33 0111
h   6.09 0110
r   5.99 0101
d   4.25 11111
l   4.03 11110
c   2.78 01001
u   2.76 01000
m   2.41 00111
w   2.37 00110
f   2.23 00100
g   2.02 110011
y   1.97 110010
p   1.93 110001
b   1.49 110000
v   1.04 001010
k   0.75 0010111
j   0.15 001011011
x   0.15 001011010
q   0.10 001011001
z   0.07 001011000

pouvez vous s'il vous plaît fournir la récursivité de la fonction, j'ai essayé de le faire, mais a échoué...
J'ai tester votre code, mais j'ai une erreur:print(i[1], '{:6.2 f}'.format(i[0]), le code[i[1]]) KeyError: 'e'
Cela ne prend pas en compte le vocabulaire de la commande de nœuds avec l'égalité des fréquences.

OriginalL'auteur Dave

@Dave walk_tree est manquant arbre de code de traitement de

# Recursively walk the tree down to the leaves,
# assigning a code value to each symbol
def walk_tree(node, prefix="", code={}):
if isinstance(node[1].left[1], HuffmanNode):
walk_tree(node[1].left,prefix+"0", code)
else:
code[node[1].left[1]]=prefix+"0"
if isinstance(node[1].right[1],HuffmanNode):
walk_tree(node[1].right,prefix+"1", code)
else:
code[node[1].right[1]]=prefix+"1"
return(code)

OriginalL'auteur user1762278

Encore une solution de retour d'un dictionnaire {label:code} et récursive dictionnaire tree contenant le graphe obtenu. L'entrée vals est en forme de dictionnaire {label:freq}:

def assign_code(nodes, label, result, prefix = ''):    
childs = nodes[label]     
tree = {}
if len(childs) == 2:
tree['0'] = assign_code(nodes, childs[0], result, prefix+'0')
tree['1'] = assign_code(nodes, childs[1], result, prefix+'1')     
return tree
else:
result[label] = prefix
return label
def Huffman_code(_vals):    
vals = _vals.copy()
nodes = {}
for n in vals.keys(): # leafs initialization
nodes[n] = []
while len(vals) > 1: # binary tree creation
s_vals = sorted(vals.items(), key=lambda x:x[1]) 
a1 = s_vals[0][0]
a2 = s_vals[1][0]
vals[a1+a2] = vals.pop(a1) + vals.pop(a2)
nodes[a1+a2] = [a1, a2]        
code = {}
root = a1+a2
tree = {}
tree = assign_code(nodes, root, code)   # assignment of the code for the given binary tree      
return code, tree

Il peut être utilisé comme:

freq = [
(8.167, 'a'), (1.492, 'b'), (2.782, 'c'), (4.253, 'd'),
(12.702, 'e'),(2.228, 'f'), (2.015, 'g'), (6.094, 'h'),
(6.966, 'i'), (0.153, 'j'), (0.747, 'k'), (4.025, 'l'),
(2.406, 'm'), (6.749, 'n'), (7.507, 'o'), (1.929, 'p'), 
(0.095, 'q'), (5.987, 'r'), (6.327, 's'), (9.056, 't'), 
(2.758, 'u'), (1.037, 'v'), (2.365, 'w'), (0.150, 'x'),
(1.974, 'y'), (0.074, 'z') ]    
vals = {l:v for (v,l) in freq}
code, tree = Huffman_code(vals)
text = 'hello' # text to encode
encoded = ''.join([code[t] for t in text])
print('Encoded text:',encoded)
decoded = []
i = 0
while i < len(encoded): # decoding using the binary graph
ch = encoded[i]  
act = tree[ch]
while not isinstance(act, str):
i += 1
ch = encoded[i]  
act = act[ch]        
decoded.append(act)          
i += 1
print('Decoded text:',''.join(decoded))

L'on peut visualiser l'arbre avec Graphviz:
Comment puis-je créer un arbre de Huffman codage et de décodage?

La figure a été généré par le script suivant que (Graphviz est nécessaire):

def draw_tree(tree, prefix = ''):    
if isinstance(tree, str):            
descr = 'N%s [label="%s:%s", fontcolor=blue, fontsize=16, width=2, shape=box];\n'%(prefix, tree, prefix)
else: # Node description
descr = 'N%s [label="%s"];\n'%(prefix, prefix)
for child in tree.keys():
descr += draw_tree(tree[child], prefix = prefix+child)
descr += 'N%s -> N%s;\n'%(prefix,prefix+child)
return descr
import subprocess
with open('graph.dot','w') as f:
f.write('digraph G {\n')
f.write(draw_tree(tree))
f.write('}') 
subprocess.call('dot -Tpng graph.dot -o graph.png', shell=True)

C'est génial! @Pavel. En collaboration avec le Graphiz script, ce qui rend une bonne réponse

OriginalL'auteur Pavel Prochazka

Je travaillais ce problème aujourd'hui, pour essayer et le résultat d'un match au-dessus de réponse. Pour la plupart partie, cette solution fonctionne bien mais la seule chose que je trouve non-intuitif est à ajouter [0] et [1] dans l'impression de la non-node (leaf).
Mais cela répond à des miracles sur la question -, vous pouvez l'imprimer à l'aide de toute la traversée de mécanisme

import queue
class HuffmanNode(object):
def __init__(self,left=None,right=None,root=None):
self.left = left
self.right = right
self.root = root
def children(self):
return (self.left,self.right)
def preorder(self,path=None):
if path is None:
path = []
if self.left is not None:
if isinstance(self.left[1], HuffmanNode):
self.left[1].preorder(path+[0])
else:
print(self.left,path+[0])
if self.right is not None:
if isinstance(self.right[1], HuffmanNode):
self.right[1].preorder(path+[1])
else:
print(self.right,path+[1])
freq = [
(8.167, 'a'), (1.492, 'b'), (2.782, 'c'), (4.253, 'd'),
(12.702, 'e'),(2.228, 'f'), (2.015, 'g'), (6.094, 'h'),
(6.966, 'i'), (0.153, 'j'), (0.747, 'k'), (4.025, 'l'),
(2.406, 'm'), (6.749, 'n'), (7.507, 'o'), (1.929, 'p'), 
(0.095, 'q'), (5.987, 'r'), (6.327, 's'), (9.056, 't'), 
(2.758, 'u'), (1.037, 'v'), (2.365, 'w'), (0.150, 'x'),
(1.974, 'y'), (0.074, 'z') ]
def encode(frequencies):
p = queue.PriorityQueue()
for item in frequencies:
p.put(item)
#invariant that order is ascending in the priority queue
#p.size() gives list of elements
while p.qsize() > 1:
left,right = p.get(),p.get()
node = HuffmanNode(left,right)
p.put((left[0]+right[0],node))
return p.get()
node = encode(freq)
print(node[1].preorder())

OriginalL'auteur max_new

1

@Dave classe HuffmanNode(objet) a un bug subtil. Lorsque les deux fréquences sont égales, une exception est levée: Pour exemple, nous allons
```
    freq = [ (200/3101, 'd'), (100/3101, 'e'), (100/3101, 'f') ]
```
Puis vous obtenez des TypeError: unorderable types: HuffmanNode() < str().
Le problème a à voir avec la PriorityQueue mise en œuvre. Je soupçonne quand les premiers éléments de l'tuples de comparer l'égalité, PriorityQueue veut comparer le deuxième éléments dont l'un est un objet python. Vous ajoutez le lt méthode à votre classe et le problème est résolu.
```
    def __lt__(self,other):
return 0
```
OriginalL'auteur B Abali

Vous devez vous connecter pour publier un commentaire.