Huffman Kodlaşdırma

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Bloomberg google Morgan Stanley Samsung UHG Optum
Kodlaşdırma-dekodlaşdırma Görməmiş Sükut Hashing RiyaziyyatBaxılıb 41

Çatdırmaq istədiyimiz bir mesaj var. Mesajın mümkün qədər kiçik olmasını istəyirik ki, mesajın göndərilməsində çəkilən xərclər az olsun. Burada mesajın ölçüsünü azaltmaq üçün Huffman Kodlaşdırma konsepsiyasından istifadə edirik.

Gəlin aşağıdakı məlumatlara sahib olduğumuzu düşünək

  • Mesaj:BCCABBDDABCCBBAEDDCC
  • Hər bir simvol ASCII dəyəri ilə təmsil olunur (8 bit)
  • Mesajın dəyəri = Bir simvol üzərində göndərmə dəyəri X Mesajın uzunluğu

Huffman Kodlamasına dair açıqlama

Beləliklə, mesajın ölçüsü = (8 × 20) = 160 bit. Yuxarıdakı mesaj hər hansı bir kodlaşdırma olmadan sadəcə baha başa gələn şəkildə göndərilir və biz

yalnız 8 bit (5 kombinasiya) ilə təmsil oluna bilən 3 fərqli simvol olduğumuz zaman 8 bitlik bir nümayəndəlikdən istifadə edirik.

Aşağıdakı cədvəldə hər bir simvol və yalnız 3 bit istifadə etdiyimiz zaman təmsil olunur.

A 000
B 001
C 010
D 011
E 100

Görünən odur ki, indi çəkilən xərc 20 × 3 = 60 bitə qədər azalır, lakin şifrələnmiş mesajı deşifr etmək çətin olacaq və bununla da yuxarıdakı cədvəllə göndərilməlidir ki, bu da ümumi dəyəri 15 bit olan 115 bitə başa gələcək.

Yuxarıda göstərilən metod hər bir simvol üçün sabit ölçülü koddan istifadə edir. Huffman metodunun şəkilə gəldiyi yer budur. Aşağıda prosesin xülasəsi verilmişdir

  • Əlifbaları sayın artan qaydasında düzəldin
  • Yeni bir qovşaq yaratmaq üçün iki kiçik qovşaqları birləşdirin

Prosesi addım-addım nəzərdən keçirək:

Step1: Hər bir əlifba üçün bir qovşaq yaradın və tezliklərinə görə sıralayın

Huffman Kodlaşdırma

Step2: Ən az tezliklə iki qovşaq birləşdirin. Ana qovşaq dəyəri hər iki qovşaqdan alınan dəyərlərin cəmi olacaqdır

Huffman KodlaşdırmaPin

İkili ağacı əldə edənə qədər ikinci addımı təkrarlayırıq.

Huffman KodlaşdırmaPin

Pin

Bütün qovşaqları birləşdirdikdən sonra əldə edilən ağac

Pin

İndi bütün əlifbalar üçün kodlaşdırmanı əldə edək

  • Hər dəfə sola dönəndə nümayəndəliyə 0 əlavə edin
  • Hər dəfə sağa dönəndə nümayəndəliyə 1 əlavə edin

Aşağıdakı cədvəldə alınan kodlar verilmişdir

A 000
B 10
C 11
D 01
E 001

Ölçü indi 52 bitə qədər azalır ki, bu da maliyyədə xeyli azalma deməkdir.

Artıq prosesi başa düşdüyümüz üçün tətbiqetməyə də nəzər salaq.

Huffman Kodlama üçün Java Proqramı

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,"");
}
}

Huffman Kodlaşdırma üçün C ++ Proqramı

#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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyinə baxaq:

Hər bir düyünün minimuma qədər yığılması üçün sərf olunan vaxtyığın: giriş (n)

Düyünlərin sayı: n

Beləliklə çəkilən vaxt O (n log n) olacaqdır

References

Translate »