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)

相关推荐

  • C语言实现BMP图像边缘检测处理

    本文实例为大家分享了C语言实现BMP图像边缘检测处理的具体代码,供大家参考,具体内容如下 以Sobel算子为例,其余模板算子卷积代码部分同Sobel算子.如:高斯算子.拉普拉斯算子等 #include <stdio.h> #include <stdlib.h> #include <Windows.h> #include <math.h> int main(int* argc, char** argv) { FILE* fp = fopen("./0

  • C语言实现BMP图像细化处理

    细化(thinning)算法有很多,我们在这里介绍的是一种简单而且效果很好的算法,用它就能够实现从文本抽取骨架的功能.我们的对象是白纸黑字的文本,但在程序中为了处理的方便,还是采用 256 级灰度图,不过只用到了调色板中 0 和 255 两项. 所谓细化,就是从原来的图中去掉一些点,但仍要保持原来的形状.实际上,是保持原图的骨架.所谓骨架,可以理解为图象的中轴,例如一个长方形的骨架是它的长方向上的中轴线:正方形的骨架是它的中心点:圆的骨架是它的圆心,直线的骨架是它自身,孤立点的骨架也是自身.那么

  • C语言实现哈夫曼编码

    本文实例为大家分享了C语言实现哈夫曼编码的具体代码,供大家参考,具体内容如下 代码来自于<小甲鱼C++快速入门> 主程序main.cpp #include "stdafx.h" #include <stdlib.h> #include "huffman.h" int main() { htTree *codeTree = buildTree("I love wwwwwwwwwFishC.com!");//建立哈夫曼树 hl

  • C语言实现BMP图像闭运算处理

    闭运算可以把比结构元素小的特定图像细节出去,同时保证不产生全局的几何失真.填充比结构元素小的缺口或孔,搭接短的间断而起到连接作用. 运算:也就是先膨胀后腐蚀. #include <stdio.h> #include <stdlib.h> #include <Windows.h> int main(int* argc, char** argv) { FILE* fp = fopen("./threshold.bmp", "rb");

  • 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) 从左到右把上述频率按从小到大的

  • 用R语言实现霍夫曼编码的示例代码

    可读性极低,而且其实也没必要用R语言写,图个乐罢了 p=c(0.4,0.2,0.2,0.1,0.1)###输入形如c(0.4,0.2,0.2,0.1,0.1)的概率向量,即每个待编码消息的发生概率 p1=p###将概率向量另存,最后计算编码效率要用 mazijuzhen=matrix(,nrow=length(p),ncol=length(p)-1)###码字矩阵:第i行对应向量p的第i个分量所对应的那个待编码消息的编码后的码字 group=matrix(c(1:length(p),rep(NA

  • 利用Python和C语言分别实现哈夫曼编码

    目录 1.C语言实现 1.1代码说明 1.2运行结果 2.Python实现 2.1代码说明 2.2运行结果 1.C语言实现 1.1代码说明 a  创建双向链表: 在创建哈夫曼树的过程中,需要不断对结点进行更改和删除,所以选用双向链表的结构更容易 '''C #include <stdlib.h> #include <stdio.h> #include <windows.h> //哈夫曼树结构体,数据域存储字符及其权重 typedef struct node { char

  • 基于C++实现的哈夫曼编码解码操作示例

    本文实例讲述了基于C++实现的哈夫曼编码解码操作.分享给大家供大家参考,具体如下: 哈夫曼编码是一个通过哈夫曼树进行的一种编码,一般情况下,以字符:'0'与'1'表示.编码的实现过程很简单,只要实现哈夫曼树,通过遍历哈夫曼树,这里我们从每一个叶子结点开始向上遍历,如果该结点为父节点的左孩子,则在字符串后面追加"0",如果为其右孩子,则在字符串后追加"1".结束条件为没有父节点.然后将字符串倒过来存入结点中. C++实现代码如下: #include<iostre

  • JS实现的哈夫曼编码示例【原始版与修改版】

    本文实例讲述了JS实现的哈夫曼编码.分享给大家供大家参考,具体如下: 原始版 function cal(str) { if (typeof str !== 'string' || str.length < 1) { return; } var map = {}; var i = 0; while(str[i]) { map[str[i]] ? map[str[i]]++ : (map[str[i]] = 1); i++; } return map; } function sort(map) {

  • C++实现哈夫曼编码

    本文实例为大家分享了C++实现哈夫曼编码的具体代码,供大家参考,具体内容如下 #include<iostream> #include<string> #include<vector> #include<algorithm> using namespace std; int Max = 300; class tree{ public: char s; int num; tree *left; tree *right; tree(){ s= '!'; num =

  • Java利用哈夫曼编码实现字符串压缩

    赫夫曼编码基本介绍 1) 赫夫曼编码也翻译为 哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式, 属于一种程序算法 2) 赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一. 3) 赫夫曼编码广泛地用于数据文件压缩.其压缩率通常在 20%-90%之间 4) 赫夫曼码是可变字长编码(VLC)的一种.Huffman 于 1952 年提出一种编码方法,称之为最佳编码 在通信领域中几种信息处理方式的区别(以字符串" i like like like java do you li

  • C语言实现BMP图像处理(直方图均衡化)

    本文实例为大家分享了C语言实现BMP图像直方图均衡化处理的具体代码,供大家参考,具体内容如下 计算步骤: 1)统计各灰度值的概率: 2)计算了累积概率直方图(CDF): 3)取整扩展:Tk = int[ (L-1)*Tk]; #include <Windows.h> #include <stdlib.h> #include <stdio.h> #include <math.h> int main(int* argc, char** argv) { FILE*

  • 如何用Java实现啥夫曼编码

    大家可能会想,程序和第三方提供了很多压缩方式,何必自己写压缩代码呢?不错,如GZIP这样的压缩工具很多,可是在某些情况下(如文本内容小且字符不重复),GZIP压缩后会比原始文本还要大.所以在某些特殊情况下用自己的压缩方式可以更优. 大家可能早已忘记了在学校学习的哈夫曼知识,可以先在百度百科了解一下哈夫曼知识:http://baike.baidu.com/view/127820.htm 哈夫曼思想:统计文本字符重复率,求出各字符权值,再构造出一颗最优二叉树(又称哈夫曼树),然后给每个叶子结点生成一

随机推荐