Comment compresser des données à l'aide de l'encodage Huffman : 10 étapes

Table des matières:

Comment compresser des données à l'aide de l'encodage Huffman : 10 étapes
Comment compresser des données à l'aide de l'encodage Huffman : 10 étapes

Vidéo: Comment compresser des données à l'aide de l'encodage Huffman : 10 étapes

Vidéo: Comment compresser des données à l'aide de l'encodage Huffman : 10 étapes
Vidéo: DEBUTER DANS LE HACKING SANS BASES ET NE PAS ETRE UN SCRIPT KIDDIE ! 2024, Mars
Anonim

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

Pas

Partie 1 sur 2: Encodage

Compresser les données à l'aide de l'encodage Huffman Étape 1
Compresser les données à l'aide de l'encodage Huffman Étape 1

Étape 1. Comptez la fréquence de chaque caractère du fichier à encoder

Incluez un caractère factice pour marquer la fin du fichier -- ce sera important plus tard. Pour l'instant, appelez-le EOF (fin de fichier) et marquez-le comme ayant une fréquence de 1.

Par exemple, si vous voulez encoder un fichier texte avec la lecture "ab ab cab", vous aurez 'a' avec la fréquence 3, 'b' avec la fréquence 3, ' ' (espace) avec la fréquence 2, 'c' avec la fréquence 1, et EOF avec la fréquence 1

Compresser les données à l'aide de l'encodage Huffman Étape 2
Compresser les données à l'aide de l'encodage Huffman Étape 2

Étape 2. Stockez les caractères en tant que nœuds d'arborescence et placez-les dans une file d'attente prioritaire

Vous allez construire un grand arbre binaire avec chaque caractère en tant que feuille, vous devez donc stocker les caractères dans un format tel 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 donnée est un nœud pouvant avoir jusqu'à un parent et deux enfants. Il est souvent dessiné comme un arbre ramifié, d'où son nom.
  • Une file d'attente est une collection de données bien nommée où la première chose à entrer dans la file d'attente est également la première chose à sortir (comme faire la queue). Dans une file d'attente prioritaire, les données sont stockées par ordre de 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 mise en file d'attente.
  • Dans l'exemple "ab ab cab", votre file d'attente prioritaire ressemblerait à ceci: {'c':1, EOF:1, ' ':2, 'a':3, 'b':3}
Compresser les données à l'aide de l'encodage Huffman Étape 3
Compresser les données à l'aide de l'encodage Huffman Étape 3

Étape 3. Commencez à construire votre arbre

