ሃፍማን ኮድ ማድረጊያ


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን ብሉምበርግ google ሞርጋን ስታንሊ ሳምሰንግ UHG Optum
ኢንኮዲንግ-ዲኮዲንግ ስስታም ሃሽ ሃምሽንግ ሒሳብ

ማድረስ የምንፈልገው መልእክት አለን ፡፡ መልዕክቱን ለመላክ የተከሰቱት ወጭዎች ዝቅተኛ እንዲሆኑ መልዕክቱ በተቻለ መጠን አነስተኛ እንዲሆን እንፈልጋለን ፡፡ እዚህ የመልእክቱን መጠን ለመቀነስ የሃፍማን ኮዲንግ ፅንሰ-ሀሳብ እንጠቀማለን ፡፡

የሚከተለው መረጃ እንዳለን እናስብ

  • መልዕክት:ብሲካብድዳቢሲሲ ብባህደዲሲ
  • እያንዳንዱ ቁምፊ በ 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 ቢት ያስከፍለናል ፡፡

ከላይ ያለው ዘዴ ለእያንዳንዱ ቁምፊ ቋሚ መጠን ያለው ኮድ ይጠቀማል። የሃፍማን ዘዴ ወደ ምስሉ የሚመጣው እዚህ ነው ፡፡ ከዚህ በታች የሂደቱ ማጠቃለያ ነው

  • የቁጥር ቅደም ተከተል በመጨመር ፊደላትን ያዘጋጁ
  • አዲስ መስቀለኛ መንገድ ለመፍጠር ሁለት ትናንሽ አንጓዎችን ያዋህዱ

እስቲ የሂደቱን ደረጃ በደረጃ እንመልከት-

ደረጃ 1: ለእያንዳንዱ ፊደል መስቀለኛ ክፍል ይፍጠሩ እና በድግግሞቻቸው ያስተካክሉዋቸው

ሃፍማን ኮድ ማድረጊያ

ደረጃ 2: ሁለት አንጓዎችን በትንሹ ድግግሞሽ ያዋህዱ። የወላጅ መስቀለኛ መንገድ እሴት ከሁለቱም አንጓዎች የእሴቶች ድምር ይሆናል

ሃፍማን ኮድ ማድረጊያ

የሁለትዮሽ ዛፍ እስክናገኝ ድረስ ሁለተኛውን ደረጃ መደገሙን እንቀጥላለን።

ሃፍማን ኮድ ማድረጊያ

ሁሉንም አንጓዎች ከተቀላቀለ በኋላ የተገኘው ዛፍ

ለሁሉም ፊደላት አሁን ኢንኮዲንግን እናገኝ

  • ወደ ግራ በሚዞሩ ቁጥር 0 ወደ ተወካዩ XNUMX ያክሉ
  • ወደ ቀኝ በሚዞሩ ቁጥር 1 ወደ ውክልናው XNUMX ያክሉ

ከዚህ በታች ያለው ሰንጠረዥ የተገኙትን ኮዶች ይዘረዝራል

A 000
B 10
C 11
D 01
E 001

መጠኑ አሁን ወደ 52 ቢቶች ይቀነሳል ይህ ደግሞ የወጪ ቅናሽ ነው ፡፡

አሁን ሂደቱን ስለ ተረዳነው ለተግባራዊነቱ ወደዚያው እንመልከት ፡፡

የጃቫ ፕሮግራም ለሃፍማን ኮዲንግ

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

ስለዚህ የተወሰደው ጊዜ ኦ (n log n) ይሆናል

ማጣቀሻዎች