C语言实现BMP图像处理(哈夫曼编码)
哈夫曼(Huffman)编码是一种常用的压缩编码方法,是 Huffman 于 1952 年为压缩文本文件建立的。它的基本原理是频繁使用的数据用较短的代码代替,较少使用的数据用较长的代码代替,每个数据的代码各不相同。这些代码都是二进制码,且码的长度是可变的。
下面给出具体的 Huffman 编码算法:
(1) 首先统计出每个符号出现的频率,上例 S0 到 S7 的出现频率分别为 4/14,3/14,2/14,1/14,1/14,1/14,1/14,1/14。
(2) 从左到右把上述频率按从小到大的顺序排列。
(3) 每一次选出最小的两个值,作为二叉树的两个叶子节点,将和作为它们的根节点,这两个叶子节点不再参与比较,新的根节点参与比较。
(4) 重复(3),直到最后得到和为 1 的根节点。
(5) 将形成的二叉树的左节点标 0,右节点标 1。把从最上面的根节点到最下面的叶子节点途中遇到的 0,1 序列串起来,就得到了各个符号的编码。
产生 Huffman 编码需要对原始数据扫描两遍。第一遍扫描要精确地统计出原始数据中,每个值出现的频率,第二遍是建立 Huffman 树并进行编码。由于需要建立二叉树并遍历二叉树生成编码,因此数据压缩和还原速度都较慢,但简单有效,因而得到广泛的应用。
第一步:实现哈夫曼编码与解码
#include <stdio.h> #include <malloc.h> #include <stdlib.h> #include <string.h> // 结构体 typedef struct Tree { int weight; // 权值 int id; // 后面解码用到 struct Tree * lchild; // 左孩子 struct Tree * rchild; // 右孩子 }TreeNode; // 创建哈夫曼树 TreeNode* createTree(int *arr, int n) { int i, j; TreeNode **temp, *hufmTree; temp = (TreeNode**)malloc(sizeof(TreeNode*)*n); // 创建结构体指针数组 for (i = 0; i < n; ++i) { temp[i] = (TreeNode*)malloc(sizeof(TreeNode)); temp[i]->weight = arr[i]; temp[i]->lchild = temp[i]->rchild = NULL; temp[i]->id = i; } for (i = 0; i < n - 1; ++i) { int small1 = -1, small2; // 存储最小权值的两个节点 for (j = 0; j < n; ++j) // 第一步:找到最开始两个非空节点 { if (temp[j] != NULL && small1 == -1) { small1 = j; continue; } if (temp[j] != NULL) { small2 = j; break; } } for (j = small2; j < n; ++j) // 找到权值最小的两个节点,并将最小的序号赋给small1,次小的赋给small2 { if (temp[j] != NULL) { if (temp[j]->weight < temp[small1]->weight) { small2 = small1; small1 = j; } else if (temp[j]->weight < temp[small2]->weight) { small2 = j; } } } hufmTree = (TreeNode*)malloc(sizeof(TreeNode)); hufmTree->lchild = temp[small1]; hufmTree->rchild = temp[small2]; hufmTree->weight = temp[small1]->weight + temp[small2]->weight; temp[small1] = hufmTree; temp[small2] = NULL; } free(temp); return hufmTree; } // 前序遍历 void PreOrderTraversal(TreeNode* hufmTree) { if (hufmTree) { printf("%d", hufmTree->weight); PreOrderTraversal(hufmTree->lchild); PreOrderTraversal(hufmTree->rchild); } } // 哈夫曼编码 void hufmTreeCode(TreeNode* hufmTree,int depth) { static int code[10],i; if (hufmTree) { if (hufmTree->lchild == NULL && hufmTree->rchild == NULL) { int i=0; printf("权值为%d的节点,哈夫曼编码为:", hufmTree->weight); for (i = 0; i < depth; ++i) { printf("%d", code[i]); } printf("\n"); } else { code[depth] = 0; hufmTreeCode(hufmTree->lchild, depth + 1); code[depth] = 1; hufmTreeCode(hufmTree->rchild, depth + 1); } } } // 哈夫曼解码 // 思想:通过定位ID,找到源码中的位置 void hufmTreeDecode(TreeNode* hufmTree, char a[],char st[]) { int i,arr[100]; TreeNode* temp; for (i = 0; i < strlen(a); ++i) // 转化字符串编码为数组编码 { if (a[i] == '0') arr[i] = 0; else arr[i] = 1; } i = 0; while (i < strlen(a)) { temp = hufmTree; while (temp->lchild != NULL && temp->rchild != NULL) { if (arr[i] == 0) temp = temp->lchild; else temp = temp->rchild; i++; } printf("%c", st[temp->id]); } printf("\n"); free(temp); } int main() { int i, n, arr[100]; printf("输入需要创建的节点个数:\n"); scanf("%d", &n); printf("输入权值:\n"); for (i = 0; i < n; ++i) scanf("%d", &arr[i]); printf("\n请输入每个权值对应的字符:\n"); char st[100]; scanf("%s",st); // 创建哈夫曼树 TreeNode* hufmTree; hufmTree = createTree(arr, n); // 哈夫曼编码 printf("\n哈夫曼编码为:\n"); hufmTreeCode(hufmTree, 0); // 遍历 printf("\n前序遍历:\n"); PreOrderTraversal(hufmTree); // 解码 printf("\n请输入需要解码的码字:\n"); char codeSt[100]; scanf("%s",codeSt); printf("\n解码的码字为:\n"); hufmTreeDecode(hufmTree, codeSt, st); free(hufmTree); system("pause"); return 0; }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。
赞 (0)