赫夫曼编码

2013-02-28 23:19:21   最后更新: 2015-08-06 23:46:18   访问数量:755




赫夫曼编码是一种应用广泛并且非常有效的压缩技术,一般可以压缩掉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]); } }

 

 






读书笔记      技术帖      算法      算法导论      数据结构      龙潭书斋            tree      贪心算法      贪心      赫夫曼编码      code      编码      解码      压缩     


京ICP备15018585号