Étapes pour compresser un fichier en utilisant le code Huffman

Question

Je sais qu'il y a beaucoup de questions impliquant le code Huffman, y compris une autre de moi-même, mais je me demande quelle serait la meilleure façon d'encoder réellement un fichier texte. La décompression semble triviale; traversant l'arbre, en allant à gauche à 0 et à droite sur 1, en imprimant le personnage.

Cependant, comment va la compression? En quelque sorte stocker la représentation bit du personnage dans son nœud l'arbre? Rechercher l'arbre pour le caractère chaque fois qu'il est rencontré et tracer les étapes? Est-ce important de quelle manière cela est codé? Jusqu'ici, j'ai un arbre de Huffman où les nœuds de feuille n'ont pas une valeur binaire qui leur est associée. Mon problème est d'assigner les valeurs binaires à chaque caractère de l'arbre.

Merci

Answer 1

Eh bien, si vous allez encoder un fichier sur une base de caractères, je ne vois pas le problème, il suffit de garder la table de hachage des symboles, puis construire un arbre & écrire dans le début d'un fichier en utilisant la convention que vous voulez, appliquez un nouvel alphabet au texte. Jetez un oeil à l'approche adoptée dans DEFLATE, qui est utilisé pour compresser les images PNG.

EDIT

Il n'est pas ce qui est vraiment clair que le problème est.

Rechercher l'arbre pour le caractère chaque fois qu'il est rencontré et tracer les étapes? Chaque nœud de l'arborescence représente un symbole unique.

Vous n'avez pas à chercher quoi que ce soit, vous ne pouvez construire l'arbre de Huffman que lorsque vous avez déjà calculé l'occurrence de chaque symbole.

Donc, vous avez déjà développé un algorithme pour construire un arbre et le problème est de savoir comment assigner les valeurs binaires aux nœuds? Ou où stocker ces valeurs? L'arbre lui-même représente les valeurs binaires naturellement, vous pouvez les suivre pendant la construction de l'arbre, garder la trace d'un 'chemin' dans l'opération d'insertion et stocker cette valeur dans un noeud, ou créer une table de hachage si vous ne le faites pas vouloir modifier l'entité de noeud.