전달하고 싶은 메시지가 있습니다. 우리는 메시지를 보내는 데 드는 비용을 낮출 수 있도록 메시지의 크기를 최대한 작게 만들고 싶습니다. 여기서 우리는 메시지의 크기를 줄이기 위해 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)입니다.