Exploration du codage de Huffman qui est une technique de compression de données
Codage de Huffman
Le codage de Huffman est une technique de compression de données sans perte qui attribue des codes de longueurs variables aux symboles en fonction de leur fréquence d'apparition. Voici les étapes principales du codage de Huffman :
1️⃣ Calcul des fréquences d'apparition :
◉ Parcourir le texte ou les données à compresser.
◉ Compter le nombre d'apparitions de chaque symbole et construire une table de fréquences.
2️⃣ Création de l'arbre de Huffman :
◉ Créer un nœud pour chaque symbole avec sa fréquence.
◉ Regrouper les deux nœuds de fréquences minimales pour former un nouvel arbre.
◉ Répéter l'opération jusqu'à ce qu'il reste un seul arbre.
3️⃣ Attribution des codes binaires :
◉ Parcourir l'arbre de Huffman de la racine aux feuilles.
◉ Assigner 0 pour chaque arête gauche et 1 pour chaque arête droite.
◉ Les codes binaires des symboles sont obtenus en concaténant les valeurs sur le chemin de la racine à la feuille.
Arbre de Huffman :
L'arbre de Huffman est une structure d'arbre binaire utilisée dans le codage de Huffman. Il est construit en utilisant les fréquences des symboles à compresser. Voici quelques caractéristiques de l'arbre de Huffman :
Propriétés de l'arbre
1️⃣ Chaque nœud interne a deux enfants.
2️⃣ Les nœuds internes ont une fréquence égale à la somme des fréquences de leurs enfants.
3️⃣ Les feuilles de l'arbre représentent les symboles à compresser.
Exemple d'arbre de Huffman :
Supposons que nous ayons les symboles suivants avec leurs fréquences associées : • A: 45 • B: 13 • C: 12 • D: 16 • E: 9 • F: 5 Pour construire un arbre de Huffman à partir des fréquences suivantes : • A: 45 • B: 13 • C: 12 • D: 16 • E: 9 • F: 5
Voici les étapes détaillées :
1. Calcul des Fréquences Les fréquences déjà données sont : • A: 45 • B: 13 • C: 12 • D: 16 • E: 9 • F: 5
2. Création des Nœuds Créez un nœud pour chaque symbole avec sa fréquence : • Nœud A (45) • Nœud B (13) • Nœud C (12) • Nœud D (16) • Nœud E (9) • Nœud F (5)
3. Construction de l'Arbre Étapes de combinaison : a. Trier les nœuds par fréquence : • F: 5 • E: 9 • C: 12 • B: 13 • D: 16 • A: 45
b. Combiner F et E : • Créez un nœud avec une fréquence de 14 (5 + 9). • Nœud combiné : (F + E) = 14
c. Nouvelle liste de nœuds : • 14 (F + E) • C: 12 • B: 13 • D: 16 • A: 45
d. Trier à nouveau : • C: 12 • B: 13 • 14 (F + E) • D: 16 • A: 45
e. Combiner C et B : • Créez un nœud avec une fréquence de 25 (12 + 13). • Nœud combiné : (C + B) = 25
f. Nouvelle liste de nœuds : • 14 (F + E) • 25 (C + B) • D: 16 • A: 45
g. Trier à nouveau : • 14 (F + E) • D: 16 • 25 (C + B) • A: 45
h. Combiner 14 et D : • Créez un nœud avec une fréquence de 30 (14 + 16). • Nœud combiné : (F + E + D) = 30
g. Nouvelle liste de nœuds : • 25 (C + B) • 30 (F + E + D) • A: 45
h. Trier à nouveau : • 25 (C + B) • 30 (F + E + D) • A: 45
i. Combiner 25 et 30 : • Créez un nœud avec une fréquence de 55 (25 + 30). • Nœud combiné : (B + C + F + E + D) = 55
j. Finaliser l'arbre : Combiner ce nœud avec A (45) pour obtenir la racine de l'arbre avec une fréquence de 100.
Conclusion Ce processus montre comment construire un arbre de Huffman à partir de symboles et de leurs fréquences, en respectant les règles établies pour garantir une compression optimale.
Exemples de codes en Python :
Calcul des fréquences d'apparition :
⌨️
def calculate_frequencies(text): frequencies = {} for symbol in text: if symbol in frequencies: frequencies[symbol] += 1 else: frequencies[symbol] = 1 return frequencies
# Exemple d'utilisation text = 'ABACADABRA' frequencies = calculate_frequencies(text)
# Affichage des fréquences d'apparition pour chaque symbole for symbol, frequency in frequencies.items(): print(symbol + ':', frequency)
Résultat :
A: 5 B: 2 C: 1 D: 1 R: 1
Construction de l'arbre de Huffman :
⌨️
class Node: def __init__(self, symbol, frequency): self.symbol = symbol self.frequency = frequency self.left = None self.right = None
def build_huffman_tree(symbols, frequencies): nodes = [Node(symbol, frequency) for symbol, frequency in zip(symbols, frequencies)]
def assign_codes(node, code, codes): if node.symbol is not None: codes[node.symbol] = code else: assign_codes(node.left, code + '0', codes) assign_codes(node.right, code + '1', codes)
codes = {} assign_codes(huffman_tree, '', codes)
# Affichage des codes attribués à chaque symbole for symbol, code in codes.items(): print(symbol + ':', code)
Résultat :
B: 00 G: 0100 F: 0101 E: 011 A: 10 D: 110 C: 111
Exercices - corrigés: le codage de Huffman
Exercice 1:
Donnez les étapes du codage de Huffman pour les symboles suivants avec leurs fréquences respectives : Symboles : A, B, C, D, E Fréquences : 10, 5, 12, 8, 15
2. Construction de l'arbre de Huffman : Étape 1 : Combinaison des nœuds de fréquences minimales • B et D (5 + 8 = 13) • A (10) • C (12) • E (15)
Étape 2 : Combinaison des nœuds de fréquences minimales restants • B et D (13) • A (10) • C (12, racine) • E (15)
Étape 3 : Combinaison des nœuds de fréquences minimales restants • B et D (13) • A (10) • C (12, racine) • E (15, racine)
L'arbre de Huffman obtenu est le suivant : _________ | | ____25____ E:15 | | ___13___ C:12 | | _5_ A:10 | | B:5 D:8
3. Attribution des codes binaires : • Parcours de l'arbre de Huffman de la racine aux feuilles • Assignation de 0 pour chaque arête gauche et 1 pour chaque arête droite • Les codes binaires des symboles sont obtenus en concaténant les valeurs sur le chemin de la racine à la feuille
Un texte contient les symboles suivants avec leurs fréquences respectives :
Symboles : A, B, C, D, E, F Fréquences : 20, 15, 10, 8, 6, 1
1. Calculez les fréquences d'apparition pour chaque symbole. 2. Construisez l'arbre de Huffman correspondant. 3. Attribuez les codes binaires à chaque symbole.
1. Calcul des fréquences d'apparition pour chaque symbole.
Les fréquences d'apparition sont les suivantes : A: 20, B: 15, C: 10, D: 8, E: 6, F: 1
2. Construction de l'arbre de Huffman correspondant.
L'arbre de Huffman obtenu est le suivant : ______________ | | _____60____ F:1 | | ____30___ E:6 | | ___15___ D:8 | | C:10 B:15 | A:20
3. Attribution des codes binaires à chaque symbole.
Les codes binaires attribués sont les suivants : A: 0, B: 10, C: 110, D: 111, E: 1110, F: 1111
Ces exercices vous permettent de pratiquer les étapes du codage de Huffman et de vous familiariser avec la construction de l'arbre de Huffman et l'attribution des codes binaires.
Exercice 3:
Un fichier contient les symboles suivants avec leurs fréquences respectives :
Symboles : A, B, C, D, E, F, G Fréquences : 20, 15, 12, 10, 8, 5, 2
1. Calculez les fréquences d'apparition pour chaque symbole. 2. Construisez l'arbre de Huffman correspondant. 3. Attribuez les codes binaires à chaque symbole. 4. Calculez le taux de compression pour le fichier original.
1. Calcul des fréquences d'apparition pour chaque symbole.
Les fréquences d'apparition sont les suivantes : A: 20, B: 15, C: 12, D: 10, E: 8, F: 5, G: 2
2. Construction de l'arbre de Huffman correspondant.
3. Attribution des codes binaires à chaque symbole.
Les codes binaires attribués sont les suivants : A: 0, B: 10, C: 110, D: 111, E: 101, F: 1001, G: 1000
4. Calcul du taux de compression pour le fichier original.
Le taux de compression peut être calculé en utilisant la formule suivante : Taux de compression = (Taille du fichier original - Taille du fichier compressé) / Taille du fichier original
Supposons que chaque symbole est codé sur 4 bits (ce qui peut varier en fonction de l'implémentation réelle). Dans ce cas, la taille du fichier original serait de (20 + 15 + 12 + 10 + 8 + 5 + 2) * 4 = 224 bits.
La taille du fichier compressé dépend des fréquences d'apparition des symboles et de leurs codes binaires. En utilisant les codes attribués précédemment, vous pouvez calculer la taille du fichier compressé. Par exemple, si le fichier compressé utilise 3 bits par symbole en moyenne, la taille du fichier compressé serait de (20 * 3 + 15 * 3 + 12 * 3 + 10 * 3 + 8 * 3 + 5 * 3 + 2 * 3) = 282 bits.
En utilisant la formule du taux de compression, le taux de compression serait alors : (224 - 282) / 224 = -0.259, soit -25.9%.
Remarque : Un taux de compression négatif indique que la taille du fichier compressé est plus grande que la taille du fichier original dans ce cas particulier.
Exercice 4:
Un fichier contient les symboles suivants avec leurs fréquences respectives :
Symboles : A, B, C, D, E, F Fréquences : 25, 20, 15, 12, 10, 8
1. Calculez les fréquences d'apparition pour chaque symbole. 2. Construisez l'arbre de Huffman correspondant. 3. Attribuez les codes binaires à chaque symbole. 4. Calculez le taux de compression pour le fichier original.
1. Calcul les fréquences d'apparition pour chaque symbole.
Les fréquences d'apparition sont les suivantes : A: 25, B: 20, C: 15, D: 12, E: 10, F: 8
2. Construction l'arbre de Huffman correspondant.
L'arbre de Huffman obtenu est le suivant : _____________ | | ____80____ F:8 | | ____35___ E:10 | | ___15___ D:12 | | C:15 B:20 | A:25
3. Attribution des codes binaires à chaque symbole.
Les codes binaires attribués sont les suivants : A: 00, B: 01, C: 100, D: 101, E: 110, F: 111
4. Calcul du taux de compression pour le fichier original.
Correction : Supposons que chaque symbole est codé sur 3 bits (ce qui peut varier en fonction de l'implémentation réelle). Dans ce cas, la taille du fichier original serait de (25 + 20 + 15 + 12 + 10 + 8) * 3 = 270 bits.
La taille du fichier compressé dépend des fréquences d'apparition des symboleset de leurs codes binaires. En utilisant les codes attribués précédemment, vous pouvez calculer la taille du fichier compressé. Par exemple, si le fichier compressé utilise 2 bits par symbole en moyenne, la taille du fichier compressé serait de (25 * 2 + 20 * 2 + 15 * 3 + 12 * 3 + 10 * 3 + 8 * 3) = 206 bits.
En utilisant la formule du taux de compression, le taux de compression serait alors : (270 - 206) / 270 = 0.237, soit 23.7%.
Remarque : Un taux de compression positif indique que la taille du fichier compressé est plus petite que la taille du fichier original, ce qui est le cas dans cet exemple.
Plongez dans l'univers fascinant des suites numériques, où chaque terme révèle des patterns surprenants et des applications pratiques dans les mathématiques et au-delà.
Découvrez comment les fonctions tissent des liens entre les nombres et les concepts, transformant des idées abstraites en outils puissants pour résoudre des problèmes du quotidien.
Éducation
