Кодирование Хаффмана


Сложный уровень средний
Часто спрашивают в Амазонка Bloomberg Google Morgan Stanley Samsung UHG Optum
Кодирование-декодирование Жадный Hash хеширования Экзамен Математики

У нас есть сообщение, которое мы хотим доставить. Мы хотим, чтобы сообщение было минимально возможного размера, чтобы затраты на его отправку были низкими. Здесь мы используем концепцию кодирования Хаффмана, чтобы уменьшить размер сообщения.

Предположим, что у нас есть следующие данные

  • Сообщение:BCCABBDDABCCBBAEDDCC
  • Каждый символ представлен своим значением ASCII (8 бит)
  • Стоимость сообщения = Стоимость отправки одного символа X Длина сообщения

Объяснение кодирования Хаффмана

Таким образом, размер сообщения = (8 × 20) = 160 бит. Сообщение выше отправлено просто без кодирования, что делает его дорогостоящим, и мы

используя 8-битное представление, когда у нас есть только 5 различных символов, которые могут быть представлены только 3 битами (8 комбинаций).

В приведенной ниже таблице показаны каждый символ и их представление, когда мы используем только 3 бита.

A 000
B 001
C 010
D 011
E 100

Похоже, что понесенные затраты теперь сокращаются до 20 × 3 = 60 бит, но зашифрованное сообщение будет трудно расшифровать и, следовательно, его также придется отправлять с приведенной выше таблицей, что будет стоить нам еще 15 бит, что составит общую стоимость 115 бит.

Вышеупомянутый метод использует код фиксированного размера для каждого символа. Здесь на помощь приходит метод Хаффмана. Ниже приводится краткое изложение процесса

  • Расставьте алфавиты в порядке возрастания счета
  • Объедините два небольших узла, чтобы сформировать новый узел

Давайте рассмотрим процесс шаг за шагом:

Step1: Создайте узел для каждого алфавита и отсортируйте их по частоте

Кодирование Хаффмана

Step2: Объединяйте два узла с наименьшей частотой. Значение родительского узла будет суммой значений от обоих узлов.

Кодирование Хаффмана

Продолжаем повторять второй шаг, пока не получим двоичное дерево.

Кодирование Хаффмана

Дерево, полученное после объединения всех узлов

Давайте теперь получим кодировку для всех алфавитов

  • Добавляйте 0 к изображению каждый раз, когда поворачиваете налево
  • Добавляйте 1 к изображению каждый раз, когда поворачиваете направо

В таблице ниже перечислены полученные коды.

A 000
B 10
C 11
D 01
E 001

Теперь размер уменьшается до 52 бит, что значительно снижает стоимость.

Теперь, когда мы разобрались с процессом, давайте рассмотрим его реализацию.

Программа Java для кодирования Хаффмана

import java.util.*;
//Node will represent all the letters with their frequency
class Node
{
  int data;
  char c;
  Node left;
  Node right;
}
class compare implements Comparator<Node>
{
public int compare(Node a,Node b)
{
  return a.data-b.data;
}
}
public class huffman
{
public static void construct(Node root,String s)
{
  //Identifying a root node
  if(root.left==null && root.right==null && Character.isLetter(root.c))
  {
  System.out.println(root.c+":"+s);
  return;
  }
  //Every time we turn left we add a zero to the code representation
  construct(root.left,s+"0");
  //Every time we turn right we add a one to the code representation
  construct(root.right,s+"1");
}
public static void main(String args[])
{
  int n=6;
  char[] message= { 'a', 'b', 'c', 'd', 'e' }; 
     int[] frequen= { 5, 5, 5, 4, 1 }; 
    //Putting our data in min-priority queue
    PriorityQueue<Node>q=new PriorityQueue<Node>(n,new compare());
    for(int i=0;i<n;i++)
    {
    	Node s=new Node();
    	s.c   =message[i];
    	s.data=frequen[i];
    	s.left=null;
    	s.right=null;
    	q.add(s);
    }
    Node root=null;
    //Extracting the sorted nodes from the queue
    //Emptying until all we have is the root node
    while(q.size()>1)
    {
    	//Right for our root
    	Node rht=q.poll();
    	//Left for our root
    	Node lft=q.poll();
    	Node temp=new Node();
    	//Root will have the sum of data from both left and right
    	temp.data=rht.data+lft.data;
    	temp.c='-';
    	temp.left =lft;
    	temp.right=rht;
    	root=temp;
    	//Adding this to the queue to build up higher levels of the tree
    	q.add(temp);
    }
    construct(root,"");
}
}

Программа C ++ для кодирования Хаффмана

#include <iostream> 
using namespace std; 
#define MAX_TREE_HT 100  
struct MinHeapNode 
{  
    char data; 
    int freq;  
    struct MinHeapNode *left, *right; 
}; 
 
