enHuffman  허프만 코딩
deHuffman  허프만 코딩으로부터의 복호

허프만 코딩
    long enHuffman(unsigned char *code, long clen,
                   unsigned char *text, long tlen);

허프만 코딩으로부터의 복호
    long deHuffman(unsigned char *text, long tlen,
                   unsigned char *code, long clen);

허프만 코딩 함수에 대해
    code  (입출력) 허프만 코딩을 격납하는 배열
    clen  (입력) 배열 code의 길이
    text  (입력) 텍스트를 격납하는 배열
    tlen  (입력) 배열 text의 길이

허프만 코딩으로부터의 복호 함수에 대해
    text  (입출력) 텍스트를 격납하는 배열
    tlen  (입력) 배열 text의 길이
    code  (입력) 허프만 코딩을 격납하는 배열
    clen  (입력) 배열 code의 길이

허프만 코딩 함수에 대해
    허프만 코딩의 길이. encode에 실패했을 때는 -1L.

허프만 코딩으로부터의 복호 함수에 대해
    텍스트의 길이. 복호에 실패했을 때는 -1L.

typedef struct {
    long count;      /* 자 노드의 출현 빈도의 화 */
    int  parent;     /* 친노드에 */
    int  left;       /* 좌측의 아이 노드에 */
    int  right;      /* 우측의 아이 노드에 */
} NODE;

#define CHAR_SIZE    256
#define NODE_SIZE    (2*CHAR_SIZE+2)

long enHuffman(unsigned char *code, long clen,
               unsigned char *text, long tlen)
{
    int  i, k;
    long c, len;
    int  min1, min2;
    long max;
    int  root;
    NODE node[NODE_SIZE]; int  freeNode;
    char bit[NODE_SIZE];  char *bitp;
    static unsigned char bit0[8] = {~128,~64,~32,~16,~8,~4,~2,~1};
    static unsigned char bit1[8] = { 128, 64, 32, 16, 8, 4, 2, 1};

    if (tlen <= 0 || clen <= 2*CHAR_SIZE) return -1L;

    /* 각 문자의 출현 빈도를 계산 */
    for (i = 0; i < NODE_SIZE; i++) node[i]. count = 0;
    for (c = 0; c < tlen; c++) node[text[c]]. count++;

    /* 최대 출현 빈도의 값이 2바이트를 넘지 않게 조정한다 */
    for (i = 0, max = 0; i < CHAR_SIZE; i++)
        if (node[i]. count > max) max = node[i]. count;
    if ((k = max/0x10000L) > 0)
        for (i = 0, k++; i < CHAR_SIZE; i++)
            if (node[i]. count > 0) {
                node[i]. count /= k;
                if (node[i]. count == 0) node[i]. count = 1;
            }

    /* 각 문자의 출현 빈도를 출력 */
    for (i = 0; i < CHAR_SIZE; i++) {
        *code++ = (node[i]. count >> 8) & 0xff;
        *code++ = node[i]. count & 0xff;
    }
    
    /* EOF */
    node[CHAR_SIZE]. count = 1;

    /* 하프맨나무를 만든다 */
    node[NODE_SIZE - 1]. count = 0x10000L;          /* 파수병 */
    for (freeNode = CHAR_SIZE+1; ; freeNode++) {
        min1 = min2 = NODE_SIZE - 1;
        for (i = NODE_SIZE - 2; i >= 0; i--)
            if (node[i]. count > 0) {
                if (node[i]. count < node[min1]. count) {
                    min2 = min1;
                    min1 = i;
                } else if (node[i]. count < node[min2]. count)
                    min2 = i;
            }

        if (min2 == NODE_SIZE - 1) break;
        node[freeNode]. left  = min1;
        node[freeNode]. right = min2;
        node[freeNode]. count = node[min1]. count + node[min2]. count;
        node[min1]. parent = node[min2]. parent = freeNode;
        node[min1]. count = node[min2]. count = 0;
    }
    root = min1;

    /* 각 문자를 encode */
    for (c = 0, i = 0, len = 2*CHAR_SIZE; ; c++) {
        k = (c == tlen) ?  CHAR_SIZE : text[c];
        
        /* 부호어를 얻는다 */
        bitp = bit;
        do {
            int parent = node[k]. parent;
            *bitp++ = (node[parent]. left == k) ?  0 : 1;
            k = parent;
        } while (k ! = root);
        
        /* 역순서에 출력 */
        do {
            if (*--bitp) *code |= bit1[i];
            else         *code &= bit0[i];
            if (++i == 8) {
                code++;
                if (++len > clen) return -1L;
                i = 0;
            }
        } while (bitp ! = bit);
        if (c == tlen) break;
    }

    if (i > 0) len++;
    return (len > clen) ?  -1L : len;
}

