자료구조 :: 힙(2) 최소힙을 이용한 허프만트리

# 허프만 트리

HuffmanTree.cpp

■ 허프만(Huffman) 코드

허프만 부호와의 기본 개념은 각 단위 정보를 표현하는 비트 수를 단위 정보들의 출현 빈도를 기반으로 할당.
빈도가 높은 정보는 적은 비트 수를 사용하여 표현하고, 빈도가 낮은 정보는 비트 수를 많이 사용하여
표현해서 전체 데이터의 표현에 필요한 비트의 양을 줄임. 대표적인 가변 길이 코드이며, 영상 압축에 많이 사용됨.


■ 허프만 압축기법

허프만 압축기법은 1954년 허프만에 의해 제안된 압축 방식으로 오늘날에도 널리 이용되고 있다.
이 기법은 정보원 데이터내의 각 문자에 대한 발생빈도를 조사해 자주 나타나는 문자에는 보다 짧은 부호어를,
그리고 잘 나타나지 않는 문자에는 더 긴 부호어를 할당함으로써, 전체 압축후 부호어의 길이를 원래의 정보원
길이보다 더 축소시킬 수 있는 통계적 특성을 이용한 압축기법이다. 이 방식의 일례를 그림으로 나타내었다.

설명 및 그림 출처 : http://blog.naver.com/hammsy

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

#define ALPHABET 26
#define MAX_LEN 255
#define MAX_ELEMENT 1000

typedefstruct { 
int alpha; // 알파벳 저장을 위한 배열
int freq; // 빈도수 저장을 위한 배열
}AlphaType; 

typedefstruct TreeNode{ 
    AlphaType weight; 
    TreeNode *left_child; 
    TreeNode *right_child; 
}TreeNode; 

typedefstruct { 
    TreeNode *pTree; 
int key; 
}Element; 

typedefstruct { 
    Element heap[MAX_ELEMENT]; 
int heap_size; 
}HeapType; 


void InsertHeap(HeapType *h,Element item) 
{ 
int i; 
    i=++(h->heap_size); 

while(i != 1 && item.key < h->heap[i/2].key) // 부모노드와 비교
    { 
        h->heap[i]=h->heap[i/2]; 
        i/=2; 
    } 

    h->heap[i]=item; 
} 

Element DeleteHeap(HeapType *h) 
{ 
int parent=1,child=2; 
    Element data,temp; 

    data = h->heap[parent]; 
    temp = h->heap[(h->heap_size)--]; // 삭제에 의한 size 감소

while(child <= h->heap_size) 
    { 
//자식 노드간 작은 수 비교 
if((child < h->heap_size) && (h->heap[child].key) > h->heap[child+1].key)  
            child++; 

if(temp.key <= h->heap[child].key) break; 

        h->heap[parent] = h->heap[child]; 
        parent = child; 
        child *= 2; // 다음 자식 노드와 비교
    } 

    h->heap[parent]=temp; 
return data; 
} 

TreeNode* MakeNode(TreeNode *left,TreeNode *right) // 노드 생성
{ 
    TreeNode *node=(TreeNode*)malloc(sizeof(TreeNode)); 

if(node == NULL) 
    { 
        printf("메모리 할당 에러\n"); 
        exit(-1); 
    } 

    node->left_child=left; 
    node->right_child=right; 

return node; 
} 

void PrintTree(TreeNode *p,int i,char *pCode) 
{ 
if(p) 
    { 
        i++; 
        pCode[i]='1'; 
        PrintTree(p->left_child,i,pCode); 
        pCode[i]='0'; 
        PrintTree(p->right_child,i,pCode); 
        pCode[i]='\0'; 

if(p->left_child == NULL && p->right_child == NULL) 
        { 
            printf("%3c\t%3d\t%s\n",p->weight.alpha,p->weight.freq,pCode); 
        } 
    } 
} 

