Exemples Intéractifs: Codage de source

Types de Codage de Source¶

Le codage de source peut être classé en deux dimensions principales :

Codage sans perte (lossless) vs codage avec perte (lossy)
Codage à longueur fixe (fixed length) vs codage à longueur variable (variable length)

Ces classifications définissent comment les symboles d’une source sont représentés en séquences binaires, en fonction des besoins de l’application (fidélité des données, efficacité de compression, etc.).

Tableau Comparatif des Types de Codage de Source¶

Add blockquote

Type de Codage	Définition	Exemples	Avantages	Inconvénients	Applications
Sans Perte (Lossless)	Fidélité totale, données reconstructibles	Huffman, LZW	Aucune perte d’information	Taux de compression limité	Textes, bases de données, archives
Avec Perte (Lossy)	Compression irréversible, données partiellement perdues	JPEG, MP3	Taux de compression élevé	Perte de qualité irréversible	Images, vidéos, audio
Longueur Fixe (Fixed Length)	Codes binaires de longueur constante pour tous les symboles	ASCII, code binaire	Décodage simple, rapide	Inefficace pour des symboles à probabilités inégales	Systèmes simples
Longueur Variable (Variable Length)	Codes plus courts pour symboles fréquents, plus longs pour symboles rares	Huffman, arithmétique	Compression efficace, proche de l’entropie	Décodage plus complexe	Compression de données, multimédia

Choix du design¶

Le choix du type de codage de source dépend des exigences spécifiques de l’application. Le codage sans perte est indispensable pour les données critiques, tandis que le codage avec perte convient aux scénarios multimédias où un compromis entre qualité et compression est acceptable. De même, les codages à longueur fixe sont adaptés aux systèmes simples et uniformes, tandis que les codages à longueur variable sont optimaux pour des sources avec des symboles de probabilités différentes, permettant une utilisation plus efficace des ressources.

Codage de Huffman : Explications et Comparaison¶

Principe du codage de Huffman¶

Le codage de Huffman est un algorithme de compression sans perte basé sur les probabilités d’apparition des symboles. Les symboles les plus fréquents sont représentés par des codes binaires courts, tandis que les symboles moins fréquents reçoivent des codes plus longs. Ce principe réduit la longueur moyenne des codes, améliorant ainsi l’efficacité du stockage ou de la transmission.

Étapes du codage de Huffman¶

1. Initialisation¶

Chaque symbole $d_i$ est associé à sa probabilité $p_i$ .
Les symboles sont représentés comme des feuilles dans un arbre.

2. Construction de l’arbre¶

Trier les probabilités :
- Identifiez les deux symboles avec les plus petites probabilités $p_{\text{min1}}$ et $p_{\text{min2}}$ .
Combinaison des probabilités :
- Créez une nouvelle branche pour les deux probabilités sélectionnées, avec une probabilité égale à $p_{\text{min1}} + p_{\text{min2}}$ .
Réaffecter les codes :
- Associez le bit 0 à l’un des symboles et 1 à l’autre.
Répétition :
- Répétez ce processus jusqu’à ce qu’un seul nœud reste, représentant la racine de l’arbre.

3. Génération des codes¶

Pour chaque symbole, le code binaire est déterminé en suivant les branches de l’arbre, de la racine jusqu’à la feuille correspondante.

Comparaison avec une méthode sans compression¶

Méthode sans compression¶

Dans une méthode sans compression, chaque symbole est représenté par un code binaire de longueur fixe. La longueur nécessaire pour représenter $K$ symboles est donnée par :

L_{\text{fixe}} = \lceil \log_2(K) \rceil

(1)

où $K$ est le nombre total de symboles.

Mesures de performance¶

1. Entropie de la source¶

L’entropie représente la quantité moyenne d’information par symbole et est calculée par :

H(S) = -\sum_{i=1}^{K} p(d_i) \log_2(p(d_i))

(2)

Plus $H(S)$ est faible, plus la source est compressible.

2. Longueur moyenne des codes (Huffman)¶

La longueur moyenne des codes est donnée par :

\bar{L} = \sum_{i=1}^{K} p(d_i) \cdot \text{longueur du code Huffman}(d_i)

(3)

3. Variance des longueurs¶

La variance mesure la dispersion des longueurs des codes autour de la moyenne :

\sigma_L^2 = \sum_{i=1}^{K} p(d_i) \cdot (\text{longueur du code Huffman}(d_i) - \bar{L})^2

(4)

Taux de compression¶

Le taux de compression mesure l’efficacité de l’algorithme de Huffman en comparant la taille moyenne des codes générés avec une méthode sans compression. Il est calculé par :

T = \frac{L_{\text{fixe}} - \bar{L}}{L_{\text{fixe}}} \times 100

(5)

où :

$L_{\text{fixe}}$ est la longueur moyenne sans compression (codage fixe),
$\bar{L}$ est la longueur moyenne des codes générés par Huffman.

Source

import heapq
from collections import defaultdict
from ipywidgets import interact, IntSlider, Textarea, Output, VBox
import numpy as np
import math

