sakuragi's miscellaneous space

 이번 것은 과제는 아니였는데, 오기로(?) 해 버렸다. 크루스칼 알고리즘을 힘들게 해결한 이후에, 이제는 슬슬 인터넷에서 소스를 찾기보다는 내 자신이 교재(참고자료 참고)의 pseudo code(의사 코드)를 보고, 몇시간을 감이 잡힐 때까지 그림을 그려보거나 골똘히 생각하다가 조금씩 실마리가 잡히면 코딩을 시작하는 형태가 되어 가고 있다.

 (참고로 나는 프로그램을 잘하거나 소질이 있는 것이 아니라서 이 정도의 프로그램을 짜려면 며칠이 걸린다. 이 허프만 코드의 경우 코딩을 시작 하기까지 두시간 정도를 책을 보면서 어떻게 구현할 수 있을까 생각한 후에, 코딩을 시작했고 꼬박 앉은 자리에서 열시간 정도를 삽질을 하면서 프로그램을 트리 구성까지 완성시켰다. 그리고 마지막 결과 트리 출력 부분을 만들기 위해 추가로 서너시간 가량이 걸렸다.)

  이렇게 최근 알고리즘에 열을 올리면서 이전에는 왜 알고리즘이나 자료구조 책에는 바로 컴파일을 할 수 있는 소스가 아니고, pseudo code만 나와있어서 이렇게 사람을 힘들게 하냐고 생각 했는데... 최근 1~2주 사이에는 힘들어도 pseudo code를 보면서 내 입맛에 맞춰서 코딩(요리)을 하는 재미도 나름대로 솔솔하다는 생각도 든다.

 그리고 지금 보고 있는 교재의 pseudo code가 다른 알고리즘이나 자료구조 책보다 깔끔하게 정리가 잘 되어 있다는 생각이 든다. 필요한 부분만 쉽게 설명해주고 pseudo code로 보여준다는 느낌이다.

 허프만 코드는 기존의 영문자 ASCII 코드가 7비트(8비트)로 문자를 표현하고 있지만, 실재로는 하나의 문서에서 몇백개나 되는 문자를 모두 쓰는 경우는 매우 드문다는 점에 착안해서, 쓰는 문자만 뽑아내고 그 문자에 가중치(빈도수)를 주어서, 자주 나오는 문자를 짧게 부호화(이진코드화)해서, 하나의 문자로 봤을때나 전체의 문자열로 봤을 때나, ASCII 코드보다 적은 비트로 표현이 가능해져서 압축을 하는 효과가 된다는 개념이다.

   지금 학교에서 배우는 교재(참고자료 참고)에서는 이번 알고리즘 역시 탐욕적인 방법으로 분류되어 나온다. 지금까지 탐욕적인 알고리즘을 몇가지 봤는데, 분할정복법의 요점이 재귀, 동적계획법의 요점이 행렬(배열)이였다면 탐욕적인 알고리즘의 요점은 정렬이라고 느꼈다. 크루스칼이나 프림의 알고리즘도 그 순간에 최적인 방법을 택하기 위해서는 정렬이 필수였고, 지금 보는 허프만 코드 역시 이진 트리를 구성하기 위해서는 정렬된 우선순위 대기열을 사용한다.

 허프만 코드에서 이진 트리를 어떻게 만드는지와 같은 알고리즘이 돌아가는 방식에 대해서는 인터넷에서 검색하면 많이 나오므로 생략한다. 소스는 철절히 교재의 pseudo code의 리듬으로 짰으므로, 교재가 있다면 이해하는데 어렵지 않으리라 생각된다.

 이건 개인적인 얘기이고 지난번에도 얘기 했지만, 알고리즘 관련 포스팅의 경우 조회수는 참 높은데, 조회수에 비해 댓글은 거의 없다. 뭔가 댓글을 좀 달아주셨으면 좋겠다. 이 부분은 이렇게 하는게 더 좋다라든지... 소스의 어느 부분이 문제라든지.. 아니면 잘 가져가서 쓴다라는 댓글이라도 좋다. 자기 블로그(홈페이지)가 있다면 주소도 좀 남겨주셨으면 좋겠다. 아니면 리퍼러에 남도록 방문해 주면 알아서 찾아갈터인데...

허프만 코드 알고리즘에서 쓰일 텍스트 파일 파일(huffman.txt)

b:5 e:10 c:12 a:16 d:17 f:25

주어진 문자와 가중치로 트리를 구성해서 허프만 부호를 뽑아내는 허프만 코드 알고리즘

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

typedef struct nodetype
{
    char symbol;   // 문자값
    int frequency; // 파일에 있는 문자의 빈도수

    struct nodetype* left;
    struct nodetype* right;
}node;

typedef struct pq   // 우선순위 대기열
{
    node* Node;         // 대기열에 있는 node
    struct pq* next;   // 다음 node
}pq;

#define ROOT    -1 // 부호화 함수 출력시 초기값

pq* insert(node* r);        // 우선순위 대기열에 노드를 정렬하여 삽입
node* huffman(int n);       // 허프만 코드 트리를 만드는 함수
node* Remove();             // 우선 순위 대기열에서 노드를 삭제
void print_PQ();            // 우선 순위 대기열 출력
void print_tree(node* r, int n, char* code);    // 결과 허프만 부호화 출력
void freetree(node* r);     // 메모리 해제

pq* PQ = NULL;      // 우선순위 대기열
FILE* file;         // 파일 식별자

