ハフマン符号とハミング符号

ブレイゴ · #1

プログラミング初心者で、この掲示板を使うのも初めてです。
符号理論の方も勉強中なので、間違いがあればご指摘お願いします。

ttp://www.nicklib.com/library/algo/h/huffman.html
こちらに載っていたものを参考に（とは言えないくらいほぼそのままですが）、
「入力した文字をfgets()で取得してハフマン符号アルゴリズムで圧縮し、エラーを追加して、ハミング符号で誤り検出訂正、復号する」というC言語のプログラムを作ろうとしています。

コード:

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

#define CHAR_SIZE 256
#define NODE_SIZE 512

typedef struct {
    long count;      // sum of the frequency of appearance of child nodes
    int  parent;     // parent node
    int  left;       //  left child node
    int  right;      // right child node
} NODE;

long enHuffman(unsigned char *code, long clen,
               unsigned char *orig, long tlen);
			   
long deHuffman(unsigned char *text, long tlen,
               unsigned char *code, long clen);


int main() {

	NODE node[NODE_SIZE];
	int i, j, k;
	char orig[CHAR_SIZE] ={""};
	unsigned char code[1000], new[500];

	printf("--- Data compression by Huffman coding --- \n");

	printf("Please enter the text. \n");
	printf(">");
	fgets(orig, sizeof(orig), stdin);
	orig[strlen(orig)-1] = '\0';

	// Compute the frequency of occurrence of each character
	for (i = 0; i < NODE_SIZE; i++) node[i].count = 0;
	for (i = 0; i < strlen(orig); i++) node[orig[i]].count++;
	
	k = enHuffman(code, 1000L, orig, (long)strlen(orig));
	if (k < 0) {
		printf("It failed to coding. \n");
		exit(1);
	}
	
	printf("\nThe frequency of occurrence of each character. \n");
	printf(" character: frequency \n");

 	for (i = 0; i < CHAR_SIZE; i++)
		if (node[i].count != 0)
			printf(" >%c: %ld \n", i, node[i].count);

	for (i = 0; i < strlen(code); i++) printf("%c", code[i]);

	printf("--------------------------------------------------- \n");
	printf("The length of the text: textlen = %d \n", strlen(orig));
	printf("The length of the code: codelen = %d \n", k - 512);
	printf("Compressibility: codelen/textlen = %5.1f(%%)\n",
		(k-512)*100.0/strlen(orig));

 	k = deHuffman(new, 500L, code, k);
	if (k < 0) {
		printf("It failed to decoding. \n");
		exit(1);
	}

	printf("\nDecoded text: length %ld character \n", k);
	printf(">");
	for (i = 0; i < k; i++) printf("%c", new[i]);
		printf("\n");

	return 0;
}


