Recomendamos leer la siguiente publicación como requisito previo para esto.
Algoritmos codiciosos | Conjunto 3 (Codificación Huffman)
La complejidad de tiempo del algoritmo discutido en la publicación anterior es O (nLogn). Si sabemos que la array dada está ordenada (por orden de frecuencia no decreciente), podemos generar códigos Huffman en tiempo O(n). A continuación se muestra un algoritmo O(n) para entrada ordenada.
1. Cree dos colas vacías.
2. Cree un Node de hoja para cada carácter único y colóquelo en la primera cola en orden de frecuencia no decreciente. Inicialmente, la segunda cola está vacía.
3. Saque de la cola dos Nodes con la frecuencia mínima examinando el frente de ambas colas. Repita los siguientes pasos dos veces
1. Si la segunda cola está vacía, elimine la cola de la primera cola.
2. Si la primera cola está vacía, elimine la cola de la segunda cola.
3. De lo contrario, compare el frente de dos colas y elimine la cola mínima.
4. Cree un nuevo Node interno con una frecuencia igual a la suma de las frecuencias de los dos Nodes. Convierta el primer Node Dequeued en su hijo izquierdo y el segundo Node Dequeued en su hijo derecho. Ponga en cola este Node en la segunda cola.
5. Repita los pasos 3 y 4 mientras haya más de un Node en las colas. El Node restante es el Node raíz y el árbol está completo.
C++
// C++ Program for Efficient Huffman Coding for Sorted input
#include <bits/stdc++.h>
using namespace std;
// This constant can be avoided by explicitly
// calculating height of Huffman Tree
#define MAX_TREE_HT 100
// A node of huffman tree
class QueueNode {
public:
char data;
unsigned freq;
QueueNode *left, *right;
};
// Structure for Queue: collection
// of Huffman Tree nodes (or QueueNodes)
class Queue {
public:
int front, rear;
int capacity;
QueueNode** array;
};
// A utility function to create a new Queuenode
QueueNode* newNode(char data, unsigned freq)
{
QueueNode* temp = new QueueNode[(sizeof(QueueNode))];
temp->left = temp->right = NULL;
temp->data = data;
temp->freq = freq;
return temp;
}
// A utility function to create a Queue of given capacity
Queue* createQueue(int capacity)
{
Queue* queue = new Queue[(sizeof(Queue))];
queue->front = queue->rear = -1;
queue->capacity = capacity;
queue->array = new QueueNode*[(queue->capacity
* sizeof(QueueNode*))];
return queue;
}
// A utility function to check if size of given queue is 1
int isSizeOne(Queue* queue)
{
return queue->front == queue->rear
&& queue->front != -1;
}
// A utility function to check if given queue is empty
int isEmpty(Queue* queue) { return queue->front == -1; }
// A utility function to check if given queue is full
int isFull(Queue* queue)
{
return queue->rear == queue->capacity - 1;
}
// A utility function to add an item to queue
void enQueue(Queue* queue, QueueNode* item)
{
if (isFull(queue))
return;
queue->array[++queue->rear] = item;
if (queue->front == -1)
++queue->front;
}
// A utility function to remove an item from queue
QueueNode* deQueue(Queue* queue)
{
if (isEmpty(queue))
return NULL;
QueueNode* temp = queue->array[queue->front];
if (queue->front
== queue
->rear) // If there is only one item in queue
queue->front = queue->rear = -1;
else
++queue->front;
return temp;
}
// A utility function to get from of queue
QueueNode* getFront(Queue* queue)
{
if (isEmpty(queue))
return NULL;
return queue->array[queue->front];
}
/* A function to get minimum item from two queues */
QueueNode* findMin(Queue* firstQueue, Queue* secondQueue)
{
// Step 3.a: If first queue is empty, dequeue from
// second queue
if (isEmpty(firstQueue))
return deQueue(secondQueue);
// Step 3.b: If second queue is empty, dequeue from
// first queue
if (isEmpty(secondQueue))
return deQueue(firstQueue);
// Step 3.c: Else, compare the front of two queues and
// dequeue minimum
if (getFront(firstQueue)->freq
< getFront(secondQueue)->freq)
return deQueue(firstQueue);
return deQueue(secondQueue);
}
// Utility function to check if this node is leaf
int isLeaf(QueueNode* root)
{
return !(root->left) && !(root->right);
}
// A utility function to print an array of size n
void printArr(int arr[], int n)
{
int i;
for (i = 0; i < n; ++i)
cout << arr[i];
cout << endl;
}
// The main function that builds Huffman tree
QueueNode* buildHuffmanTree(char data[], int freq[],
int size)
{
QueueNode *left, *right, *top;
// Step 1: Create two empty queues
Queue* firstQueue = createQueue(size);
Queue* secondQueue = createQueue(size);
// Step 2:Create a leaf node for each unique character
// and Enqueue it to the first queue in non-decreasing
// order of frequency. Initially second queue is empty
for (int i = 0; i < size; ++i)
enQueue(firstQueue, newNode(data[i], freq[i]));
// Run while Queues contain more than one node. Finally,
// first queue will be empty and second queue will
// contain only one node
while (
!(isEmpty(firstQueue) && isSizeOne(secondQueue))) {
// Step 3: Dequeue two nodes with the minimum
// frequency by examining the front of both queues
left = findMin(firstQueue, secondQueue);
right = findMin(firstQueue, secondQueue);
// Step 4: Create a new internal node with frequency
// equal to the sum of the two nodes frequencies.
// Enqueue this node to second queue.
top = newNode('$', left->freq + right->freq);
top->left = left;
top->right = right;
enQueue(secondQueue, top);
}
return deQueue(secondQueue);
}
// Prints huffman codes from the root of Huffman Tree. It
// uses arr[] to store codes
void printCodes(QueueNode* root, int arr[], int top)
{
// Assign 0 to left edge and recur
if (root->left) {
arr[top] = 0;
printCodes(root->left, arr, top + 1);
}
// Assign 1 to right edge and recur
if (root->right) {
arr[top] = 1;
printCodes(root->right, arr, top + 1);
}
// If this is a leaf node, then it contains one of the
// input characters, print the character and its code
// from arr[]
if (isLeaf(root)) {
cout << root->data << ": ";
printArr(arr, top);
}
}
// The main function that builds a Huffman Tree and print
// codes by traversing the built Huffman Tree
void HuffmanCodes(char data[], int freq[], int size)
{
// Construct Huffman Tree
QueueNode* root = buildHuffmanTree(data, freq, size);
// Print Huffman codes using the Huffman tree built
// above
int arr[MAX_TREE_HT], top = 0;
printCodes(root, arr, top);
}
// Driver code
int main()
{
char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f' };
int freq[] = { 5, 9, 12, 13, 16, 45 };
int size = sizeof(arr) / sizeof(arr[0]);
HuffmanCodes(arr, freq, size);
return 0;
}
// This code is contributed by rathbhupendra
C
// C Program for Efficient Huffman Coding for Sorted input
#include <stdio.h>
#include <stdlib.h>
// This constant can be avoided by explicitly calculating
// height of Huffman Tree
#define MAX_TREE_HT 100
// A node of huffman tree
struct QueueNode {
char data;
unsigned freq;
struct QueueNode *left, *right;
};
// Structure for Queue: collection of Huffman Tree nodes (or
// QueueNodes)
struct Queue {
int front, rear;
int capacity;
struct QueueNode** array;
};
// A utility function to create a new Queuenode
struct QueueNode* newNode(char data, unsigned freq)
{
struct QueueNode* temp = (struct QueueNode*)malloc(
sizeof(struct QueueNode));
temp->left = temp->right = NULL;
temp->data = data;
temp->freq = freq;
return temp;
}
// A utility function to create a Queue of given capacity
struct Queue* createQueue(int capacity)
{
struct Queue* queue
= (struct Queue*)malloc(sizeof(struct Queue));
queue->front = queue->rear = -1;
queue->capacity = capacity;
queue->array = (struct QueueNode**)malloc(
queue->capacity * sizeof(struct QueueNode*));
return queue;
}
// A utility function to check if size of given queue is 1
int isSizeOne(struct Queue* queue)
{
return queue->front == queue->rear
&& queue->front != -1;
}
// A utility function to check if given queue is empty
int isEmpty(struct Queue* queue)
{
return queue->front == -1;
}
// A utility function to check if given queue is full
int isFull(struct Queue* queue)
{
return queue->rear == queue->capacity - 1;
}
// A utility function to add an item to queue
void enQueue(struct Queue* queue, struct QueueNode* item)
{
if (isFull(queue))
return;
queue->array[++queue->rear] = item;
if (queue->front == -1)
++queue->front;
}
// A utility function to remove an item from queue
struct QueueNode* deQueue(struct Queue* queue)
{
if (isEmpty(queue))
return NULL;
struct QueueNode* temp = queue->array[queue->front];
if (queue->front
== queue
->rear) // If there is only one item in queue
queue->front = queue->rear = -1;
else
++queue->front;
return temp;
}
// A utility function to get from of queue
struct QueueNode* getFront(struct Queue* queue)
{
if (isEmpty(queue))
return NULL;
return queue->array[queue->front];
}
/* A function to get minimum item from two queues */
struct QueueNode* findMin(struct Queue* firstQueue,
struct Queue* secondQueue)
{
// Step 3.a: If first queue is empty, dequeue from
// second queue
if (isEmpty(firstQueue))
return deQueue(secondQueue);
// Step 3.b: If second queue is empty, dequeue from
// first queue
if (isEmpty(secondQueue))
return deQueue(firstQueue);
// Step 3.c: Else, compare the front of two queues and
// dequeue minimum
if (getFront(firstQueue)->freq
< getFront(secondQueue)->freq)
return deQueue(firstQueue);
return deQueue(secondQueue);
}
// Utility function to check if this node is leaf
int isLeaf(struct QueueNode* root)
{
return !(root->left) && !(root->right);
}
// A utility function to print an array of size n
void printArr(int arr[], int n)
{
int i;
for (i = 0; i < n; ++i)
printf("%d", arr[i]);
printf("\n");
}
// The main function that builds Huffman tree
struct QueueNode* buildHuffmanTree(char data[], int freq[],
int size)
{
struct QueueNode *left, *right, *top;
// Step 1: Create two empty queues
struct Queue* firstQueue = createQueue(size);
struct Queue* secondQueue = createQueue(size);
// Step 2:Create a leaf node for each unique character
// and Enqueue it to the first queue in non-decreasing
// order of frequency. Initially second queue is empty
for (int i = 0; i < size; ++i)
enQueue(firstQueue, newNode(data[i], freq[i]));
// Run while Queues contain more than one node. Finally,
// first queue will be empty and second queue will
// contain only one node
while (
!(isEmpty(firstQueue) && isSizeOne(secondQueue))) {
// Step 3: Dequeue two nodes with the minimum
// frequency by examining the front of both queues
left = findMin(firstQueue, secondQueue);
right = findMin(firstQueue, secondQueue);
// Step 4: Create a new internal node with frequency
// equal to the sum of the two nodes frequencies.
// Enqueue this node to second queue.
top = newNode('$', left->freq + right->freq);
top->left = left;
top->right = right;
enQueue(secondQueue, top);
}
return deQueue(secondQueue);
}
// Prints huffman codes from the root of Huffman Tree. It
// uses arr[] to store codes
void printCodes(struct QueueNode* root, int arr[], int top)
{
// Assign 0 to left edge and recur
if (root->left) {
arr[top] = 0;
printCodes(root->left, arr, top + 1);
}
// Assign 1 to right edge and recur
if (root->right) {
arr[top] = 1;
printCodes(root->right, arr, top + 1);
}
// If this is a leaf node, then it contains one of the
// input characters, print the character and its code
// from arr[]
if (isLeaf(root)) {
printf("%c: ", root->data);
printArr(arr, top);
}
}
// The main function that builds a Huffman Tree and print
// codes by traversing the built Huffman Tree
void HuffmanCodes(char data[], int freq[], int size)
{
// Construct Huffman Tree
struct QueueNode* root
= buildHuffmanTree(data, freq, size);
// Print Huffman codes using the Huffman tree built
// above
int arr[MAX_TREE_HT], top = 0;
printCodes(root, arr, top);
}
// Driver program to test above functions
int main()
{
char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f' };
int freq[] = { 5, 9, 12, 13, 16, 45 };
int size = sizeof(arr) / sizeof(arr[0]);
HuffmanCodes(arr, freq, size);
return 0;
}
Python3
# Python3 program for Efficient Huffman Coding
# for Sorted input
# Class for the nodes of the Huffman tree
class QueueNode:
def __init__(self, data = None, freq = None,
left = None, right = None):
self.data = data
self.freq = freq
self.left = left
self.right = right
# Function to check if the following
# node is a leaf node
def isLeaf(self):
return (self.left == None and
self.right == None)
# Class for the two Queues
class Queue:
def __init__(self):
self.queue = []
# Function for checking if the
# queue has only 1 node
def isSizeOne(self):
return len(self.queue) == 1
# Function for checking if
# the queue is empty
def isEmpty(self):
return self.queue == []
# Function to add item to the queue
def enqueue(self, x):
self.queue.append(x)
# Function to remove item from the queue
def dequeue(self):
return self.queue.pop(0)
# Function to get minimum item from two queues
def findMin(firstQueue, secondQueue):
# Step 3.1: If second queue is empty,
# dequeue from first queue
if secondQueue.isEmpty():
return firstQueue.dequeue()
# Step 3.2: If first queue is empty,
# dequeue from second queue
if firstQueue.isEmpty():
return secondQueue.dequeue()
# Step 3.3: Else, compare the front of
# two queues and dequeue minimum
if (firstQueue.queue[0].freq <
secondQueue.queue[0].freq):
return firstQueue.dequeue()
return secondQueue.dequeue()
# The main function that builds Huffman tree
def buildHuffmanTree(data, freq, size):
# Step 1: Create two empty queues
firstQueue = Queue()
secondQueue = Queue()
# Step 2: Create a leaf node for each unique
# character and Enqueue it to the first queue
# in non-decreasing order of frequency.
# Initially second queue is empty.
for i in range(size):
firstQueue.enqueue(QueueNode(data[i], freq[i]))
# Run while Queues contain more than one node.
# Finally, first queue will be empty and
# second queue will contain only one node
while not (firstQueue.isEmpty() and
secondQueue.isSizeOne()):
# Step 3: Dequeue two nodes with the minimum
# frequency by examining the front of both queues
left = findMin(firstQueue, secondQueue)
right = findMin(firstQueue, secondQueue)
# Step 4: Create a new internal node with
# frequency equal to the sum of the two
# nodes frequencies. Enqueue this node
# to second queue.
top = QueueNode("$", left.freq + right.freq,
left, right)
secondQueue.enqueue(top)
return secondQueue.dequeue()
# Prints huffman codes from the root of
# Huffman tree. It uses arr[] to store codes
def printCodes(root, arr):
# Assign 0 to left edge and recur
if root.left:
arr.append(0)
printCodes(root.left, arr)
arr.pop(-1)
# Assign 1 to right edge and recur
if root.right:
arr.append(1)
printCodes(root.right, arr)
arr.pop(-1)
# If this is a leaf node, then it contains
# one of the input characters, print the
# character and its code from arr[]
if root.isLeaf():
print(f"{root.data}: ", end = "")
for i in arr:
print(i, end = "")
print()
# The main function that builds a Huffman
# tree and print codes by traversing the
# built Huffman tree
def HuffmanCodes(data, freq, size):
# Construct Huffman Tree
root = buildHuffmanTree(data, freq, size)
# Print Huffman codes using the Huffman
# tree built above
arr = []
printCodes(root, arr)
# Driver code
arr = ["a", "b", "c", "d", "e", "f"]
freq = [5, 9, 12, 13, 16, 45]
size = len(arr)
HuffmanCodes(arr, freq, size)
# This code is contributed by Kevin Joshi
C++14
// Clean c++ stl code to generate huffman codes if the array
// is sorted in non-decreasing order
#include <bits/stdc++.h>
using namespace std;
// Node structure for creating a binary tree
struct Node {
char ch;
int freq;
Node* left;
Node* right;
Node(char c, int f, Node* l = nullptr,
Node* r = nullptr)
: ch(c)
, freq(f)
, left(l)
, right(r){};
};
// Find the min freq node between q1 and q2
Node* minNode(queue<Node*>& q1, queue<Node*>& q2)
{
Node* temp;
if (q1.empty()) {
temp = q2.front();
q2.pop();
return temp;
}
if (q2.empty()) {
temp = q1.front();
q1.pop();
return temp;
}
if (q1.front()->freq < q2.front()->freq) {
temp = q1.front();
q1.pop();
return temp;
}
else {
temp = q2.front();
q2.pop();
return temp;
}
}
// Function to print the generated huffman codes
void printHuffmanCodes(Node* root, string str = "")
{
if (!root)
return;
if (root->ch != '$') {
cout << root->ch << ": " << str << '\n';
return;
}
printHuffmanCodes(root->left, str + "0");
printHuffmanCodes(root->right, str + "1");
return;
}
// Function to generate huffman codes
void generateHuffmanCode(vector<pair<char, int> > v)
{
if (!v.size())
return;
queue<Node*> q1;
queue<Node*> q2;
for (auto it = v.begin(); it != v.end(); ++it)
q1.push(new Node(it->first, it->second));
while (!q1.empty() or q2.size() > 1) {
Node* l = minNode(q1, q2);
Node* r = minNode(q1, q2);
Node* node = new Node('$', l->freq + r->freq, l, r);
q2.push(node);
}
printHuffmanCodes(q2.front());
return;
}
int main()
{
vector<pair<char, int> > v
= { { 'a' , 5 }, { 'b' , 9 }, { 'c' , 12 },
{ 'd' , 13 }, { 'e' , 16 }, { 'f' , 45 } };
generateHuffmanCode(v);
return 0;
}
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA