Huffman Algorithm에 대해서

본문의 내용은 제가 찾은 블로그의 내용을 해석해서 올리는 것입니다.

Huffman 는 비손실 데이터 압축을 위해 사용되는 압축 알고리즘이다. 여기에는 밑바탕이 되는 이론이 있다. 

각각의 ASCII 코드는 항상 8비트와 함께 표현되는데, 만약 우리가 a에서 z까지의 문자로만 이루어진 자료를 가지고 있다면

우리는 알파벳 문자를 5비트로 표현할 수 있다. 2^5 =32이므로 이것은 26개의 문자를 표현하기에 충분하다.

그래서 일반적으로 데이터를 저장하려는 메모리를 줄일 수 있다.

예를 들어 코드들이 있다. -> 바이너리 코드는 아래와 같이 충분히 표현 가능하다.

a = 00000

b = 00001

c = 00010

d = 00011

e = 00100

좀 더 효울적인 접근은 다양한 길이를 사용하는 것이다. 여기서 다양한 길이는 비트 수를 의미한다. 

즉 각각의 문자를 표현하기 위해 비트의 수를 다르게 갖게 하는 것이다. 좀더 특별하게 처음 우리는 자료에서 문자의 빈도수를 알아내고, 

이것을 이용해 우리는 자주 사용되는 문자들은 짧은 비트를 갖는 바이너리 트리(이것을 Huffman tree라 한다.)를 만든다. 

예를 들어 영어 단어에서 문자들의 빈도수는 아래와 같다.

허프만 트리를 이용해서  모든 문자들을 표현하는 바이너리 코드 표를 만들 수 있다. 표는 아래와 같다.

a = 0011

b = 011011 c = 11111 d = 00100 e = 101 f = 000010 g = 011001 h = 1110 i = 0101 j = 011010101 k = 0110101001 l = 00101 m = 000001 n = 0111 o = 0100 p = 011000 q = 0110101000 r = 1101 s = 1100 t = 0001 u = 11110 v = 0110100 w = 000000 x = 011010111 y = 000011 z = 011010110 space = 100

아래의 코드는 Huffman Algorithm 이다.

#include <stdio.h> #include <stdlib.h> #include <math.h> #define len(x) ((int)log10(x)+1) /* Node of the huffman tree */ struct node{     int value;     char letter;     struct node *left,*right; }; typedef struct node Node; /* 81 = 8.1%, 128 = 12.8% and so on. The 27th frequency is the space. Source is Wikipedia */ int englishLetterFrequencies [27] = {81, 15, 28, 43, 128, 23, 20, 61, 71, 2, 1, 40, 24, 69, 76, 20, 1, 61, 64, 91, 28, 10, 24, 1, 20, 1, 130}; /*finds and returns the small sub-tree in the forrest*/ int findSmaller (Node *array[], int differentFrom){     int smaller;     int i = 0;     while (array[i]->value==-1)         i++;     smaller=i;     if (i==differentFrom){         i++;         while (array[i]->value==-1)             i++;         smaller=i;     }     for (i=1;i<27;i++){         if (array[i]->value==-1)             continue;         if (i==differentFrom)             continue;         if (array[i]->value<array[smaller]->value)             smaller = i;     }     return smaller; } /*builds the huffman tree and returns its address by reference*/ void buildHuffmanTree(Node **tree){     Node *temp;     Node *array[27];     int i, subTrees = 27;     int smallOne,smallTwo;     for (i=0;i<27;i++){         array[i] = malloc(sizeof(Node));         array[i]->value = englishLetterFrequencies[i];         array[i]->letter = i;         array[i]->left = NULL;         array[i]->right = NULL;     }     while (subTrees>1){         smallOne=findSmaller(array,-1);         smallTwo=findSmaller(array,smallOne);         temp = array[smallOne];         array[smallOne] = malloc(sizeof(Node));         array[smallOne]->value=temp->value+array[smallTwo]->value;         array[smallOne]->letter=127;         array[smallOne]->left=array[smallTwo];         array[smallOne]->right=temp;         array[smallTwo]->value=-1;         subTrees--;     }     *tree = array[smallOne]; return; } /* builds the table with the bits for each letter. 1 stands for binary 0 and 2 for binary 1 (used to facilitate arithmetic)*/ void fillTable(int codeTable[], Node *tree, int Code){     if (tree->letter<27)         codeTable[(int)tree->letter] = Code;     else{         fillTable(codeTable, tree->left, Code*10+1);         fillTable(codeTable, tree->right, Code*10+2);     }     return; } /*function to compress the input*/ void compressFile(FILE *input, FILE *output, int codeTable[]){     char bit, c, x = 0;     int n,length,bitsLeft = 8;     int originalBits = 0, compressedBits = 0;     while ((c=fgetc(input))!=10){         originalBits++;         if (c==32){             length = len(codeTable[26]);             n = codeTable[26];         }         else{             length=len(codeTable[c-97]);             n = codeTable[c-97];         }         while (length>0){             compressedBits++;             bit = n % 10 - 1;             n /= 10;             x = x | bit;             bitsLeft--;             length--;             if (bitsLeft==0){                 fputc(x,output);                 x = 0;                 bitsLeft = 8;             }             x = x << 1;         }     }     if (bitsLeft!=8){         x = x << (bitsLeft-1);         fputc(x,output);     }     /*print details of compression on the screen*/     fprintf(stderr,"Original bits = %dn",originalBits*8);     fprintf(stderr,"Compressed bits = %dn",compressedBits);     fprintf(stderr,"Saved %.2f%% of memoryn",((float)compressedBits/(originalBits*8))*100);     return; } /*function to decompress the input*/ void decompressFile (FILE *input, FILE *output, Node *tree){     Node *current = tree;     char c,bit;     char mask = 1 << 7;     int i;     while ((c=fgetc(input))!=EOF){         for (i=0;i<8;i++){             bit = c & mask;             c = c << 1;             if (bit==0){                 current = current->left;                 if (current->letter!=127){                     if (current->letter==26)                         fputc(32, output);                     else                         fputc(current->letter+97,output);                     current = tree;                 }             }             else{                 current = current->right;                 if (current->letter!=127){                     if (current->letter==26)                         fputc(32, output);                     else                         fputc(current->letter+97,output);                     current = tree;                 }             }         }     }     return; } /*invert the codes in codeTable2 so they can be used with mod operator by compressFile function*/ void invertCodes(int codeTable[],int codeTable2[]){     int i, n, copy;     for (i=0;i<27;i++){         n = codeTable[i];         copy = 0;         while (n>0){             copy = copy * 10 + n %10;             n /= 10;         }         codeTable2[i]=copy;     } return; } int main(){     Node *tree;     int codeTable[27], codeTable2[27];     int compress;     char filename[20];     FILE *input, *output;     buildHuffmanTree(&tree);     fillTable(codeTable, tree, 0);     invertCodes(codeTable,codeTable2);     /*get input details from user*/     printf("Type the name of the file to process:n");     scanf("%s",filename);     printf("Type 1 to compress and 2 to decompress:n");     scanf("%d",&compress);     input = fopen(filename, "r");     output = fopen("output.txt","w");     if (compress==1)         compressFile(input,output,codeTable2);     else         decompressFile(input,output, tree);     return 0; }

<출처 : http://www.programminglogic.com/implementing-huffman-coding-in-c/ >