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の長さ

ハフマン符号関数について
    ハフマン符号の長さ。符号化に失敗したときは -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++;

    /* 最大出現頻度の値が２バイトを越えないように調整する */
    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;

    /* 各文字を符号化 */
    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. 出現頻度のもっとも小さい２つのノードに対し、親ノードをつくり、 一方に 0 のラベル、他方に 1 のラベルをつける。また親ノードに、子ノ ードの出現頻度の和を書き込む。この親ノードは以降、子ノードの代わり となる。
3. 残りのノードと親ノードから、ノードの数が１つになるまで、 2. の 処理を繰り返す。
4. ルートから記号に対応するノードまで枝をたどったときに得られる 0、1 のラベル列がその記号に対する符号語となる。また、このように構成 される符号の木を、ハフマン木と呼ぶ。

実際の符号化プログラムでは、テキストを２回走査する。１回目では各 記号（文字）の出現頻度を調べた上で、ハフマン木をつくる。また復号 できるように、各記号の出現頻度を符号の一部として出力する。２回目の 走査では、ハフマン木をはどりながら各文字を符号化する。

出力符号のフォーマットは、先頭に１文字２バイトずつの出現頻度、計 512バイトのヘッダ部と、その後に続く符号語列からなる。

なお、符号語列の終了を表すために、出現頻度が１のEOF記号（コード256） に対応する符号語を書き込む。