long deHuffman(unsigned char *text, long tlen,
               unsigned char *code, long clen)
{
    int  i, k;
    long c, len;
    int  min1, min2;
    int  root;
    NODE node[NODE_SIZE]; int  freeNode;
    static unsigned char bit1[8] = { 128, 64, 32, 16, 8, 4, 2, 1};

    if (clen <= 2*CHAR_SIZE) return -1L;

    /* 각 문자의 출현 빈도를 세트 */
    for (i = 0; i < NODE_SIZE; i++) node[i]. count = 0;
    for (i = 0; i < CHAR_SIZE; i++) {
        node[i]. count = *code++;
        node[i]. count = (node[i]. count << 8) | *code++;
    }
    
    /* EOF */
    node[CHAR_SIZE]. count = 1;

    /* 하프맨나무를 만든다 */
    node[NODE_SIZE - 1]. count = 0x10000L;          /* 파수병 */
    for (freeNode = CHAR_SIZE+1; ; freeNode++) {
        min1 = min2 = NODE_SIZE - 1;
        for (i = NODE_SIZE - 2; i >= 0; i--)
            if (node[i]. count > 0)
                if (node[i]. count < node[min1]. count) {
                    min2 = min1;
                    min1 = i;
                } else if (node[i]. count < node[min2]. count)
                    min2 = i;
        if (min2 == NODE_SIZE - 1) break;
        node[freeNode]. left  = min1;
        node[freeNode]. right = min2;
        node[freeNode]. count = node[min1]. count + node[min2]. count;
        node[min1]. parent = node[min2]. parent = freeNode;
        node[min1]. count = node[min2]. count = 0;
    }
    root = min1;
            
    /* 복호화 */
    for (i = 0, len = 0, c = 2*CHAR_SIZE; ; ) {
        /* 부호어에 대응하는 문자 노드를 얻는다 */
        k = root;
        do {
            int parent = k;
            k = (*code & bit1[i]) ?  node[k]. right : node[k]. left;
            if (k >= parent) return -1L;     /* 있을 수  없다 */
            if (++i == 8) {
                code++;
                if (++c > clen) return -1L;
                i = 0;
            }
        } while (k > CHAR_SIZE);
        if (k == CHAR_SIZE) break;
        if (++len > tlen) return -1L;
        *text++ = k;
    }
    return len;
}

• 모든 부호어의 길이는 일정이 아니다.
• 출현 확률의 작은 기호에 긴 부호어, 출현 확률의 큰 기호에 짧다 부호어를 할당한다.
• 평균 부호장이 최소.
• 부호어열로부터, 원의 기호열을 일의적으로 복호 할 수 있다.

허프만 코딩을 이하와 같이 구성할 수 있다.

1. 텍스트에 있는 각 기호(문자)에 대응하는 노드를 만든다. 각각 의 노드에는, 그 기호의 출현 빈도를 기입한다.
2. 출현 빈도의 가장 작은 2개의 노드에 대해, 친노드를 만들어, 한편에 0 의 라벨, 한편에 1 의 라벨을 붙인다. 또 친노드에, 아이노 드의 출현 빈도의 화를 기입한다. 이 친노드는 이후, 아이 노드의 대신 된다.
3. 나머지의 노드와 친노드로부터, 노드의 수가 1개가 될 때까지, 2. 의 처리를 반복한다.
4. 루트로부터 기호에 대응하는 노드까지 에다를 더듬었을 때에 얻을 수 있다 0, 1 의 라벨열이 그 기호에 대한 부호어가 된다. 또, 이와 같이 구성 되는 부호의 나무를, 하프맨나무라고 부른다.

실제의 encode 프로그램에서는, 텍스트를 2회 주사 한다. 1회째로는 각 기호(문자)의 출현 빈도를 조사한 다음, 하프맨나무를 만든다. 또 복호 할 수 있도록(듯이), 각 기호의 출현 빈도를 부호의 일부로서 출력한다. 2번째의 주사에서는, 하프맨나무리나 무늬 각 문자를 encode 한다.

출력 부호의 포맷은, 선두에 1 문자 2바이트씩의 출현 빈도, 합계 512바이트의 헤더부와 그 후에 계속되는 부호어열로부터 된다.

덧붙여 부호어열의 종료를 나타내기 위해서(때문에), 출현 빈도가 1의 EOF 기호(코드 256) 에 대응하는 부호어를 기입한다.