struct MinHeap 
{  
    unsigned size;  
    unsigned capacity;  
    struct MinHeapNode** array; 
}; 
  
struct MinHeapNode* newNode(char data, unsigned freq) 
{ 
    struct MinHeapNode* temp  = (struct MinHeapNode*)malloc(sizeof(struct MinHeapNode)); 
    temp->left = temp->right = NULL; 
    temp->data = data; 
    temp->freq = freq; 
    return temp; 
} 

struct MinHeap* createMinHeap(unsigned capacity)  
{ 
    struct MinHeap* minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap)); 
    minHeap->size = 0; 
    minHeap->capacity = capacity; 
minHeap->array=(struct MinHeapNode**)malloc(minHeap-> capacity * sizeof(struct MinHeapNode*)); 
    return minHeap; 
} 

void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b) 
{ 
    struct MinHeapNode* t = *a; 
    *a = *b; 
    *b = t; 
} 

void minHeapify(struct MinHeap* minHeap, int idx)   
{ 
    int smallest = idx; 
    int left = 2 * idx + 1; 
    int right = 2 * idx + 2; 
    if (left < minHeap->size && minHeap->array[left]-> freq<minHeap->array[smallest]->freq) 
        smallest = left; 
  
    if (right < minHeap->size && minHeap->array[right]->freq<minHeap->array[smallest]->freq) 
        smallest = right; 
  
    if (smallest != idx) 
    { 
        swapMinHeapNode(&minHeap->array[smallest], 
                        &minHeap->array[idx]); 
        minHeapify(minHeap, smallest); 
    } 
} 
int isSizeOne(struct MinHeap* minHeap) 
{ 
  
    return (minHeap->size == 1); 
} 

struct MinHeapNode* extractMin(struct MinHeap* minHeap)  
{ 
  
    struct MinHeapNode* temp = minHeap->array[0]; 
    minHeap->array[0] = minHeap->array[minHeap->size - 1]; 
    --minHeap->size; 
    minHeapify(minHeap, 0); 
    return temp; 
} 
  
 
void insertMinHeap(struct MinHeap* minHeap, struct MinHeapNode* minHeapNode)   
{ 
  
    ++minHeap->size; 
    int i = minHeap->size - 1; 
    while (i && minHeapNode->freq<minHeap->array[(i - 1) / 2]->freq) 
    { 
        minHeap->array[i] = minHeap->array[(i - 1) / 2]; 
        i = (i - 1) / 2; 
    } 
    minHeap->array[i] = minHeapNode; 
} 
  

void buildMinHeap(struct MinHeap* minHeap)   
{ 
    int n = minHeap->size - 1; 
    int i;
    for (i = (n - 1) / 2; i >= 0; --i) 
        minHeapify(minHeap, i); 
} 
 
void printArr(int arr[], int n) 
{ 
    int i; 
    for (i = 0; i < n; ++i) 
        cout<< arr[i]; 
  
    cout<<"\n"; 
} 

int isLeaf(struct MinHeapNode* root) 
  
{  
    return !(root->left) && !(root->right); 
} 
  
 
struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size)   
{ 
    struct MinHeap* minHeap = createMinHeap(size); 
    for (int i = 0; i < size; ++i) 
        minHeap->array[i] = newNode(data[i], freq[i]); 
  
    minHeap->size = size; 
    buildMinHeap(minHeap); 
  
    return minHeap; 
} 

struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) 
  
{ 
    struct MinHeapNode *left, *right, *top; 
    struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size); 
    while (!isSizeOne(minHeap)) 
    { 
        left = extractMin(minHeap); 
        right = extractMin(minHeap); 
        top = newNode('$', left->freq + right->freq); 
  
        top->left = left; 
        top->right = right; 
  
        insertMinHeap(minHeap, top); 
    } 
    return extractMin(minHeap); 
} 
void printCodes(struct MinHeapNode* 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 (isLeaf(root)) { 
  
        cout<< root->data <<": "; 
        printArr(arr, top); 
    } 
} 
void HuffmanCodes(char data[], int freq[], int size) 
  
{ 
    // Construct Huffman Tree 
    struct MinHeapNode* 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' }; 
    int freq[] = { 5, 9, 12, 13, 16}; 
  
    int size = sizeof(arr) / sizeof(arr[0]); 
  
    HuffmanCodes(arr, freq, size); 
  
    return 0; 
}
c: 00
d: 01
a: 100
b: 101
e: 11

Анализ сложности

Давайте посмотрим на временную сложность:

Время, затрачиваемое на нагромождение каждого узла до минимума.куча: журнал (n)

Количество узлов: n

Таким образом, затраченное время будет O (n log n)

дело