int main()
{
    int n = 1;
    node* result = (node*) malloc(sizeof(node));   // 결과를 돌려받을 노드
    char* code = (char*) malloc(sizeof(char));

    file = fopen("huffman.txt", "r");  // 입력이 되는 문자와 빈도수
    if(file == NULL) {
        perror("File open error");
        return 0;
    }


    while(1) {
        node* r = (node*) malloc(sizeof(node));
        if( ( fscanf(file, "%c:%d ", &r->symbol, &r->frequency)) == -1) {
            break;       // 파일에 더 이상 값이 없으면 while 끝내기
        }
        r->left = NULL;
        r->right = NULL;
        insert(r);      // 노드를 삽입 하면서 정렬함
        n++;
    }

    printf("### Huffman Algorithm ###\n\n");
    print_PQ();     // 입력이 끝난 우선순위 대기열

    result = huffman(n);    // 허프만 알고리즘

    printf("\n-- Result Huffman code tree\n");
    print_tree(result, ROOT, code);
    printf("\n");

    freetree(result);   // 메모리 해제
    fclose(file);

    return 0;
}

void freetree(node* r)  // 메모리 해제
{
    if(r) {
        freetree(r->left);
        freetree(r->right);
        free(r);
    }
}


pq* insert(node* r) // 우선순위 대기열에 노드 삽입
{
    pq* tmp = NULL;
    pq* new = NULL;

    // 우선순위 대기열 추가할 새로운 공간 할당
    new = (pq*) malloc(sizeof(pq));
    new->Node = r;      // 대기열에 추가할 새로운 공간에 r 노드값 삽입
    new->next = NULL;

    if(PQ == NULL){    // 대기열이 비여있으면 새로운 공간이 리스트의 head가 됌
        PQ = new;
        return PQ;
    } else if(PQ->Node->frequency > new->Node->frequency) {
        new->next = PQ;             // 루트 노드에 대한 비교 및 정렬
        PQ = new;
    }else {                            // 대기열에 리스트가 들어 있다면..
        tmp = PQ;                       // tmp는 head
        while(tmp->next != NULL) {        // 다음 노드가 없을때까지..
            if(tmp->next->Node->frequency <= new->Node->frequency)
                tmp = tmp->next;        // 우선순위 대기열 정렬을 위한 비교
            else {                       // new의 빈도수가 tmp 보다 크고,
                new->next = tmp->next;  // tmp->next의 빈도수보다 작으면..  
                tmp->next = new;        // 두 노드 사이에 새 노드를 삽입
                break;
            }

        }
        if(tmp->next == NULL)     // 다음 대기열이 비어 있으면 삽입
            tmp->next = new;

        return tmp;
    }
    return 0;
}

node* huffman(int n)    // 허프만 알고리즘
{
    node* p;
    node* q;
    node* r;

    int i;

    for(i = 1; i < n-1; i++) {
        p = Remove();   // 우선 순위 대기열에서 하나의 노드를 빼와서 p에 삽입
        q = Remove();   // 우선 순위 대기열에서 하나의 노드를 빼와서 q에 삽입

        r = (node*) malloc(sizeof(node)); // 새로운 부분 트리를 위한 공간 할당
        r->left = p;
        r->right = q;
        r->frequency = p->frequency + q->frequency;
        r->symbol = '*';  // 부분 트리의 뿌리임을 나타냄
        insert(r);          // 만들어진 부분 트리를 우선 순위 대기열에 삽입

        printf("-- Create sub tree (%d/%d)\n  ", i, n-2);
        printf("%c:%d = %c:%d + %c:%d\n",
                r->symbol, r->frequency, p->symbol, p->frequency, q->symbol, q->frequency);
        print_PQ();
    }

    r = Remove();   // 우선 순위 대기열에 있는 트리의 뿌리를 빼와서 r에 대입
    return r;
}

node* Remove()  // 우선 순위 대기열에서 하나의 노드를 빼서 리턴값으로 넘긴다
{
    node* pq_firstnode = NULL;

    pq_firstnode = PQ->Node;
    PQ = PQ->next;

    return pq_firstnode;
}

void print_PQ()     // 우선순위 대기열 출력
{
    pq* tmp = PQ;
    printf("-- Priority Queue\n  | ");
    while(tmp != NULL){
        printf("%c:%d | ", tmp->Node->symbol, tmp->Node->frequency);
        tmp = tmp->next;
    }
    printf("\n\n");
}

void print_tree(node* r, int n, char* code) // 결과 허프만 알고리즘  트리 출력
{
    if(r) {
        n++;    // 트리의 깊이를 표시

        code[n] = '0';    // 트리의 좌측
        print_tree(r->left, n, code);

        code[n] = '1';    // 트리의 우측
        print_tree(r->right, n, code);

        code[n] = '\0';   // 찌꺼기 제거
        if(r->left == NULL || r->right == NULL)   // 자식이 있는 노드는 출력하지 않음
            printf(" - %c:%d\t= %s\n", r->symbol, r->frequency, code);
    }
}

결과는 다음과 같다.

 생각보다 마지막에 결과인, 허프만 코드(부호)를 출력하는데 무지하게 애를 먹었다. 어떻게 트리를 순회하면서, 노드의 값이 아닌, 노드와 노드사이를 연결한 방향을 나타내는 부호인 0과 1을 출력할 수 있을까? 하고...

참고자료
• 알고리즘(Foundatations of Algorithms Using C++ Pseudocode) - Neapolitan, Naimipour 저 / 도경구 역