Supprimez (ou retirez de la file d'attente) les deux choses les plus urgentes de la file d'attente prioritaire. Créez un nouveau nœud d'arbre pour être le parent de ces deux nœuds, en stockant le premier nœud comme son enfant gauche et le second comme son enfant droit. La priorité du nouveau nœud doit être la somme des priorités de son enfant. Mettez ensuite ce nouveau nœud dans la file d'attente prioritaire.

La file d'attente prioritaire ressemble maintenant à ceci: {' ':2, new node:2, 'a':3, 'b':3}

Compresser les données à l'aide de l'encodage Huffman Étape 4
Compresser les données à l'aide de l'encodage Huffman Étape 4

Étape 4. Terminez la construction de votre arbre:

répétez l'étape ci-dessus jusqu'à ce qu'il n'y ait qu'un seul nœud dans la file d'attente. Notez qu'en plus des nœuds que vous avez créés pour les personnages et leurs fréquences, vous retirerez également la file d'attente, vous transformerez en arbres et vous remettrez en file d'attente des nœuds parents, des 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 la racine de l'arbre d'encodage, avec tous les autres nœuds qui en découlent.
  • Les caractères les plus fréquemment utilisés seront les feuilles les plus proches du sommet de l'arbre, tandis que les caractères rarement utilisés seront positionnés au bas de l'arbre, plus loin de la racine.
Compresser les données à l'aide de l'encodage Huffman Étape 5
Compresser les données à l'aide de l'encodage Huffman Étape 5

Étape 5. Créez une carte d'encodage. Traversez 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 l'enfant droit d'un nœud, c'est un « 1 ». Lorsque vous arrivez à un caractère, stockez le caractère avec la séquence de 0 et de 1 qu'il a fallu pour y arriver. Cette séquence est ce que le caractère sera codé comme dans le fichier compressé. Stockez les personnages et leurs séquences dans une carte.

  • Par exemple, commencez à la racine. Visitez l'enfant gauche de la racine, puis visitez l'enfant gauche de ce nœud. Puisque le nœud où vous vous trouvez n'a pas d'enfant, vous avez atteint un personnage. C'est ' '. Puisque vous avez marché deux fois à gauche pour arriver ici, l'encodage pour ' ' est "00".
  • Pour cet arbre, la carte ressemblera à ceci: {' ':"00", 'a':"10", 'b':"11", 'c':"010", EOF:"011"}.
Compresser les données à l'aide de l'encodage Huffman Étape 6
Compresser les données à l'aide de l'encodage Huffman Étape 6

Étape 6. Dans le fichier de sortie, incluez la carte de codage comme en-tête

Cela permettra au fichier d'être décodé.

Compresser les données à l'aide de l'étape 7 de l'encodage Huffman
Compresser les données à l'aide de l'étape 7 de l'encodage Huffman

Étape 7. Encodez le fichier

Pour chaque caractère du fichier à encoder, écrivez la séquence binaire que vous avez stockée dans la carte. Une fois que vous avez fini d'encoder le fichier, assurez-vous d'ajouter l'EOF à la fin.

  • Pour le fichier "ab ab cab", le fichier encodé 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 n'auront souvent pas des longueurs multiples de 8. Les chiffres restants seront remplis de 0. Dans ce cas, deux 0 seraient ajoutés à la fin du fichier, qui ressemble à un autre espace. Cela pourrait être un problème: comment le décodeur saurait-il quand arrêter la lecture ? Cependant, parce que nous avons inclus un caractère de fin de fichier, le décodeur y parviendra puis s'arrêtera, ignorant tout ce qui a été ajouté par la suite.

Partie 2 sur 2: Décodage

Compresser les données à l'aide de l'encodage Huffman Étape 8
Compresser les données à l'aide de l'encodage Huffman Étape 8

Étape 1. Lisez un fichier encodé Huffman

Tout d'abord, lisez l'en-tête, qui devrait être la carte d'encodage. Utilisez ceci pour construire un arbre de décodage de la même manière que vous avez construit l'arbre que vous avez utilisé pour encoder le fichier. Les deux arbres doivent être identiques.

Compresser les données à l'aide de l'étape 9 de l'encodage Huffman
Compresser les données à l'aide de l'étape 9 de l'encodage Huffman

Étape 2. Lisez le binaire un chiffre à la fois

Parcourez l'arbre au fur et à mesure que vous lisez: si vous lisez un '0', allez à l'enfant de gauche du nœud où vous vous trouvez, et si vous lisez un '1', allez à l'enfant de droite. Lorsque vous atteignez une feuille (un nœud sans aucun enfant), vous êtes arrivé à un caractère. Écrivez le caractère dans le fichier décodé.

En raison de la façon dont les caractères sont stockés dans l'arborescence, les codes de chaque caractère ont une propriété de préfixe, de sorte qu'aucun encodage binaire de caractère ne peut jamais se produire au début de l'encodage d'un autre caractère. L'encodage de chaque caractère est totalement unique. Cela rend le décodage beaucoup plus facile

Compresser les données à l'aide de l'étape 10 de l'encodage Huffman
Compresser les données à l'aide de l'étape 10 de l'encodage Huffman

Étape 3. Répétez jusqu'à ce que vous atteigniez l'EOF

Toutes nos félicitations! Vous avez décodé le fichier.

Conseillé: