nlogn's log :: 천천히 달리기

Compressed/Decompressed Files Software

 

사용자로부터 주어진 텍스트 파일을 압축하고 반대로 압축된 파일은 압축을 푸는 프로그램으로 호프만 알고리즘(Huffman Code Algorithm)을 이용하여 호프만 테이블을 작성한다.

작성된 호프만 테이블로 입력된 텍스트 파일을 하나의 버퍼에 저장 후 파일에 출력 파일에 출력할 때 호프만 코드를 같이 출력한다.

파일 압축을 풀 때 하나의 버퍼에 파일의 내용을 저장 후 현재 프로그램의 버전과의 일치 여부와 코드 파일의 내용을 비교하면서 압축을 푼다.

참고로, 파일 압축시 50~75%정도 나온다.

 

 

특수문자, Multi Byte Code, 대용량 파일 처리를 하지 않았으니 참고하세요.

 

// 사용 방법

 

압축 할때

실행파일명 -e[E] text.txt output.txt

 

압축 풀때

실행파일명 -d[D] output.txt text.txt

 

/////////////////// 소스 코드 ////////////////////////////////

 

//********************************************

Version 1.0, October 2002.

Copyright(C) aroma_guy 

http://blog.naver.com/aroma_guy

 

Everyone is permitted to copy, modify or distribute this codes.

***********************************************//

 

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

 

#define VERSION                       1.0

#define MAX_SIZE                      256

#define CHARBITS                      8

#define MAX_CODE_LENGTH               16

#define MAX_CODE_NUMBER               256

#define MAX_STRING_LENGTH             1024*100       // maximum size of compressed file is 100 kbyte

#define MAX_BIT_MASK_NUMBER           8

#define RIGHTBITS(n, x) ((x) & ((1U << (n)) - 1U))

 

typedef struct code_tag

{

        int                    ascii;

        char                   code[MAX_CODE_LENGTH];

        int                    lengthOfCode;

        unsigned               frequency;

} CODE;

 

int HuffmanCodeTable(CODE codeTable[]);

void SetCode(CODE codeTable[], int cnt);

int EncryptString(char original_string[],

          int length_Of_Original_string,

          CODE codeTable[], int cnt_of_Codes,

          char encoded_String[]);

void WriteBitString(char encoded_String[],

          int cnt_Of_EncodedBits);

int DecryptBitString(char encoded_String[],

          int cnt_Of_EncodeBit,

          CODE codeTable[], int cnt_Of_Codes,

          char decoded_String[]);

int SearchAlphabet(char key, CODE codeTable[],

          int cnt_Of_Codes);

void AttachCode(char encoded_String[], int cnt_Of_Bits,

          char code[], int lengthOfCode);

int SearchCode(char key[], CODE codeTable[], int cnt_Of_Codes);

void WriteInFile(char encoded_String[],int cnt_Of_EncodedBits,

          CODE codeTable[], int cnt_of_codes);

void PrnFreq(CODE codeTable[], int cnt_of_codes);

void Error(char *msg);

void DownHeap(int i);

void GetTableSizeAndCodeBits(int *size_of_table,

                             int  *cnt_Of_EncodeBit);

int GetVersion();

void GetCodeTable(CODE codeTable[], int cnt_of_codes);

void GetCode(char encoded_string[]);

void PrnCodeTable(CODE codeTable[], int cnt_of_codes);

void WriteDecodedBit(char decoded_String[]);

 

char bitMask_OR[MAX_BIT_MASK_NUMBER];

char bitMask_AND[MAX_BIT_MASK_NUMBER];

int heap_size, heap[2*MAX_SIZE-1], parent[2*MAX_SIZE-1], left[2*MAX_SIZE-1], right[2*MAX_SIZE-1];

unsigned long int frequency[2*MAX_SIZE-1];

FILE *ifp, *ofp;

 

int main(int argc, char *argv[])

