허프만 코딩

난이도 중급
자주 묻는 질문 아마존 블룸버그 게시물에서 구글 모건 스탠리 (Morgan Stanley) 삼성 UHG 옵텀
인코딩-디코딩 탐욕스러운 해시 해싱 수학조회수 63

전달하고 싶은 메시지가 있습니다. 우리는 메시지를 보내는 데 드는 비용을 낮출 수 있도록 메시지의 크기를 최대한 작게 만들고 싶습니다. 여기서 우리는 메시지의 크기를 줄이기 위해 Huffman Coding 개념을 사용합니다.

다음 데이터가 있다고 가정 해 봅시다.

  • 요청사항:BCCABBDDABCCBBAEDDCC
  • 각 문자는 ASCII 값 (8 비트)으로 표시됩니다.
  • 메시지 비용 = 한 문자를 통해 보내는 비용 X 메시지 길이

허프만 코딩에 대한 설명

따라서 메시지의 크기는 = (8x20) = 160 비트입니다. 위의 메시지는 인코딩없이 간단하게 전송되어 비용이 많이 듭니다.

8 비트 (5 개의 조합)로 표현할 수있는 3 개의 고유 문자 만있을 때 8 비트 표현을 사용합니다.

아래 표는 3 비트 만 사용할 때의 각 문자와 그 표현을 보여줍니다.

A 000
B 001
C 010
D 011
E 100

발생하는 비용은 이제 20x3 = 60 비트로 줄어들지 만 암호화 된 메시지는 해독하기가 어려우므로 위의 표와 함께 전송해야하므로 총 비용이 15 비트가되므로 추가로 115 비트가 필요합니다.

위의 방법은 각 문자에 대해 고정 크기 코드를 사용합니다. 이것이 허프만 방법이 등장하는 곳입니다. 다음은 프로세스 요약입니다.

  • 카운트 오름차순으로 알파벳 정렬
  • 두 개의 작은 노드를 병합하여 새 노드를 만듭니다.

프로세스를 단계별로 살펴 보겠습니다.

Step1 : 각 알파벳에 대한 노드를 만들고 빈도별로 정렬

허프만 코딩

Step2 : 빈도가 가장 낮은 두 노드를 병합합니다. 부모 노드의 값은 두 노드의 값의 합이됩니다.

허프만 코딩

이진 트리를 얻을 때까지 두 번째 단계를 계속 반복합니다.

허프만 코딩

모든 노드를 병합 한 후 얻은 트리

이제 모든 알파벳에 대한 인코딩을 얻습니다.

  • 좌회전 할 때마다 표현에 0을 추가합니다.
  • 우회전 할 때마다 표현에 1을 추가합니다.

아래 표는 얻은 코드를 나열합니다.

A 000
B 10
C 11
D 01
E 001

이제 크기가 52 비트로 줄어들어 비용이 상당히 절감됩니다.

이제 프로세스를 이해 했으므로 동일한 구현을 살펴 보겠습니다.

Huffman 코딩을위한 자바 프로그램

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 코딩을위한 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

복잡성 분석

시간 복잡성을 살펴 보겠습니다.

각 노드를 최소로 힙화하는 데 걸리는 시간더미: log (n)

노드 수 : n

따라서 소요 시간은 O (n log n)입니다.

참조

Translate »