C语言实现BMP图像处理(哈夫曼编码)
作者:傻不拉几的程序员 时间:2022-10-08 02:04:02
哈夫曼(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;
}
来源:https://blog.csdn.net/fengxianghui01/article/details/85253486
标签:C语言,图像处理,哈夫曼编码
0
投稿
猜你喜欢
C#特性 匿名类型与隐式类型局部变量使用介绍
2023-09-29 12:42:50
利用Java自写一个生成ID的工具类
2023-04-24 04:10:08
Java基础教程之HashMap迭代删除使用方法
2023-10-04 02:15:32
java实现超市商品库存管理平台
2022-05-25 10:09:20
ListView通用泛型适配器
2022-06-30 11:52:04
Spring实战之使用注解实现声明式事务操作示例
2021-08-19 07:16:07
Java8 Optional优雅空值判断的示例代码
2021-09-20 09:16:26
C++深浅拷贝和写时拷贝图文详解
2021-06-07 00:12:58
idea插件之mybatis log plugin控制台sql的问题
2023-05-14 06:45:32
C#利用win32 Api 修改本地系统时间、获取硬盘序列号
2021-11-23 06:52:24
Android app启动时黑屏或者白屏的原因及解决办法
2023-06-09 11:32:32
java IO流读取图片供前台显示代码分享
2023-10-01 20:55:26
Spring Security使用Lambda DSL配置流程详解
2021-12-23 19:20:32
Android实现录音静音降噪
2023-01-06 23:46:25
Elasticsearch percolate 查询示例详解
2021-07-15 04:57:54
Struts2实现文件上传功能实例解析
2023-11-04 04:56:13
SpringBoot定制三种错误页面及错误数据方法示例
2022-03-10 01:15:55
Android操作系统之内存回收策略
2021-09-26 06:38:01
Java SSM框架如何配置静态资源加载
2023-03-22 17:40:01
Android批量插入数据到SQLite数据库的方法
2022-09-28 06:18:06