Codificación de Huffman usando cola de prioridad

Requisito previo: algoritmos codiciosos | Conjunto 3 (Codificación de Huffman) , Priority_queue::push() y Priority_queue::pop() en C++ STL 
Dada una array de caracteres ch[] y la frecuencia de cada carácter como freq[] . La tarea es encontrar códigos Huffman para cada carácter en ch[] usando Priority Queue .

Ejemplo 

Entrada: ch[] = { ‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ​​’f’ }, freq[] = { 5, 9, 12, 13, 16, 45 } 
Salida : 
f 0 
c 100 
d 101 
a 1100 
b 1101 
e 111 
  

Acercarse: 

  1. Empuje todos los caracteres en ch[] asignados a la frecuencia correspondiente freq[] en la cola de prioridad .
  2. Para crear Huffman Tree, extraiga dos Nodes de la cola de prioridad.
  3. Asigne dos Nodes emergentes de la cola de prioridad como hijo izquierdo y derecho del nuevo Node.
  4. Empuje el nuevo Node formado en la cola de prioridad.
  5. Repita todos los pasos anteriores hasta que el tamaño de la cola de prioridad sea 1.
  6. Atraviese el Árbol Huffman (cuya raíz es el único Node que queda en la cola de prioridad) para almacenar el Código Huffman
  7. Imprima todo el Código Huffman almacenado para cada carácter en ch[] .

A continuación se muestra la implementación del enfoque anterior:  

C++

// C++ Program for Huffman Coding
// using Priority Queue
#include <iostream>
#include <queue>
using namespace std;
 
// Maximum Height of Huffman Tree.
#define MAX_SIZE 100
 
class HuffmanTreeNode {
public:
    // Stores character
    char data;
 
    // Stores frequency of
    // the character
    int freq;
 
    // Left child of the
    // current node
    HuffmanTreeNode* left;
 
    // Right child of the
    // current node
    HuffmanTreeNode* right;
 
    // Initializing the
    // current node
    HuffmanTreeNode(char character,
                    int frequency)
    {
        data = character;
        freq = frequency;
        left = right = NULL;
    }
};
 
// Custom comparator class
class Compare {
public:
    bool operator()(HuffmanTreeNode* a,
                    HuffmanTreeNode* b)
    {
        // Defining priority on
        // the basis of frequency
        return a->freq > b->freq;
    }
};
 
// Function to generate Huffman
// Encoding Tree
HuffmanTreeNode* generateTree(priority_queue<HuffmanTreeNode*,
                              vector<HuffmanTreeNode*>,
                                             Compare> pq)
{
 
    // We keep on looping till
    // only one node remains in
    // the Priority Queue
    while (pq.size() != 1) {
 
        // Node which has least
        // frequency
        HuffmanTreeNode* left = pq.top();
 
        // Remove node from
        // Priority Queue
        pq.pop();
 
        // Node which has least
        // frequency
        HuffmanTreeNode* right = pq.top();
 
        // Remove node from
        // Priority Queue
        pq.pop();
 
        // A new node is formed
        // with frequency left->freq
        // + right->freq
 
        // We take data as '$'
        // because we are only
        // concerned with the
        // frequency
        HuffmanTreeNode* node = new HuffmanTreeNode('$',
                                  left->freq + right->freq);
        node->left = left;
        node->right = right;
 
        // Push back node
        // created to the
        // Priority Queue
        pq.push(node);
    }
 
    return pq.top();
}
 
// Function to print the
// huffman code for each
// character.
 
// It uses arr to store the codes
void printCodes(HuffmanTreeNode* root,
                int arr[], int top)
{
    // Assign 0 to the left node
    // and recur
    if (root->left) {
        arr[top] = 0;
        printCodes(root->left,
                   arr, top + 1);
    }
 
    // Assign 1 to the right
    // node and recur
    if (root->right) {
        arr[top] = 1;
        printCodes(root->right, arr, top + 1);
    }
 
    // If this is a leaf node,
    // then we print root->data
 
    // We also print the code
    // for this character from arr
    if (!root->left && !root->right) {
        cout << root->data << " ";
        for (int i = 0; i < top; i++) {
            cout << arr[i];
        }
        cout << endl;
    }
}
 
void HuffmanCodes(char data[],
                  int freq[], int size)
{
 
    // Declaring priority queue
    // using custom comparator
    priority_queue<HuffmanTreeNode*,
                   vector<HuffmanTreeNode*>,
                   Compare>
        pq;
 
    // Populating the priority
    // queue
    for (int i = 0; i < size; i++) {
        HuffmanTreeNode* newNode
            = new HuffmanTreeNode(data[i], freq[i]);
        pq.push(newNode);
    }
 
    // Generate Huffman Encoding
    // Tree and get the root node
    HuffmanTreeNode* root = generateTree(pq);
 
    // Print Huffman Codes
    int arr[MAX_SIZE], top = 0;
    printCodes(root, arr, top);
}
 
// Driver Code
int main()
{
    char data[] = { 'a', 'b', 'c', 'd', 'e', 'f' };
    int freq[] = { 5, 9, 12, 13, 16, 45 };
    int size = sizeof(data) / sizeof(data[0]);
 
    HuffmanCodes(data, freq, size);
    return 0;
}
Producción: 

f 0
c 100
d 101
a 1100
b 1101
e 111

 

Complejidad de tiempo: O(n*logn) donde n es el número de caracteres únicos
Espacio auxiliar: O(n)

Publicación traducida automáticamente

Artículo escrito por namang133 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *