Comment compresser des données à l`aide du codage huffman

L`algorithme de Huffman est utilisé pour comprimer ou encoder des données. Normalement, chaque caractère d`un fichier texte est stocké sous forme de huit bits (chiffres, 0 ou 1) de la carte à ce caractère à l`aide d`un codage appelé ASCII. Un fichier codé Huffman décompose la structure rigide 8 bits afin que les caractères les plus couramment utilisés soient stockés dans quelques bits (`A` pourrait être "dix" ou alors "1000" plutôt que l`ASCII, qui est "01100001"). Les caractères les moins communs prendront souvent beaucoup plus de 8 bits (z `pourrait être "00100011010"), mais parce qu`ils se produisent si rarement, le codage de Huffman, dans l`ensemble, crée un fichier beaucoup plus petit que l`original.

Pas

Partie 1 de 2:
Codage
  1. Image intitulée Compressez les données à l`aide de l`étape 1 de codage Huffman
1. Compter la fréquence de chaque caractère dans le fichier à coder. Inclure un caractère factice pour marquer la fin du fichier - cela sera important plus tard. Pour l`instant, appelez-le de l`EOF (fin du fichier) et marquez-le comme ayant une fréquence de 1.
  • Par exemple, si vous souhaitez encoder une lecture de fichier texte "AB AB CAB," Vous auriez «A» avec fréquence 3, `B` avec fréquence 3, `` (espace) avec fréquence 2, `C` avec fréquence 1 et EOF avec fréquence 1.
  • Image intitulée Compressez les données à l`aide de l`étape 2 de codage Huffman
    2. Stocker des caractères comme des nœuds d`arbre et les mettre dans une file d`attente prioritaire. Vous construirez un gros arbre binaire avec chaque caractère comme une feuille, vous devez donc stocker les caractères dans un format de sorte qu`ils puissent devenir des nœuds de l`arbre. Placez ces nœuds dans une file d`attente prioritaire avec la fréquence de chaque personnage comme priorité de son nœud.
  • Un arbre binaire est un format de données où chaque pièce de données est un nœud pouvant accueillir jusqu`à un parent et deux enfants. Il est souvent dessiné comme un arbre de ramification, d`où le nom.
  • Une file d`attente est une collection de données nommée bien que la première chose à entrer dans la file d`attente est également la première chose à sortir (comme en attente). Dans un priorité La file d`attente, les données sont stockées dans l`ordre de leur priorité, de sorte que la première chose à sortir est la chose la plus urgente, la chose avec la plus petite priorité, plutôt que la première chose enchantée.
  • Dans le "AB AB CAB" Exemple, votre file d`attente prioritaire ressemblerait à ceci: {`C`: 1, EOF: 1, ``: 2, `A`: 3, `B`: 3}
  • Image intitulée Compressez les données à l`aide de l`étape 3 de codage Huffman
    3. Commencez à construire votre arbre. Enlever (ou dequeuse) les deux choses les plus urgentes de la file d`attente prioritaire. Créez un nouveau nœud d`arborescence pour être le parent de ces deux nœuds, stockant le premier nœud en tant qu`enfant gauche et le second comme son enfant droit. La priorité du nouveau noeud devrait être la somme des priorités de son enfant. Ensuite, en faisez ce nouveau noeud dans la file d`attente prioritaire.
  • La file d`attente prioritaire ressemble maintenant à ceci: {``: 2, nouveau noeud: 2, `A`: 3, `B`: 3}
  • Image intitulée Compressez les données à l`aide de l`étape 4 de codage Huffman
    4. Terminez votre arbre: Répétez l`étape ci-dessus jusqu`à ce qu`il n`y ait qu`un seul noeud dans la file d`attente. Notez que, en plus des nœuds que vous avez créés pour les caractères et leurs fréquences, vous allez également désactiver, devenir des arbres et réapproquer les nœuds parents, les nœuds qui sont déjà eux-mêmes des arbres.
  • Lorsque vous avez terminé, le dernier nœud de la file d`attente sera le racine de l`arbre de codage, avec tous les autres nœuds se ramifiant de celui-ci.
  • Les caractères les plus fréquemment utilisés seront les feuilles les plus proches du haut de l`arborescence, tandis que les caractères rarement utilisés seront placés au fond de l`arbre, plus éloignés de la racine.
  • Image intitulée Compressez les données à l`aide de l`étape 5 de codage Huffman
    5. Créé un Carte de codage. Marcher dans l`arbre pour atteindre chaque personnage. Chaque fois que vous visitez l`enfant gauche d`un nœud, c`est un `0`. Chaque fois que vous visitez un enfant droit d`un nœud, c`est un «1». Lorsque vous arrivez à un personnage, stockez le personnage avec la séquence de 0s et 1s qu`il a fallu pour y arriver. Cette séquence est ce que le caractère sera codé comme dans le fichier compressé. Stocker les caractères et leurs séquences sur une carte.
  • Par exemple, commencez à la racine. Visitez l`enfant gauche de la racine, puis visitez l`enfant gauche de ce nœud. Depuis le nœud que vous n`avez pas à présent n`a aucun enfant, vous avez atteint un personnage. C`est ` `. Depuis que vous avez marché à gauche deux fois pour arriver ici, le codage pour `` est "00".
  • Pour cet arbre, la carte ressemblera à ceci: {``:"00", `une`:"dix", `B`:"11", `c`:"010", Eof:"011"}.
  • Image intitulée Compressez les données à l`aide de l`étape 6 de codage Huffman
    6. Dans le fichier de sortie, incluez la carte de codage comme en-tête. Cela permettra au fichier à décoder.
  • Image intitulée Compressez les données à l`aide de l`étape 7 de codage Huffman
    7. Encoder le fichier. Pour chaque caractère du fichier à coder, écrivez la séquence binaire que vous avez enregistrée sur la carte. Une fois que vous avez terminé de coder le fichier, assurez-vous d`ajouter le EOF à la fin.
  • Pour le fichier "AB AB CAB", Le fichier codé ressemblera à ceci: "1011001011000101011011".
  • Les fichiers sont stockés sous forme d`octets (8 bits ou 8 chiffres binaires). Étant donné que l`algorithme de codage Huffman n`utilise pas le format 8 bits, les fichiers codés ne seront souvent pas de longueurs qui sont des multiples de 8. Les chiffres restants seront remplis avec 0s. Dans ce cas, deux 0s seraient ajoutés à la fin du fichier, qui ressemble à un autre espace. Cela pourrait être un problème: comment savoir le décodeur quand arrêter de lire? Cependant, parce que nous avons inclus un caractère de fin de fichier, le décodeur ira à cela puis s`arrêter, ignorer toute autre chose qui a été ajoutée après.
    • Partie 2 de 2:
    Décodage
    1. Image intitulée Compressez les données à l`aide de l`étape 8 de codage Huffman
    1. Lire dans un fichier codé Huffman. Tout d`abord, lisez l`en-tête, qui devrait être la carte de codage. Utilisez ceci pour créer un arbre de décodage de la même manière que vous avez construit l`arbre que vous avez utilisé pour coder le fichier. Les deux arbres doivent être identiques.
  • Image intitulée Compressez les données à l`aide de l`étape 9 de codage Huffman
    2. Lire dans le binaire à un chiffre à la fois. Traverser l`arbre au fur et à mesure que vous lisez: Si vous lisez dans un «0», allez à l`enfant gauche du nœud, et si vous lisez dans un «1», allez à l`enfant droit. Lorsque vous atteignez une feuille (un nœud sans enfants), vous êtes arrivé à un personnage. Écrivez le caractère dans le fichier décodé.
  • En raison de la manière dont les caractères sont stockés dans l`arbre, les codes de chaque personnage ont un Propriété préfixe, de sorte que le codage binaire de personne ne peut jamais se produire au début du codage d`un autre personnage. Le codage pour chaque caractère est totalement unique. Cela rend le décodage beaucoup plus facile.
  • Image intitulée Compressez les données à l`aide de l`étape 10 de codage Huffman
    3. Répéter jusqu`à ce que vous atteigniez le eof. Toutes nos félicitations! Vous avez décodé le fichier.

    • Conseils

    Articles connexes