long enHuffman(unsigned char *code, long clen,
               unsigned char *orig, long tlen)
{
    int  i, k;
    long c, len;
    int  min1, min2;
    long max;
    int root;
	int parent;
    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;

	// Compute the frequency of occurrence of each character
	for (i = 0; i < NODE_SIZE; i++) node[i].count = 0;
	for (i = 0; i < tlen; i++) node[orig[i]].count++;

    // Adjust so that the value of the maximum frequency of occurrence does not exceed 2 bytes
    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;
            }

    // Output the appearance frequency of each character
    for (i = 0; i < CHAR_SIZE; i++) {
        *code++ = (node[i].count >> 8) & 0xff;
        *code++ = node[i].count & 0xff;
    }

    /* EOF */
    node[CHAR_SIZE].count = 1;

    // Construct the binary tree
	// Sentinels
    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;
	
	// Coding each Character
	for (c = 0, i = 0, len = 2*CHAR_SIZE, bitp = bit; ; c++) {
		k = (c == tlen) ? CHAR_SIZE : orig[c];

		// Get codeword
		do {
			parent = node[k].parent;
			*bitp++ = (node[parent].left == k) ? 0 : 1;
			
			// add noize test
			/* int r = rand()%(tlen+1);
			if (i == r) {
				// *bitp++ = rand()%2; -> It failed to decoding.
				*bitp++ = rand()%1;
			} */
			k = parent; 

		} while (k != root);

		// Output in reverse order
		do {
			if (*--bitp) *code |= bit1[i];
			else         *code &= bit0[i];
			/* printf("%d", code[c]);*/
			if (++i == 8) {
				code++;
				if (++len > clen) return 0;
 				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)
	{
		//printf("clen: %lf \n", clen);
		return -1L;
	}

    // Set the frequency of occurrence of each character
    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;

    // Coding Huffman tree
    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;
            
    // Decoding
    for (i = 0, len = 0, c = 2*CHAR_SIZE; ; ) {
        // Get the character nodes corresponding to the cordword
        k = root;
        do {
            int parent = k;
            k = (*code & bit1[i]) ? node[k].right : node[k].left;
            if (k >= parent) return -1L;     // impossible
            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;
}

（長文すみません）
上記のウェブサイトに載っていたのはハフマン符号に関する部分だけなので、ハミング符号についてはまだ実装していません。
"aaaabbbccd"と入力したところ、

The length of the text: textlen = 10
The length of the code: codelen = 3
Compressibility: codelen/textlen = 30.0(%)

と表示されました。"aaaabbbccd"ですと圧縮前は20bit、圧縮後は19bitとなるので、これをtextlenとcodelenに表示させたいのですが上手くいきません。
エラーの追加は今はenHuffman関数内に記述しています。code[c]を表示させると0が24個表示され、20個ではなく24個ある点と、後にハミング符号で誤り訂正を考えるとエラーの追記をする場所はここでいいのか？という点が疑問です。

ハミング符号を実装する前にまずはこの3点を理解、解決したいです。
他のトピックよりも長文で面倒そうなのは自覚していますが、どうかお力添え頂きたく思います。
よろしくお願いします。

#2

オフトピック

このコードをコンパイルしたら、ポインタを符号の有無が違う所に渡している、printfに渡すデータの型が間違っているなどの大量の警告が出ましたが、一旦おいといて…

ブレイゴさんが書きました: "aaaabbbccd"と入力したところ、

The length of the text: textlen = 10
The length of the code: codelen = 3
Compressibility: codelen/textlen = 30.0(%)

と表示されました。

これはバイト単位ですね。

ブレイゴさんが書きました: "aaaabbbccd"ですと圧縮前は20bit、圧縮後は19bitとなるので、これをtextlenとcodelenに表示させたいのですが上手くいきません。

「圧縮前」としては与えられた入力に含まれる文字のみを固定長のコードで表す時の(復号するために必要なテーブルなどの分を除いた)コード本体のビット数、
「圧縮後」としては与えられた入力をハフマン符号で表す時のコード本体のビット数
を出力したいということですね。
実装せずにうまくいくことはありえないと思いますが、何か試したのですか？
試したのであれば、それを提示していただけますか？

ブレイゴさんが書きました: code[c]を表示させると0が24個表示され、20個ではなく24個ある点と

これはどのような入力の時のどの時点での「code[c]」(とは何か？)を、どのようにして表示させましたか？

ブレイゴさんが書きました: 後にハミング符号で誤り訂正を考えるとエラーの追記をする場所はここでいいのか？という点が疑問です。

ブレイゴさんのいう「ハミング符号」の定義が確定できませんが、自分の知っているハミング符号ではブロック単位で符号化を行うので、このように1ビット情報が生成されただけの段階で情報を破壊してしまうのはよくないでしょう。
また、自分の知っているハミング符号では、コメントアウトされたコードのような余計なビットが追加されるタイプの誤りには対応出来ないはずです。

metaphor · #3

サイトのリンクを正しい物にして（よく確認して）下さい。プログラムは初歩的なエラーを吐くし、サイトはhttpを直しても出ないし。落ち着いて、フォーラムルールをお読み下さい。

#4

metaphor さんが書きました:サイトはhttpを直しても出ないし。

とりあえずGoogleのキャッシュは閲覧できたので置いておきますね。
huffman (キャッシュ)
キャッシュのアーカイブ

metaphor · #5

あ、どうもありがとうございます。（気がつきませんでした。）

metaphor · #6

huffman-test.c を提示して下さいね。

ブレイゴ · #7

オフトピック

引用とか使い方間違っていたら申し訳ない

みけCAT さんが書きました: 「圧縮前」としては与えられた入力に含まれる文字のみを固定長のコードで表す時の(復号するために必要なテーブルなどの分を除いた)コード本体のビット数、
「圧縮後」としては与えられた入力をハフマン符号で表す時のコード本体のビット数
を出力したいということですね。

そうです！
0と1からなる文字列の長さをstrlen()で取得すれば出来るかな、と記述していたのですが、すみません、完成できなかったのでここに投稿しようとソースコードを整形していた際に削ってしまいました。
ごちゃついて収拾がつかなくなったのでここに投稿した次第です。

みけCAT さんが書きました: これはどのような入力の時のどの時点での「code[c]」(とは何か？)を、どのようにして表示させましたか？

こっちは整形する際、変に弄って勘違いしていただけのようです。入力は同様に"aaaabbbccd"、場所と方法は166行目です。

コード:

/* printf("%d", code[c]);*/

The length of the code: codelen = 3
これをbitで表記（3*8=24）しているだけですね。

みけCAT さんが書きました: コメントアウトされたコードのような余計なビットが追加されるタイプの誤りには対応出来ないはずです。

ビットを追加するのではなく、rand()関数で適当な場所の0と1を反転するよう書き換えてみます。

ブレイゴ · #8

metaphor さんが書きました: サイトのリンクを正しい物にして（よく確認して）下さい。

hを抜いてしまったのは僕のクセです、すみません。
http://www.nicklib.com/library/algo/h/huffman.html

metaphor さんが書きました: プログラムは初歩的なエラーを吐くし

表示される結果は目指しているものではありませんが、投稿したソースコードでの動作自体は確認済みなのですが……。

metaphor さんが書きました: huffman-test.c を提示して下さいね。

投稿したソースコードはリンク先のhuffman.cとhuffman-test.cをひとつにまとめたものです（歪ではありますが）。
みけCATさんがキャッシュを貼ってくださったので、そちらからDLできると思います。
一応、貼っておきますね。

コード:

#include "huffman.c"

main()
{
    int      i;
    long     k;
    unsigned char orig[500], code[1000], new[500];

    printf("--- ハフマン符号によるデータ圧縮 ---\n");
    printf("テキストを入力して下さい（入力例 aaaabbbbccdde）\n");
    scanf("%s", orig);

    k = enHuffman(code, 1000L, orig, (long)strlen(orig));
    if (k < 0) {
        printf("符号化できませんでした\n");
        exit(1);
    }

    printf("\n各文字の出現頻度\n");
    for (i = 0; i < 512; i += 2)
        if (code[i] != 0 || code[i+1] != 0)
            printf("文字 %c、頻度 %d\n", i/2, code[i]*256+code[i+1]);
    printf("\nテキストの長さ textlen = %d\n",  strlen(orig));
    printf("符号の長さ     codelen = %ld\n", k - 512);
    printf("圧縮率 codelen/textlen = %5.1f (%%)\n\n",
           (k-512)*100.0/strlen(orig));

    k = deHuffman(new, 500L, code, k);
    if (k < 0) {
        printf("復号できませんでした\n");
        exit(1);
    }

    printf("復号されたテキスト： 長さ %ld 文字\n", k);
    for (i = 0; i < k; i++) printf("%c", new[i]);
    printf("\n");
    exit(0);
}

		8月 2025
日	月	火	水	木	金	土
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31

ハフマン符号とハミング符号

ハフマン符号とハミング符号

Re: ハフマン符号とハミング符号

Re: ハフマン符号とハミング符号

Re: ハフマン符号とハミング符号

Re: ハフマン符号とハミング符号

Re: ハフマン符号とハミング符号

Re: ハフマン符号とハミング符号

Re: ハフマン符号とハミング符号