# ================================
# Générer l'arbre de Huffman avec étapes intermédiaires
# ================================
def huffman_tree_with_steps(probabilities):
    """
    Génère l'arbre de Huffman à partir des probabilités des symboles
    et affiche les étapes intermédiaires.
    """
    heap = [[weight, [symbol, ""]] for symbol, weight in probabilities.items()]
    heapq.heapify(heap)

    steps = []  # Pour stocker les étapes intermédiaires

    while len(heap) > 1:
        low = heapq.heappop(heap)
        high = heapq.heappop(heap)
        steps.append((low, high))  # Ajoute l'étape intermédiaire

        for pair in low[1:]:
            pair[1] = "0" + pair[1]
        for pair in high[1:]:
            pair[1] = "1" + pair[1]
        heapq.heappush(heap, [low[0] + high[0]] + low[1:] + high[1:])

    final_tree = sorted(heapq.heappop(heap)[1:], key=lambda p: (len(p[-1]), p))
    return final_tree, steps

# ================================
# Calcul des mesures de performance
# ================================
def calculate_performance(probabilities, huffman_codes):
    """
    Calcule l'entropie, la longueur moyenne des codes et leur variance.
    """
    entropie = -sum(p * math.log2(p) for p in probabilities.values())
    lengths = {symbol: len(code) for symbol, code in huffman_codes}
    average_length = sum(probabilities[symbol] * lengths[symbol] for symbol in probabilities)
    variance = sum(probabilities[symbol] * (lengths[symbol] - average_length) ** 2 for symbol in probabilities)

    return entropie, average_length, variance

# ================================
# Fonction pour afficher les résultats
# ================================
def huffman_with_inputs(num_data, probabilities_input):
    """
    Génère le codage de Huffman à partir des inputs utilisateur
    et affiche les étapes intermédiaires et une comparaison avec la méthode non compressée.
    """
    # Parse les probabilités saisies
    probabilities = {}
    symbols = [f'd{i+1}' for i in range(num_data)]
    inputs = probabilities_input.split(",")

    if len(inputs) != num_data:
        print(f"[ERREUR] Vous devez entrer {num_data} probabilités séparées par des virgules.")
        return

    try:
        probabilities = {symbols[i]: float(inputs[i]) for i in range(num_data)}
    except ValueError:
        print("[ERREUR] Les probabilités doivent être des nombres décimaux.")
        return

    # Vérifie si la somme des probabilités est proche de 1
    if abs(sum(probabilities.values()) - 1.0) > 1e-6:
        print("[ERREUR] La somme des probabilités doit être égale à 1.")
        return

    # Générer l'arbre de Huffman et étapes intermédiaires
    huffman_codes, steps = huffman_tree_with_steps(probabilities)

    # Calculer les performances
    entropie, average_length, variance = calculate_performance(probabilities, huffman_codes)

    # Résultat sans compression
    fixed_length = math.ceil(math.log2(len(probabilities)))
    fixed_average_length = fixed_length

    # Afficher les étapes intermédiaires
    print("=== Étapes intermédiaires ===")
    for step_idx, (low, high) in enumerate(steps):
        print(f"Étape {step_idx + 1}:")
        print(f"  Combinaison de {low[1:]} et {high[1:]} → Nouvelle probabilité : {low[0] + high[0]}")
    print("\n")

    # Afficher le codage de Huffman
    print("=== Codage de Huffman ===")
    print(f"{'Symbole':<10}{'Probabilité':<15}{'Code Huffman'}")
    for symbol, code in huffman_codes:
        print(f"{symbol:<10}{probabilities[symbol]:<15.3f}{code}")

    # Comparaison avec une méthode sans compression
    print("\n=== Comparaison avec une méthode sans compression ===")
    print(f"Taille fixe (nombre de bits par symbole sans compression) : {fixed_length} bits")
    print(f"Longueur moyenne des codes sans compression : {fixed_average_length:.3f} bits")

    # Afficher les mesures de performance de Huffman
    print("\n=== Mesures de performance ===")
    print(f"Entropie de la source (H(S)) : {entropie:.3f} bits")
    print(f"Longueur moyenne des codes (Huffman) : {average_length:.3f} bits")
    print(f"Variance des longueurs des codes (σ²) : {variance:.3f} bits²")

# ================================
# Interface principale
# ================================
def huffman_interface(num_data):
    """
    Interface principale avec des champs d'entrée pour les probabilités.
    """
    # Probabilités par défaut générées aléatoirement
    random_probs = np.random.random(num_data)
    normalized_probs = [round(p / sum(random_probs), 3) for p in random_probs]

    # Générer un champ de saisie de probabilités
    probabilities_input = Textarea(
        value=",".join(map(str, normalized_probs)),
        description="Probabilités (séparées par des virgules) :",
        layout={'width': '600px', 'height': '100px'}
    )

    # Fonction pour capturer la mise à jour
    def update(_):
        output.clear_output()
        with output:
            huffman_with_inputs(num_data, probabilities_input.value)

    # Créer une sortie dynamique
    output = Output()
    probabilities_input.observe(update, names="value")

    # Afficher l'interface
    display(VBox([probabilities_input, output]))
    update(None)

print("### Codage de Huffman Interactif ###")
interact(
    huffman_interface,
    num_data=IntSlider(
        value=4,
        min=2,
        max=10,
        step=1,
        description="Nombre de données :"
    )
)

Introduction

Section 7 - Codage de source