int DestroyTree(TreeNode *p)  
{ 
if(p == NULL) return -1; 

    DestroyTree(p->left_child); 
    DestroyTree(p->right_child); 

    free(p); 

return1; 
} 

void HuffmanTree(AlphaType *pArr,int n) 
{ 
    TreeNode *node,*temp; 
    Element e,e1,e2; 
    HeapType heap; 
char binaryCode[100]; 
int i; 

    heap.heap_size=0; 

for(i=0;i<n;i++) 
    { 
        node=MakeNode(NULL,NULL);   
        node->weight.alpha=pArr[i].alpha; 
        e.key=node->weight.freq=pArr[i].freq; 
        e.pTree=node; 
        InsertHeap(&heap,e); // 생성한 노드를 힙에 삽입
    } 

for(i=0;i<n-1;i++) // n-1까지 반복, 마지막 남은 노드가 루트
    { 
        e1=DeleteHeap(&heap); // 최소값을 가지는 노드 2개를 빼낸다
        e2=DeleteHeap(&heap);  

        temp=MakeNode(e1.pTree,e2.pTree); // 2개의 노드를 가지는 노드 생성

        e.key=temp->weight.freq=e1.key+e2.key; // 2개의 노드 값을 더한다
        e.pTree=temp; // 위에서 만든 노드를 대입

        InsertHeap(&heap,e); // 트리로 구성된 노드를 힙에 삽입
    } 
    e = DeleteHeap(&heap); // 여기서 꺼낸 데이터는 완성된 트리

    PrintTree(e.pTree,-1,binaryCode); // 허프만 코드 출력

    DestroyTree(e.pTree); // 메모리 반환

} 

void Init(AlphaType *p) 
{ 
for(int i=0;i<ALPHABET;i++) 
    { 
        p[i].alpha=i+65; 
        p[i].freq=0; 
    } 
} 

int main() 
{ 
    AlphaType data[ALPHABET]; // 문자열의 갯수 저장을 위한 변수
    AlphaType *copyData; // 존재하는 문자열의 갯수 저장을 위한 변수

    Init(data); 

char *str=(char*)malloc(sizeof(char)*MAX_LEN); 

int i,j,k=0; 
int flag,count=0; 

    printf("Input String : "); 
    scanf("%s",str); 

    strupr(str); // 모든 문자를 대문자로 변환

for(i='A';i<='Z';i++) 
    { 
        flag=0; 
for(j=0;j<strlen(str);j++) 
        { 
if(i == str[j]) 
            { 
                data[i-65].freq++; 
                flag=1; // i값의 알파벳이 존재
            } 
        } 
if(flag==1) 
            count++; // 알파벳이 존재하므로 카운터 증가
    } 

    copyData=(AlphaType*)malloc(sizeof(AlphaType)*count); 

for(i=0;i<ALPHABET;i++) 
    { 
if(data[i].freq != NULL) // 존재하는 문자만 복사
        { 
            copyData[k].alpha=i+65; 
            copyData[k].freq=data[i].freq; 
            k++; 
        } 
    } 

    printf("\n- character frequency -\n"); 
for(i=0;i<count;i++) 
        printf("%3c\t%3d \n",copyData[i].alpha,copyData[i].freq); 

    printf("\n- Huffman Tree Code -\n"); 
    HuffmanTree(copyData,count); 

    free(str); 
    free(copyData); 

return0; 
} 

이걸 하면서 다시 한번 재귀의 중요성을 느끼고.. 세상엔 천재가 참 더럽게 많다는 생각을 한다..

출력 부분이 너무나 복잡하다. 어떠한 key값에 대한 코드만 출력 하려고 했는데 너무 복잡해져서 결국 다른분의
소스코드를 참고해서 전체가 나오게 구현했다.
책에 있는 부분에서 이부분 저부분을 수정하고 문자열 입력 부분을 추가하다보니 200라인이 넘었다......휴..