{

        int i, j = 0;

        char Original_String[MAX_STRING_LENGTH];

        char encoded_String[MAX_STRING_LENGTH];

        char decoded_String[MAX_STRING_LENGTH];

              int lengthOfDecodedString;

        int cnt_Of_EncodedBits = 0;

        CODE codeTable[MAX_CODE_NUMBER];

        int cnt_Of_Codes = 0;

        char option;

       

        if(argc != 4 || ((option = *argv[1]) != 'e'

                       && option != 'E'

                       && option != 'd' && option != 'D'))

        {

               printf("Usage : %s [e or E|d or D] input_file

                   output_file\n", argv[0]);

               exit(1);

        }

              

        ifp = fopen(argv[2], "rb");

        if(ifp == NULL)

        {

               printf("Cannot open file : %s", argv[2]);

               exit(1);

        }

 

        ofp = fopen(argv[3], "wb");

        if(ofp == NULL)

        {

               printf("Cannot open file : %s", argv[3]);

               exit(1);

        }

       

        for(i=0; i < 8; i++)

        {

               bitMask_OR[i] = 1 << (7-i);

               bitMask_AND[i] = bitMask_OR[i] ^ 0xff;

        }

 

        if(option == 'e' || option == 'E')

        {

               while((i = getc(ifp)) != EOF)

               {

                       Original_String[j++] = i;

                       if(j >= MAX_STRING_LENGTH)

                              Error("Error : larger than

                                     100kbyte!\n");

               }

               Original_String[j]='\0';

               rewind(ifp);

               cnt_Of_Codes = HuffmanCodeTable(codeTable);

               cnt_Of_EncodedBits = EncryptString(

                     Original_String, strlen(Original_String),

                     codeTable, cnt_Of_Codes, encoded_String);

               WriteInFile(encoded_String, cnt_Of_EncodedBits,

                     codeTable, cnt_Of_Codes);

 

        }

        else

        {

               if(GetVersion())

                       Error("Error : The file isn't equivalent

                           the current program version!\n");

               

               GetTableSizeAndCodeBits(&cnt_Of_Codes,

                             &cnt_Of_EncodedBits);

               GetCodeTable(codeTable, cnt_Of_Codes);

               GetCode(encoded_String);

               lengthOfDecodedString = DecryptBitString(

                      encoded_String, cnt_Of_EncodedBits,

                      codeTable, cnt_Of_Codes, decoded_String);

               WriteDecodedBit(decoded_String);

        }

        fclose(ifp);

        fclose(ofp);

        return 0;

}

 

int GetVersion()

{             

        int i, j = 0;

        char buffer[10];

              

        while((i = getc(ifp)) != EOF && j < 3)

        {

               buffer[j++] = i;

               if(j >= MAX_STRING_LENGTH)

                    Error("Error : larger than 100kbyte!\n");

        }

       

        if(atof(buffer) == VERSION)

               return 0;

        else

               return -1;

}

 

/*************************************************************

 * 호프만 테이블 사이즈와 비트의 수 얻기

 *  

 *************************************************************/

void GetTableSizeAndCodeBits(int *size_of_table, int *cnt_Of_EncodeBit)

{

        int ch, i = 0;

        char buffer[10];

 

        while((ch = getc(ifp)) != EOF && ch != 0x2F)

               buffer[i++] = ch;

        buffer[i] = '\0';

        *size_of_table = atoi(buffer);

        i = 0;

        while((ch = getc(ifp)) != EOF && ch != 0x20)

               buffer[i++] = ch;

        *cnt_Of_EncodeBit = atoi(buffer);

        return;

}

 

/*************************************************************

 * 호프만 코드 테이블을 메모리에 저장

 *

 *************************************************************/

void GetCodeTable(CODE codeTable[], int cnt_of_codes)

{

        int i = 0, j = 0, tmp, is_block = 0;

       

        while((tmp = getc(ifp)) != EOF || i < cnt_of_codes)

        {

               if(!is_block && tmp != '0' && tmp != '1')

               {

                       codeTable[i].ascii = tmp;

               }

               else if(tmp == '0' || tmp == '1')

               {

                       is_block = 1;

                       codeTable[i].code[j++] = tmp;

                       continue;

               }

               else if(is_block && tmp != '0' && tmp != '1')

               {

                       codeTable[i].code[j] = '\0';

                       is_block = 0, j = 0;

                       if(cnt_of_codes == ++i)

                              break;

                       codeTable[i].ascii = tmp;

               }

        }

        PrnCodeTable(codeTable, cnt_of_codes);

}

 

/*************************************************************

 * 호프만 코드로 작성된 내용을 버퍼에 저장

 *

 *************************************************************/

void GetCode(char encoded_string[])

{

        int ch, i = 0;

 

        while((ch = getc(ifp)) != EOF)

        {

               encoded_string[i++] = ch;

               if(i >= MAX_STRING_LENGTH)

                      Error("Error : larger than 100kbyte!\n");

        }

        encoded_string[i] = '\0';

       

}

 

void Error(char *msg)

{

        printf("%s", msg);

        exit(1);

}

 

void PrnFreq(CODE codeTable[], int cnt_of_codes)

{

        int i, k = 0, size = 0;

       

        printf("텍스트 분석 중...\n");

        printf("---------------------------------\n");

        printf("alphabet\tfrequency\n");

        printf("---------------------------------\n");

        for(i = 0; i <= cnt_of_codes; i++)

        {

               if((codeTable[i].ascii >= 65 &&

                  codeTable[i].ascii <= 90) ||

                  (codeTable[i].ascii >= 97 &&

                  codeTable[i].ascii <= 122))

               {

                       printf("%c\t\t%d\n", codeTable[i].ascii,

                          codeTable[i].frequency);

                       size += codeTable[i].frequency;

               }

        }

        printf("---------------------------------\n");

        printf("텍스트의 크기 : %d byte\n", size);

        printf("---------------------------------\n\n\n");

}

 

/*************************************************************

 * 버퍼에 저장된 호프만 코드를 사용 빈도수에 맞게 버퍼에 저장

 *

 *************************************************************/

void DownHeap(int i)

{

        int j, k;

        k = heap[i];

 

        while ((j = 2 * i) <= heap_size)

        {

               if (j < heap_size && frequency[heap[j]] >

                  frequency[heap[j + 1]])

                       j++;

               if (frequency[k] <= frequency[heap[j]])

                       break;

               heap[i] = heap[j];

               i = j;

        }

        heap[i] = k;

}

 

/*************************************************************

 * 호프만 알고리즘을 이용한 코드 테이블 작성

 *

 *************************************************************/

int HuffmanCodeTable(CODE codeTable[])

{

        int i, j, k, avail, cnt_of_codes;

        unsigned long int incount;

 

        for(i = 0; i < MAX_SIZE; i++)

               frequency[i] = 0;

 

              while ((i = getc(ifp)) != EOF)

               frequency[i]++;

 

        heap[i] = 0;

        heap_size = 0;

 

        for(i = 0; i < MAX_SIZE; i++)

        {

               if(frequency[i] != 0)

                       heap[++heap_size] = i;

        }

 

        for(i = 1; i <= heap_size; i++)

        {

               codeTable[i-1].ascii = heap[i];

               codeTable[i-1].frequency = frequency[heap[i]];

        }

 

        cnt_of_codes = heap_size;

        PrnFreq(codeTable, cnt_of_codes);

 

        for(i = heap_size / 2; i >= 1; i--)

               DownHeap(i);

        for(i = 0; i < 2 * MAX_SIZE - 1; i++)

               parent[i] = 0;

        k = heap[1];

        avail = MAX_SIZE;

        while (heap_size > 1)

        {

               i = heap[1];

               heap[1] = heap[heap_size--];

               DownHeap(1);

               j = heap[1];

               k = avail++;

               frequency[k] = frequency[i] + frequency[j];

               heap[1] = k;

               DownHeap(1);

               parent[i] = k;

               parent[j] = -k;

               left[k] = i;

                right[k] = j;

        }

 

        incount = 0;

        rewind(ifp);

        SetCode(codeTable, cnt_of_codes);

        return cnt_of_codes;

}

 

/*************************************************************

 * 아스키 코드에 대한 코드 작성

 *

 *************************************************************/

void SetCode(CODE codeTable[], int cnt_of_codes)

{

        int i, j, k, val = 0;

        char temp[MAX_SIZE];

        

        for(i = 0, j = 0, k = 0; i < cnt_of_codes; i++, j = 0,

            k = 0)

        {

               val = codeTable[i].ascii;

               while ((val = parent[val]) != 0)

               {

                       if (val > 0)

                              temp[j++] = '0';

                       else

                       {

                              temp[j++] = '1';

                              val = -val;

                       }

               }

 

               while(--j >= 0)

               {

                       codeTable[i].code[k] = temp[j];

                       k++;

               }

               codeTable[i].code[k] = '\0';

               codeTable[i].lengthOfCode = strlen(

                                            codeTable[i].code);

        }

        PrnCodeTable(codeTable, cnt_of_codes);

}

 

void PrnCodeTable(CODE codeTable[], int cnt_of_codes)

{

        int i;

        printf("Huffman code 생성 중...\n");

        printf("---------------------------------\n");      

        printf("alphabet\tcode\n");

        printf("---------------------------------\n");

        for(i = 0; i < cnt_of_codes; i++)

        if((codeTable[i].ascii >= 65 && codeTable[i].ascii <=

           90) || (codeTable[i].ascii >= 97 &&

           codeTable[i].ascii <= 122))

               printf("%c\t\t%s\n", codeTable[i].ascii,

                 codeTable[i].code);

        printf("---------------------------------\n");

}

 

/*************************************************************

 * 호프만 코드로 문자열 압축

 *

 *************************************************************/

int EncryptString(char original_String[],

                  int length_Of_Original_String,

                  CODE codeTable[],

                  int cnt_Of_Codes,

                  char encoded_String[])

{

        int i, pos, cnt_Of_Bits = 0;

        for(i = 0; i < length_Of_Original_String; i++)

        {

               pos = SearchAlphabet(original_String[i],

                                    codeTable, cnt_Of_Codes);

               if(pos >= 0)

               {

                       AttachCode(encoded_String, cnt_Of_Bits,

                                  codeTable[pos].code,

                                  codeTable[pos].lengthOfCode);

                       cnt_Of_Bits +=

                                  codeTable[pos].lengthOfCode;

               }

               else

               {

                       printf("%c does not exist in code

                               table!!\n", original_String[i]);

                       return -1;

               }

        }

        return cnt_Of_Bits;

                      

}

 

void WriteBitString(char encoded_String[],

                    int cnt_Of_EncodedBits)

{

        int i, pos = 0;

        char a;

        for(i=0; i < cnt_Of_EncodedBits; i++)

        {

               if(i%8==0)

               {

                       putchar(' ');

                       a = encoded_String[pos++];

               }

               putchar(((a & bitMask_OR[0]) == 0) ? '0' : '1');

               a <<= 1;

        }

        putchar('\n');

}

 

 

void WriteDecodedBit(char decoded_String[])

{

        int i, j, length, val, tmp = 0, diff;

        double progress = 0.0;

       

        printf("압축 푸는 중 ...\n");

        length = (int)strlen(decoded_String);

        for(i =0; i < length; i++)

        {

               progress = (double)(i+1) / (double)length *

                            100.0;

               if((int)progress%10 == 0 && (int)progress != 0

                       && (int)progress != 100)

               {

                       if((val = (int)progress) != tmp)

                       {

                              if((diff = (val - tmp) / 10) > 1)

                                      for(j = 1; j < diff; j++)

                                        printf("%d %% 압축

                                          품\n", tmp + j * 10);

                              printf("%d %% 압축 품\n", val);

                              tmp = val;

                       }

               }

              else if((int)progress/10 && (int)progress%10 > 5)

               {

                       if((val = ((int)progress/10)*10) != tmp)

                       {

                              if((diff = (val - tmp) / 10) > 1)

                                      for(j = 1; j < diff; j++)

                                        printf("%d %% 압축 품

                                            \n", tmp + j * 10);

                              printf("%d %% 압축 품\n", val);

                              tmp = val;

                       }

               }

               else if((val = ((int)progress/10)*10) != tmp &&

                        (int)progress != 100)

               {

                       if((diff = (val - tmp) / 10) > 1)

                       {

                              for(j = 1; j < diff; j++)

                                      printf("%d %% 압축 품\n",

                                          tmp + j * 10);

                       }

                       printf("%d %% 압축 품\n", val);

                       tmp = val;

               }

               putc(decoded_String[i], ofp);

        }

        printf("완료.\n");

}

 

void WriteInFile(char encoded_String[],

                 int cnt_Of_EncodedBits,

                 CODE codeTable[],

                 int cnt_of_codes)

{

        int i, j, ch = 0, incount, outcount, pos = 0, val,

            tmp = 0, diff;

        double version = VERSION, progress = 0.0;

        char *p, buffer[MAX_STRING_LENGTH];

        printf("압축 중 ...\n");

        fseek(ifp, 0L, SEEK_END);

        incount = ftell(ifp);

       

        // write a version

        sprintf(buffer, "%.1f ", version);

        for(i =0; i < (int)strlen(buffer); i++)

               putc(buffer[i], ofp);

              

        // write a size of the code tables

        sprintf(buffer, "%d", cnt_of_codes);

        for(i =0; i < (int)strlen(buffer); i++)

               putc(buffer[i], ofp);

        sprintf(buffer, "/%d ", cnt_Of_EncodedBits);

        for(i =0; i < (int)strlen(buffer); i++)

               putc(buffer[i], ofp);

       

        // write contents of the code tables

        for(i = 0; i < cnt_of_codes; i++)

        {             

               putc(codeTable[i].ascii, ofp);

               for(j = 0; j < codeTable[i].lengthOfCode; j++)

                       putc(codeTable[i].code[j], ofp);

        }

        putc(' ', ofp);

 

        // write contents of compressed file

        p = encoded_String;

        for(i=0; (i < cnt_Of_EncodedBits) && (ch != EOF) &&

            (*p != '\0'); i++)

        {

               progress = (double)i /

                          (double)cnt_Of_EncodedBits * 100.0;

               if((int)progress%10 == 0 && (int)progress != 0

                   && (int)progress != 100)

               {

                       if((val = (int)progress) != tmp)

                       {

                              if((diff = (val - tmp) / 10) > 1)

                              {

                                      for(j = 1; j < diff; j++)

                                        printf("%d %% 압축\n",

                                                 tmp + j * 10);

                              }

                              printf("%d %% 압축\n", val);

                              tmp = val;

                       }

               }

              else if((int)progress/10 && (int)progress%10 > 5)

               {

                       if((val = ((int)progress/10)*10) != tmp)

                       {

                              if((diff = (val - tmp) / 10) > 1)

                              {

                                      for(j = 1; j < diff; j++)

                                       printf("%d %% 압축\n",

                                                 tmp + j * 10);

                              }

                              printf("%d %% 압축\n", val);

                              tmp = val;

                       }

               }

               else if((val = ((int)progress/10)*10) != tmp &&

                       (int)progress != 100)

               {

                       if((diff = (val - tmp) / 10) > 1)

                       {

                              for(j = 1; j < diff; j++)

                                printf("%d %% 압축\n",

                                       tmp + j * 10);

                       }

                       printf("%d %% 압축\n", val);

                       tmp = val;

               }

               if(i%8==0)

                       ch = putc( p[pos++], ofp );

        }

        printf("압축 완료.\n");

        outcount = ftell(ofp);

        printf("---------------------------------\n");

        printf("텍스트 파일 크기 : %u bytes\n", incount);

        printf("압축된 파일 크기 : %u bytes\n", outcount);

        printf("압축 비율 : %.3f(%u/%u - 1)\n",

               ((double)incount / (double)outcount - 1.0)

               , incount, outcount);

}

 

/*************************************************************

 * 호프만 코드로 문자열 압축 풀기

 *

 *************************************************************/

int DecryptBitString(char encoded_String[],

                     int cnt_Of_EncodeBit,

                     CODE codeTable[],

                     int cnt_Of_Codes,

                     char decoded_String[])

{

        int i, index, pos=0, length_Of_DecodedString=0;

        char code[MAX_CODE_LENGTH] = {'\0'};

        char a;

        for (i = 0; i < cnt_Of_EncodeBit; i++)

        {

               if(i%8 ==0)

                       a=encoded_String[pos++];

 

               if(a & bitMask_OR[0])

                       strcat(code, "1");

               else

                       strcat(code, "0");

               a <<= 1;

               index=SearchCode(code, codeTable, cnt_Of_Codes);

               if(index != -1)

               {

                       decoded_String[length_Of_DecodedString]

                           = codeTable[index].ascii;

                       length_Of_DecodedString++;

                       code[0] = '\0';

               }

        }

        decoded_String[length_Of_DecodedString] = '\0';

        return length_Of_DecodedString;

}

 

/*************************************************************

 * 호프만 테이블 내의 주어진 알파벳 문자의 인덱스 찾기

 *

 *************************************************************/

int SearchAlphabet(char key, CODE codeTable[], int cnt_Of_Codes)

{

        int i, index = -1;

        for (i = 0; i <cnt_Of_Codes; i++)

        {

               if(codeTable[i].ascii == key)

               {

                       index=i;

                       break;

               }

        }

        return index;

}

 

/*************************************************************

 * 호프만 테이블 내의 주어진 코드의 인덱스 찾기

 *

 *************************************************************/

int SearchCode(char key[], CODE codeTable[], int cnt_Of_Codes)

{

        int i, index=-1;

        for (i = 0; i < cnt_Of_Codes; i++)

        {

               if(strcmp(codeTable[i].code, key) == 0)

               {

                       index=i;

                       break;

               }

        }

        return index;

}

 

/*************************************************************

 * 하나의 버퍼에 호프만 코드 저장

 *

 *************************************************************/

void AttachCode(char encoded_String[], int cnt_Of_Bits, char code[],

                              int lengthOfCode)

{

        int i, lengthOfEncodedString, lastBitPosition;

 

        lengthOfEncodedString = cnt_Of_Bits/8;

        lastBitPosition = cnt_Of_Bits%8;

        for (i = 0; i < lengthOfCode; i++)

        {

               if(code[i]=='1')

                       encoded_String[lengthOfEncodedString] |=

                                  bitMask_OR[lastBitPosition];

               else

                       encoded_String[lengthOfEncodedString] &=

                                  bitMask_AND[lastBitPosition];

               lastBitPosition++;

              

               if(lastBitPosition == 8)

               {

                       lastBitPosition = 0;

                       lengthOfEncodedString =

                                     lengthOfEncodedString + 1;

               }

        }

}

1. 이론

자주 쓰이는 문자에 가장 작은 bit 를 할당하고

한두번 쓰이는 문자에는 큰 bit 를 할당한다라는 것이다.

즉 간단하게 예를 들어서

AABBAC

라는 문자열이 있다고 예를 들어보자.

영문자 하나는 1byte 이므로 총 6byte 의 크기를 가지는 문자열이다.

자 그럼

각 문자들이 사용된 횟수를 알아보자.

머 짧으니까 한눈에 알 수 있을 것이다.

A 는 3번

B 는 2번

C 는 1번 사용되었다.

그러면 가장 많이 사용된 A 에게 0 이라는 1bit 를 부여하고

B 는 10, C 는 11 을 부여할 수 있다.

그러면 위 문자열은

A(0)A(0)B(10)B(10)A(0)C(11)

합쳐보면 001010011 로 나타낼 수 있다.

총 9 bit = 1 byte + 1 bit 으로 압축을 할 수 있다.

원래 문자열이 6 byte 즉 48 bit 를 차지하였는데 9/48 = 0.19

즉 약 20% 로 압축이 되었다. 압축률이 80% 라는 이야기다.

뭐 조금 띄엄띄엄 살펴본것 같지만 허프만 알고리즘의 핵심은 바로 이것이다.

물론 헤더도 붙고 하다보면 조금더 커지겠지만

큰 파일일 수록, 텍스트 기반일 수록, 자주 쓰이는 문자가 많을 수록 압축률은 높아지게 되어 있다.



2. 이진 트리

자 그렇다면 이론은 알겠는데

실제로는 어떻게 적용해야하는 걸까?

순서대로 한번 살펴보자.

대상 문자열 : CDDCACBCBCCCBBCDA

1. 각 문자열별로 빈도수를 검사한다.






2. 빈도수 순서대로 정렬한다. (repeat 1/2)






3. 가장 낮은 두 그룹을 묶어서 하나의 그룹으로 만든다. (repeat 2/2)









4. 빈도수 순서대로 정렬한다. (repeat 1/2)









5. 가장 낮은 두 그룹을 묶어서 하나의 그룹으로 만든다. (repeat 2/2)











6. 빈도수 순서대로 정렬한다. (repeat 1/2)











7. 가장 낮은 두 그룹을 묶어서 하나의 그룹으로 만든다. (repeat 2/2) 트리완성.














8. 이제 트리가 완성되었다.

가장 윗 트리에서부터 빈도수가 큰 트리에 0을 작은 트리에 1을 부여한다.














9. 위 트리를 기준으로 각 문자열의 비트를 참조한다.

부모노드에서 출발하여 문자열에 다다를때까지 비트를 더하여 참조한다. 즉,














A - 001 이 된다.

이와 같은 방법으로

B - 01, C - 1, D - 000 로 비트를 할당 할 수 있게 된다.

그러면 초기 문자열을 할당된 비트로 치환하여 보자.

1000000100110110111101011000001

위와 같이 치환되었다.

총 17문자, 17 byte 였던 원래 문자열이 31 bit 즉, 8 byte 로 압축이 된것이다.

물론 문자열 테이블도 붙고 헤더도 붙으면 약간 더 늘어나겠지만

이번 테스트에서의 압축률은 약 50%로 나타났다.



3. 디코딩은?

호프만 알고리즘을 이용하여 압축을 하면

어떤 문자가 어떤 bit 로 치환되었는지를 판단해야되기 때문에

호프만 테이블이라고 불리는 테이블을 추가해야한다.

호프만 테이블은 방금 우리가 만든 그 이진 트리를 말한다.

그 트리를 보고 복호화하는것이다.













한 bit 단위로 읽어서 테이블대로

문자가 나올때까지 트리를 타고 가면서 치환하는것이다.

예를 들어 00101 이라는 데이타는

AB 를 나타낸다는 것이다.

 - 00101 을 복호화해보자

 - 첫 비트 0 은 17로 표시되어 있는 트리에서 왼쪽, 즉 9 로 표시되어 있는 트리로 내려간다.
 - 다음 0 은 역시 왼쪽, 5 로 표시되어 있는 트리로 내려간다.
 - 다음 1 비트는 오른쪽, 즉 2로 표시되어 있는 트리, A 를 나타낸다.
 - 문자를 하나 찾았으니 자 그럼 다시 처음부터
 - 다음 0 은 17 트리에서 9 트리로
 - 다음 1 은 오른쪽 4 트리로, 즉 B 를 나타낸다.

이런식으로 문자열을 치환해주면된다.

대단하지 않은가??

이게 바로 허프만 알고리즘의 원리인것이다.

In computer science and information theory, Huffman coding is an entropy encoding algorithm used for lossless data compression. The term refers to the use of a variable-length code table for encoding a source symbol (such as a character in a file) where the variable-length code table has been derived in a particular way based on the estimated probability of occurrence for each possible value of the source symbol. It was developed by David A. Huffman while he was a Ph.D. student at MIT, and published in the 1952 paper "A Method for the Construction of Minimum-Redundancy Codes."