Рубрики

Эффективное кодирование Хаффмана для отсортированного ввода | Жадный Алго-4

Рекомендуем прочитать следующий пост как необходимое условие для этого.

Жадные алгоритмы | Набор 3 (кодирование Хаффмана)

Временная сложность алгоритма, рассмотренного в посте выше, равна O (nLogn). Если мы знаем, что данный массив отсортирован (по неубывающему порядку частоты), мы можем генерировать коды Хаффмана за O (n) времени. Ниже приведен алгоритм O (n) для отсортированного ввода.

1. Создайте две пустые очереди.

2. Создайте листовой узел для каждого уникального символа и поместите его в первую очередь в неубывающем порядке частоты. Изначально вторая очередь пуста.

3. Снимите очередь с двух узлов с минимальной частотой, изучив переднюю часть обеих очередей. Повторите следующие шаги два раза
… .. а) Если вторая очередь пуста, очередь из первой очереди.
… .. б) Если первая очередь пуста, очередь из второй очереди.
… .. в) Иначе, сравните начало двух очередей и выведите минимум из очереди.

4. Создайте новый внутренний узел с частотой, равной сумме частот двух узлов. Сделайте первый узел Dequeued как его левый потомок, а второй узел Dequeued как правый потомок. Поставьте этот узел во вторую очередь.

5. Повторяйте шаги № 3 и № 4, пока в очередях не будет более одного узла. Оставшийся узел является корневым, и дерево завершено.

C ++

// Программа C ++ для эффективного кодирования Хаффмана для отсортированного ввода
#include <bits/stdc++.h>

using namespace std;

  
// Эту константу можно избежать явно
// вычисление высоты дерева Хаффмана
#define MAX_TREE_HT 100 

  
// Узел дерева Хаффмана

class QueueNode 

    public:

    char data; 

    unsigned freq; 

    QueueNode *left, *right; 

}; 

  
// Структура для очереди: коллекция
// узлов дерева Хаффмана (или QueueNodes)

class Queue 

    public:

    int front, rear; 

    int capacity; 

    QueueNode **array; 

}; 

  
// Утилита для создания нового 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; 

  
// Вспомогательная функция для создания очереди заданной емкости

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; 

  
// Полезная функция для проверки, равен ли размер данной очереди 1

int isSizeOne(Queue* queue) 

    return queue->front == queue->rear && queue->front != -1; 

  
// Сервисная функция, чтобы проверить, пуста ли данная очередь

int isEmpty(Queue* queue) 

    return queue->front == -1; 

  
// Сервисная функция, чтобы проверить, заполнена ли данная очередь

int isFull(Queue* queue) 

    return queue->rear == queue->capacity - 1; 

  
// Утилита для добавления элемента в очередь

void enQueue(Queue* queue, QueueNode* item) 

    if (isFull(queue)) 

        return

    queue->array[++queue->rear] = item; 

    if (queue->front == -1) 

        ++queue->front; 

  
// Утилита для удаления элемента из очереди
QueueNode* deQueue(Queue* queue) 

    if (isEmpty(queue)) 

        return NULL; 

    QueueNode* temp = queue->array[queue->front]; 

    if (queue->front == queue->rear) // Если в очереди только один элемент

        queue->front = queue->rear = -1; 

    else

        ++queue->front; 

    return temp; 

  
// Полезная функция для получения из очереди
QueueNode* getFront(Queue* queue) 

    if (isEmpty(queue)) 

        return NULL; 

    return queue->array[queue->front]; 

  
/ * Функция для получения минимального элемента из двух очередей * /
QueueNode* findMin(Queue* firstQueue, Queue* secondQueue) 

    // Шаг 3.a: Если первая очередь пуста, очередь из второй очереди

    if (isEmpty(firstQueue)) 

        return deQueue(secondQueue); 

  

    // Шаг 3.b: Если вторая очередь пуста, очередь из первой очереди

    if (isEmpty(secondQueue)) 

        return deQueue(firstQueue); 

  

    // Шаг 3.c: Иначе, сравнить начало двух очередей и минимум очереди

    if (getFront(firstQueue)->freq < getFront(secondQueue)->freq) 

        return deQueue(firstQueue); 

  

    return deQueue(secondQueue); 

  
// Сервисная функция, чтобы проверить, является ли этот узел листом

int isLeaf(QueueNode* root) 

    return !(root->left) && !(root->right) ; 

  
// Вспомогательная функция для печати массива размера n

void printArr(int arr[], int n) 

    int i; 

    for (i = 0; i < n; ++i) 

        cout<<arr[i]; 

    cout<<endl; 

  
