赫夫曼编码
2013-02-28 23:19:21 最后更新: 2015-08-06 23:46:18 访问数量：1271
问题描述
赫夫曼编码是一种应用广泛并且非常有效的压缩技术，一般可以压缩掉20%到90%
赫夫曼编码使用一张字符出现频度表，记录每个字符出现的频度，根据每个字符出现的频度来进行不定长编码，即对于出现频度大的字符使用尽量短的编码，这样，与定长编码相比，可以很大幅度的节省空间
对于一个编码方式，最重要的就是可解码，因此，任何一个字符的编码都不能是另一个字符的编码的前缀，因此对于一个编码树来说，每一个支路上最多只能有一个字符的存在，因此，所有数据必须都放到叶子节点中
与Shannon-Fano编码的最大不同是，赫夫曼编码使用自底向上的方式进行编码，使用贪心策略，将当前频度最小的字符设置为叶子，这样可以保证赫夫曼树的最优化
根据哈夫曼树的哈夫曼编码方式如下图所示
算法代码
/*
* file: main.c
* author: 龙泉居士
* date: 2013-02-28 09:56
*/
#include <stdio.h>
#include "function/function.h"
int main ()
{
int alpha_array[20];
int count=0;
printf ("Please input the array, end by 9999:\n");
while (1)
{
scanf ("%d", &alpha_array[count]);
if (alpha_array[count] == 9999)
break;
++count;
}
Node *root = create_HuffmanTree (alpha_array, count);
print_tree (root, count);
free_tree (root, count);
return 0;
}
/*
* file: function.h
* author: 龙泉居士
* date: 2013-02-28 20:21
*/
#ifndef FUNCTION_H_20130227
#define FUNCTION_H_20130227
typedef struct Node
{
int value;
struct Node *left;
struct Node *right;
int isalpha;
} Node;
Node *create_HuffmanTree(int *a, int size);
void eton (int *a, Node **node_array, int size);
Node *create_tree (Node **node_array, int size);
void exch (Node *na, Node *nb);
Node *find_min (Node **node_array, int size);
void print_tree (Node *root, int size);
void free_tree (Node *root, int size);
#endif
/*
* file: function.c
* author: 龙泉居士
* date: 2013-02-28 20:21
*/
#include <stdio.h>
#include <malloc.h>
#include "function.h"
Node *create_HuffmanTree (int *a, int size)
{
Node **node_array = (Node **)malloc(sizeof(Node *)*size);
eton (a, node_array, size);
Node *root = create_tree(node_array, size);
free(node_array);
return root;
}
void eton (int *a, Node **node_array, int size)
{
int i;
for (i=0; i<size; ++i)
{
Node *n = (Node *)malloc(sizeof(Node));
n->value = a[i];
n->isalpha = 1;
n->left = n->right = NULL;
node_array[i]=n;
}
}
Node *create_tree (Node **node_array, int size)
{
if (size < 2)
return node_array[0];
Node *left_node = find_min(node_array, size);
--size;
exch (left_node, node_array[size]);
left_node = node_array[size];
Node *right_node = find_min(node_array, size);
--size;
exch (right_node, node_array[size]);
right_node = node_array[size];
Node *n = (Node *)malloc(sizeof(Node));
n->value = left_node->value + right_node->value;
n->left = left_node;
n->right = right_node;
n->isalpha = 0;
node_array[size] = n;
++size;
return create_tree (node_array, size);
}
void exch (Node *na, Node *nb)
{
Node *tmp = (Node *)malloc(sizeof(Node));
tmp->value = na->value ;
tmp->left = na->left ;
tmp->right = na->right ;
tmp->isalpha = na->isalpha;
na->value = nb->value ;
na->left = nb->left ;
na->right = nb->right ;
na->isalpha = nb->isalpha;
nb->value = tmp->value ;
nb->left = tmp->left ;
nb->right = tmp->right ;
nb->isalpha = tmp->isalpha;
free(tmp);
}
Node *find_min (Node **node_array, int size)
{
int i;
Node *min = node_array[0];
for (i=1; i<size; ++i)
if (node_array[i]->value < min->value)
min = node_array[i];
return min;
}
typedef struct TreeNode
{
Node *n;
int deep;
}TreeNode;
void print_tree (Node *root, int size)
{
if (root->isalpha)
{
printf ("0: %d\n", root->value);
return;
}
TreeNode **node_stack = (TreeNode **)malloc(sizeof(TreeNode *)*size);
int stack_size = 0;
Node *tmp = root;
int *code_array = (int *)malloc(sizeof(int)*size);
int array_size = 0;
int deep = 0;
while (1)
{
while (!tmp->isalpha)
{
TreeNode *n = (TreeNode *)malloc(sizeof(TreeNode));
n->n = tmp;
n->deep = deep;
node_stack[stack_size] = n;
stack_size++;
tmp = tmp->left;
++deep;
code_array[array_size] = 0;
array_size++;
}
int i;
for (i=0; i<array_size; ++i)
printf ("%d ", code_array[i]);
printf (": %d\n", tmp->value);
if (stack_size == 0)
{
free(code_array);
free(node_stack);
break;
}
--stack_size;
deep = node_stack[stack_size]->deep;
tmp = node_stack[stack_size]->n->right;
free(node_stack[stack_size]);
array_size = deep;
code_array[array_size]=1;
++array_size;
++deep;
}
}
void free_tree (Node *root, int size)
{
Node *tmp = root;
Node **node_stack = (Node **)malloc(sizeof(Node *)*size);
int stack_size = 0;
while (1)
{
while (!tmp->isalpha)
{
node_stack[stack_size] = tmp;
++stack_size;
tmp = tmp->left;
}
free(tmp);
--stack_size;
if (stack_size == 0)
break;
tmp = node_stack[stack_size]->right;
free (node_stack[stack_size]);
}
}
微信公众号
欢迎关注微信公众号，以技术为主，涉及历史、人文等多领域的学习与感悟，每周三到七篇推文，只有全部原创，只有干货没有鸡汤
