Code de Huffman préservant l’ordre approximatif

Je travaille sur une affectation pour une classe d’algorithmes et de structures de données. J’ai de la difficulté à comprendre les instructions données. Je ferai de mon mieux pour expliquer le problème.

L’entrée que je reçois est un entier positif n suivi de n entiers positifs représentant la fréquence (ou le poids) des symboles d’un jeu de caractères ordonné. Le premier objective est de construire un arbre qui donne un code de Huffman préservant l’ordre approximatif pour chaque caractère du jeu de caractères ordonné. Nous devons accomplir cela en “fusionnant avec avidité les deux arbres adjacents dont les poids ont la plus petite sum”.

Dans l’assignation, il est montré qu’une arborescence de code Huffman conventionnelle est construite en insérant d’abord les poids dans une queue prioritaire. Ensuite, en utilisant une fonction delmin () pour “extraire” la racine de la file de priorité, je peux obtenir les deux nœuds avec les fréquences les plus basses et les fusionner en un nœud, ses deux nœuds de gauche et de droite étant sa priorité, la priorité étant la sum des priorités de ses enfants. Ce nœud fusionné est ensuite réinséré dans le tas min. Le processus est répété jusqu’à ce que tous les nœuds d’entrée aient été fusionnés. J’ai implémenté cela en utilisant un tableau de taille 2 * n * -1, les noeuds d’entrée étant compris entre 0 … n -1 et ensuite de n … 2 * n * -1 comme étant les noeuds fusionnés.

Je ne comprends pas comment je peux fusionner avec avidité les deux arbres adjacents dont les poids ont la plus petite sum. Mon entrée a essentiellement été organisée en un min-heap et à partir de là je dois trouver les deux nœuds adjacents qui ont la plus petite sum et les fusionner. Par adjacent, je suppose que mon professeur signifie qu’ils sont côte à côte dans l’entrée.

Exemple d’entrée:

9 1 2 3 3 2 1 1 2 3 

Ensuite, mon min-tas ressemblerait à ceci:

  1 / \ 2 1 / \ / \ 2 2 3 1 / \ 3 3 

Les deux arbres (ou nœuds) adjacents dont la sum est la plus petite sont donc les deux 1 consécutifs qui apparaissent vers la fin de l’entrée. Quelle logique puis-je appliquer pour démarrer avec ces nœuds? Il me semble manquer quelque chose mais je n’arrive pas à le comprendre. S’il vous plaît, laissez-moi savoir si vous avez besoin de plus d’informations. Je peux élaborer moi-même ou fournir la page entière de la mission si quelque chose n’est pas clair.

Je pense que cela peut être fait avec une petite modification à l’algorithme conventionnel. Au lieu de stocker des arbres individuels dans votre segment de queue prioritaire, stockez des paires d’arbres adjacents. Ensuite, à chaque étape, vous supprimez la paire minimale (t1, t2) ainsi que les deux paires contenant également ces arbres, à savoir (u, t1) et (t2, r) . Fusionnez ensuite t1 et t2 en un nouvel arbre t' , réinsérez les paires (u, t') et (t', r) dans le tas avec les poids mis à jour et répétez.

Vous devez faire apparaître deux arbres et créer un troisième arbre. Pour cela, le noeud gauche joint l’arbre avec une sum plus petite et pour le noeud droit, rejoindre le deuxième arbre. Mettez cet arbre en tas. De votre exemple

Pop 2 arbre du tas:

1 1

Faire des arbres

  ? / \ ? ? 

Placez un arbre plus petit sur le noeud gauche

 min(1, 1) = 1 ? / \ 1 ? 

Mettre au deuxième arbre du nœud droit

  ? / \ 1 1 

L’arbre que vous avez créé a sum = sum du noeud gauche + sum du noeud droit

  2 / \ 1 1 

Mettez nouvel arbre (sum 2) à tas.

Enfin, vous aurez un arbre, c’est l’arbre de Huffman.