// Основная функция, которая строит дерево Хаффмана

QueueNode* buildHuffmanTree(char data[], int freq[], int size) 

    QueueNode *left, *right, *top; 

  

    // Шаг 1: Создать две пустые очереди

    Queue* firstQueue = createQueue(size); 

    Queue* secondQueue = createQueue(size); 

  

    // Шаг 2: Создать листовой узел для каждого уникального символа и поставить его в очередь

    // первая очередь в порядке убывания частоты. Изначально второй

    // очередь пуста

    for (int i = 0; i < size; ++i) 

        enQueue(firstQueue, newNode(data[i], freq[i])); 

  

    // Выполнить, пока очереди содержат более одного узла. Наконец, первая очередь будет

    // быть пустым и вторая очередь будет содержать только один узел

    while (!(isEmpty(firstQueue) && isSizeOne(secondQueue))) 

    

        // Шаг 3: вывести из очереди два узла с минимальной частотой, исследуя

        // фронт обеих очередей

        left = findMin(firstQueue, secondQueue); 

        right = findMin(firstQueue, secondQueue); 

  

        // Шаг 4: Создать новый внутренний узел с частотой, равной сумме

        // частот двух узлов. Поставьте этот узел во вторую очередь.

        top = newNode('$' , left->freq + right->freq); 

        top->left = left; 

        top->right = right; 

        enQueue(secondQueue, top); 

    

  

    return deQueue(secondQueue); 

  
// Печатает коды Хаффмана из корня дерева Хаффмана. Он использует arr [] для
// хранить коды

void printCodes(QueueNode* root, int arr[], int top) 

    // Присваиваем 0 левому краю и повторяем

    if (root->left) 

    

        arr[top] = 0; 

        printCodes(root->left, arr, top + 1); 

    

  

    // Назначаем 1 правому краю и повторяем

    if (root->right) 

    

        arr[top] = 1; 

        printCodes(root->right, arr, top + 1); 

    

  

    // Если это листовой узел, то он содержит один из входных

    // символы, вывести символ и его код из arr []

    if (isLeaf(root)) 

    

        cout<<root->data<<": "

        printArr(arr, top); 

    

  
// Основная функция, которая строит дерево Хаффмана и печатает коды путем обхода
// построенное дерево Хаффмана

void HuffmanCodes(char data[], int freq[], int size) 


// Построить дерево Хаффмана
QueueNode* root = buildHuffmanTree(data, freq, size); 

  
// Печатать коды Хаффмана, используя построенное выше дерево Хаффмана

int arr[MAX_TREE_HT], top = 0; 

printCodes(root, arr, top); 

  
// Код драйвера

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; 

  

  
// Этот код предоставлен rathbhupendra

С

// Программа для эффективного кодирования Хаффмана для отсортированного ввода
#include <stdio.h>
#include <stdlib.h>

  
// Этой константы можно избежать, явно рассчитав высоту дерева Хаффмана
#define MAX_TREE_HT 100

  
// Узел дерева Хаффмана

struct QueueNode

{

    char data;

    unsigned freq;

    struct QueueNode *left, *right;

};

  
// Структура для очереди: коллекция узлов дерева Хаффмана (или QueueNodes)

struct Queue

{

    int front, rear;

    int capacity;

    struct QueueNode **array;

};

  
// Утилита для создания нового 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;

}

  
// Вспомогательная функция для создания очереди заданной емкости

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;

}

  
// Полезная функция для проверки, равен ли размер данной очереди 1

int isSizeOne(struct Queue* queue)

{

    return queue->front == queue->rear && queue->front != -1;

}

  
// Сервисная функция, чтобы проверить, пуста ли данная очередь

int isEmpty(struct Queue* queue)

{

    return queue->front == -1;

}

  
// Сервисная функция, чтобы проверить, заполнена ли данная очередь

int isFull(struct Queue* queue)

{

    return queue->rear == queue->capacity - 1;

}

  
// Утилита для добавления элемента в очередь

void enQueue(struct Queue* queue, struct QueueNode* item)

{

    if (isFull(queue))

        return;

    queue->array[++queue->rear] = item;

    if (queue->front == -1)

        ++queue->front;

}

  
// Утилита для удаления элемента из очереди

struct QueueNode* deQueue(struct Queue* queue)

{

    if (isEmpty(queue))

        return NULL;

    struct QueueNode* temp = queue->array[queue->front];

    if (queue->front == queue->rear)  // Если в очереди только один элемент

        queue->front = queue->rear = -1;

    else

        ++queue->front;

    return temp;

}

  
// Полезная функция для получения из очереди

struct QueueNode* getFront(struct Queue* queue)

