Quindi, sto cercando di creare un'implementazione Java dell'algoritmo di Huffman per comprimere / decomprimere i file (come potreste sapere, da allora Perché creare un albero di Huffman per carattere invece di un nodo? ) per un incarico scolastico.
Ora ho una migliore comprensione di come questa cosa dovrebbe funzionare. Wikipedia ha qui un algoritmo di grande aspetto che sembra semplificarmi la vita. Tratto da link :
- Create a leaf node for each symbol and add it to the priority queue.
- While there is more than one node in the queue:
- Remove the two nodes of highest priority (lowest probability) from the queue
- Create a new internal node with these two nodes as children and with probability equal to the sum of the two nodes' probabilities.
- Add the new node to the queue.
- The remaining node is the root node and the tree is complete.
Sembra semplice e fantastico. Tuttavia, mi ha lasciato il dubbio: quando "unisco" due nodi (rendili figli di un nuovo nodo interno), importa anche quale direzione (a sinistra oa destra) ogni nodo sarà dopo?
Ancora non capisco perfettamente la codifica di Huffman, e non sono molto sicuro se ci sia un criterio usato per dire se un nodo dovrebbe andare a destra oa sinistra. Supponevo che, forse il nodo con la frequenza più alta sarebbe andato a destra, ma ho visto alcuni alberi di Huffman nel web che non sembrano seguire tali criteri.
Ad esempio, l'immagine di esempio di Wikipedia link sembra mettere i più alti a destra. Ma altre immagini come questa collegamento le hanno tutte a sinistra. Tuttavia, non sono mai mescolati nella stessa immagine (alcuni a destra e altri a sinistra) .
Quindi, importa? Perché?