ホフマンコーディング
4854 ワード
ハフマン符号化(Huffman Coding)は符号化方式であり、ハフマン符号化は可変ワード長符号化(VLC)の一種である.ハフマンは1952年に、文字出現確率に完全に基づいて異字ヘッドの平均長が最も短い符号語を構築し、最適符号化と呼ばれる場合があり、一般的にハフマン符号化(ホフマン符号化とも呼ばれる場合もある)と呼ばれる符号化方法を提案した.
ホフマン符号化は最適二叉木の実現である.なぜコードを採用するのですか?コンピュータ内の情報は、文字コードのASCIIコード、BCDコードなど、バイナリで格納されています.しかし、大量のバイナリの記憶は空間の浪費をもたらし、一部のデータには0や1が多く含まれていることを知っていて、余分な情報を除去することができて、多くの圧縮アルゴリズムが現れました.よく見られるのはLZW、DEFLAT、LZなどです(rukiさんの指摘に感謝しますが、LZシリーズの圧縮率は確かにホフマン符号化より高いです).しかし、なぜホフマン符号化を使わないのですか?理論的にはホフマン符号化の効率は最高ですが、実行効率は悪く、つまりデータ圧縮に要する時間が長いので、1 Gのファイルを圧縮して30分も使うことを望んでいないのではないでしょうか.従って、前述したアルゴリズムは、ホフマン符号化よりも速度が速いだけで、データ圧縮率はホフマン符号化よりも高くない.なぜホフマン符号化を知っているのでしょうか?
実はホフマン符号化はデータ圧縮の分野では少ないが,通信の分野では広く応用されている.ホフマン符号化の基本原理は,底から上へ二叉木を生成し,複数の二叉木が現れるとそれを統合することである.例:
データのセットがあります3 4 7 8 9 12 16
空色の数字は元のデータで、赤い数字はその下の2つの数字の和です.
ステップ1:
7
3 4
ステップ2:
14
7 7
3 4
ステップ3:
14
7 7 17
3 4 8 9
ステップ4:
14
7 7 17 28
3 4 8 9 12 16
ステップ5:サブツリーをマージする
59
31 28
14 17 12 16
7 7 8 9
3 4
コードは次のとおりです.
今日はこれで、次は続きます.:)
ホフマン符号化は最適二叉木の実現である.なぜコードを採用するのですか?コンピュータ内の情報は、文字コードのASCIIコード、BCDコードなど、バイナリで格納されています.しかし、大量のバイナリの記憶は空間の浪費をもたらし、一部のデータには0や1が多く含まれていることを知っていて、余分な情報を除去することができて、多くの圧縮アルゴリズムが現れました.よく見られるのはLZW、DEFLAT、LZなどです(rukiさんの指摘に感謝しますが、LZシリーズの圧縮率は確かにホフマン符号化より高いです).しかし、なぜホフマン符号化を使わないのですか?理論的にはホフマン符号化の効率は最高ですが、実行効率は悪く、つまりデータ圧縮に要する時間が長いので、1 Gのファイルを圧縮して30分も使うことを望んでいないのではないでしょうか.従って、前述したアルゴリズムは、ホフマン符号化よりも速度が速いだけで、データ圧縮率はホフマン符号化よりも高くない.なぜホフマン符号化を知っているのでしょうか?
実はホフマン符号化はデータ圧縮の分野では少ないが,通信の分野では広く応用されている.ホフマン符号化の基本原理は,底から上へ二叉木を生成し,複数の二叉木が現れるとそれを統合することである.例:
データのセットがあります3 4 7 8 9 12 16
空色の数字は元のデータで、赤い数字はその下の2つの数字の和です.
ステップ1:
7
3 4
ステップ2:
14
7 7
3 4
ステップ3:
14
7 7 17
3 4 8 9
ステップ4:
14
7 7 17 28
3 4 8 9 12 16
ステップ5:サブツリーをマージする
59
31 28
14 17 12 16
7 7 8 9
3 4
コードは次のとおりです.
#include <stdio.h>
#define MAX_WEIGHT 10000
#define MAX_LEAF 30
#define MAX_NODE MAX_LEAF*2-1
#define MAX_BIT 12
typedef int data_t;
typedef struct huff_node {
int weight;
int parent;
int lchild;
int rchild;
} huff_t;
typedef struct huff_code {
int bit[MAX_BIT];
int start;
} huff_code_t;
void huffman_tree(huff_t huff_tree[], int num, data_t weight[])
{
int i, j, m1, m2, x1, x2, n = num;
for (i = 0; i < 2 * n - 1; i++) {
huff_tree[i].weight = 0;
huff_tree[i].parent = -1;
huff_tree[i].lchild = -1;
huff_tree[i].rchild = -1;
}
for (i = 0; i < n; i++) {
huff_tree[i].weight = weight[i];
}
for (i = 0; i < n - 1; i++) {
m1 = m2 = MAX_WEIGHT;
x1 = x2 = 0;
for (j = 0; j < n + i; j++) {
if (huff_tree[j].weight < m1
&& huff_tree[j].parent == -1) {
m2 = m1;
x2 = x1;
m1 = huff_tree[j].weight;
x1 = j;
} else if (huff_tree[j].weight < m2
&& huff_tree[j].parent == -1) {
m2 = huff_tree[j].weight;
x2 = j;
}
}
huff_tree[x1].parent = n + i;
huff_tree[x2].parent = n + i;
huff_tree[n + i].weight = huff_tree[x1].weight
+ huff_tree[x2].weight;
huff_tree[n + i].lchild = x1;
huff_tree[n + i].rchild = x2;
}
}
void huffman_code(huff_t arry[], int num)
{
int i, j, c, p;
huff_code_t cd, huff_code[MAX_NODE];
for (i = 0; i < num; i++) {
cd.start = num - 1;
c = i;
p = arry[c].parent;
while (p != -1) {
if (arry[p].lchild == c)
cd.bit[cd.start] = 0;
else
cd.bit[cd.start] = 1;
cd.start--;
c = p;
p = arry[c].parent;
}
for (j = cd.start + 1; j < num; j++)
huff_code[i].bit[j] = cd.bit[j];
huff_code[i].start = cd.start;
}
for (i = 0; i < num; i++) {
for (j = huff_code[i].start + 1; j < num; j++)
printf("%d\t", huff_code[i].bit[j]);
printf("
");
}
}
int main()
{
const int length = 7;
data_t weight[7] = { 3,4,7,8,9,12,16 };
huff_t arry[MAX_NODE];
huffman_tree(arry, length, weight);
huffman_code(arry, length);
printf("
");
return 0;
}今日はこれで、次は続きます.:)