{

    if (isEmpty(queue))

        return NULL;

    return queue->array[queue->front];

}

  
/ * Функция для получения минимального элемента из двух очередей * /

struct QueueNode* findMin(struct Queue* firstQueue, struct Queue* secondQueue)

{

    // Шаг 3.a: Если первая очередь пуста, очередь из второй очереди

    if (isEmpty(firstQueue))

        return deQueue(secondQueue);

  

    // Шаг 3.b: Если вторая очередь пуста, очередь из первой очереди

    if (isEmpty(secondQueue))

        return deQueue(firstQueue);

  

    // Шаг 3.c: Иначе, сравнить начало двух очередей и минимум очереди

    if (getFront(firstQueue)->freq < getFront(secondQueue)->freq)

        return deQueue(firstQueue);

  

    return deQueue(secondQueue);

}

  
// Сервисная функция, чтобы проверить, является ли этот узел листом

int isLeaf(struct QueueNode* root)

{

    return !(root->left) && !(root->right) ;

}

  
// Вспомогательная функция для печати массива размера n

void printArr(int arr[], int n)

{

    int i;

    for (i = 0; i < n; ++i)

        printf("%d", arr[i]);

    printf("\n");

}

  
// Основная функция, которая строит дерево Хаффмана

struct QueueNode* buildHuffmanTree(char data[], int freq[], int size)

{

    struct QueueNode *left, *right, *top;

  

    // Шаг 1: Создать две пустые очереди

    struct Queue* firstQueue  = createQueue(size);

    struct Queue* secondQueue = createQueue(size);

  

    // Шаг 2: Создать листовой узел для каждого уникального символа и поставить его в очередь

    // первая очередь в порядке убывания частоты. Изначально второй

    // очередь пуста

    for (int i = 0; i < size; ++i)

        enQueue(firstQueue, newNode(data[i], freq[i]));

  

    // Выполнить, пока очереди содержат более одного узла. Наконец, первая очередь будет

    // быть пустым и вторая очередь будет содержать только один узел

    while (!(isEmpty(firstQueue) && isSizeOne(secondQueue)))

    {

        // Шаг 3: вывести из очереди два узла с минимальной частотой, исследуя

        // фронт обеих очередей

        left = findMin(firstQueue, secondQueue);

        right = findMin(firstQueue, secondQueue);

  

        // Шаг 4: Создать новый внутренний узел с частотой, равной сумме

        // частот двух узлов. Поставьте этот узел во вторую очередь.

        top = newNode('$' , left->freq + right->freq);

        top->left = left;

        top->right = right;

        enQueue(secondQueue, top);

    }

  

    return deQueue(secondQueue);

}

  
// Печатает коды Хаффмана из корня дерева Хаффмана. Он использует arr [] для
// хранить коды

void printCodes(struct QueueNode* root, int arr[], int top)

{

    // Присваиваем 0 левому краю и повторяем

    if (root->left)

    {

        arr[top] = 0;

        printCodes(root->left, arr, top + 1);

    }

  

    // Назначаем 1 правому краю и повторяем

    if (root->right)

    {

        arr[top] = 1;

        printCodes(root->right, arr, top + 1);

    }

  

    // Если это листовой узел, то он содержит один из входных

    // символы, вывести символ и его код из arr []

    if (isLeaf(root))

    {

        printf("%c: ", root->data);

        printArr(arr, top);

    }

}

  
// Основная функция, которая строит дерево Хаффмана и печатает коды путем обхода
// построенное дерево Хаффмана

void HuffmanCodes(char data[], int freq[], int size)

{

   // Построить дерево Хаффмана

   struct QueueNode* root = buildHuffmanTree(data, freq, size);

  

   // Печатать коды Хаффмана, используя построенное выше дерево Хаффмана

   int arr[MAX_TREE_HT], top = 0;

   printCodes(root, arr, top);

}

  
// Программа драйвера для проверки вышеуказанных функций

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;

}


Выход:

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

Временная сложность: O (n)

Если входные данные не отсортированы, они должны быть отсортированы в первую очередь, прежде чем они могут быть обработаны с помощью вышеуказанного алгоритма. Сортировка может быть выполнена с использованием сортировки кучи или сортировки слиянием, которые выполняются в Theta (nlogn). Таким образом, общая сложность времени становится O (nlogn) для несортированного ввода.

Ссылка:
http://en.wikipedia.org/wiki/Huffman_coding

Эта статья составлена Aashish Barnwal и рецензирована командой GeeksforGeeks. Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Эффективное кодирование Хаффмана для отсортированного ввода | Жадный Алго-4

0.00 (0%) 0 votes