Comment stocker efficacement les arbres de Huffman pour la compression des données ?

Stockage efficace de l'arbre de Huffman pour la compression des données

Le codage Huffman optimise les données en attribuant des codes plus courts aux caractères plus fréquents. Pour stocker l'arbre de Huffman construit, diverses approches existent.

Méthode de minimisation de la taille de l'arbre

Si les données d'entrée sont petites, il existe un compromis entre l'efficacité et les frais généraux. . Pour des ensembles de données plus volumineux, envisagez la méthode suivante :

• Ne stockez pas les fréquences.

• Pour chaque nœud :

  • S'il s'agit d'un nœud feuille , génère 1 bit suivi du caractère/octet (N bits).
  • S'il ne s'agit pas d'un nœud feuille, génère 0 bit et encode les deux nœuds enfants de manière récursive.

Procédure de décodage :

• Lisez un peu.
• Si 1, lisez le caractère/octet N bits et créez un nœud feuille.
• Si 0, lisez les nœuds enfants gauche et droit de manière récursive.

Exemple

Considérez l'entrée "AAAABCCCCCDDEEEEE."

• Arbre :

              20
      ----------
      |        8
      |     -------
      12     |     3
  -----   |   -----
  A   C   E   B   D
  6   6   5   1   2

• Chemins :

  • A : 00
  • B : 110
  • C: 01
  • D: 111
  • E: 10

• Sortie codée :

  • Arbre : 001A1C01E01B1D (49 bits)
  • Données : 00000000000011001010101010111111101010101 (43 bits)
  • Total : 92 bits (12 octets)

Comparaison

Sans encodage Huffman :

• 20 caractères * 8 bits = 160 bits (20 octets)

Avec encodage Huffman :

• Surcharge de 12 octets

Considérations relatives aux petites données

Pour les données d'entrée plus petites, une approche qui stocke les fréquences peut être plus économe en espace. Calculer :

• Taille de l'arbre = 10 * Nombre de caractères - 1
• Taille codée = Somme (Fréquence de chaque caractère * Longueur du chemin vers le caractère)

Cette approche minimise la probabilité de perte d'espace.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!