huffman.zip

  • snailwft
    了解作者
  • C/C++
    开发工具
  • 7KB
    文件大小
  • zip
    文件格式
  • 0
    收藏次数
  • 1 积分
    下载积分
  • 0
    下载次数
  • 2020-09-29 11:15
    上传日期
哈夫曼压缩和解压缩c语言代码,测试可行。
huffman.zip
  • huffman
  • divoom_huffman_decode.c
    16.9KB
  • anyka_types.h
    6.1KB
  • divoom_huffman_decode.h
    1.6KB
内容介绍
#include <string.h> #include <stdlib.h> #include <stdlib.h> #include <stdio.h> #include <string.h> #include "anyka_types.h" #define CODE_SIZE 256 //至少是 2*N-1 //定义哈夫曼结点类型 typedef struct _divoom_huffman_tree_node { uint8 ch; //结点值 int weight; //权重 int parent; //父结点 int lchild; //左孩子结点 int rchild; //右孩子结点 }divoom_huffman_tree_node, *Pdivoom_huffman_tree_node; //定义哈夫曼编码类型 typedef struct _divoom_huffman_code { uint8 ch; //结点值 0~255 uint16 weight; //该结点的权值 int start; uint8 cd[CODE_SIZE + 1]; //存放的哈夫曼码 }divoom_huffman_code, *Pdivoom_huffman_code; typedef struct _divoom_huffman_data_weight { uint8 ch; uint16 weight; }divoom_huffman_data_weight, *Pdivoom_huffman_data_weight; uint8 divoom_huffman_str_to_byte(uint8 *pstr) //把8个字符压缩成一个字节 { uint8 b = 0x00; int i = 0; for (i = 0; i < 8; i++) { b = b << 1; if (pstr[i] == '1') { b = b | 0x01; } } return b; } void divoom_huffman_byte_to_str(uint8 ch, uint8 *buf) { int i = 0; for (i = 0; i < 8; i++) { if (ch & (1 << 7-i)) buf[i] = '1'; else buf[i] = '0'; } buf[8] = '\0'; } int divoom_huffman_compare(Pdivoom_huffman_code hc, int n, char* str) { int i = 0; for (i = 0; i < n; i++) { if (strcmp(hc[i].cd, str) == 0) { return i; } } return -1; } void divoom_huffman_printf_code(Pdivoom_huffman_code hc, uint8 ch_num) { int i = 0, j = 0; for (i = 0; i < ch_num; i++) //外循环输出每个哈夫曼编码 { divoom_print("%x %d——", hc[i].ch, hc[i].start); for (j = hc[i].start; j <= ch_num; j++) //内循环输出哈夫曼编码,hc[i].start 编码起始位置 { divoom_print("%c", hc[i].cd[j]); } j = hc[i].start; divoom_print("--%s\n", &hc[i].cd[j]); } } /** * * NAME divoom_huffman_create_tree * * @brief 创建哈夫曼树 * * @param[in] ht 哈夫曼树 n 字符个数 * * @author wangft * * @return none * */ void divoom_huffman_create_tree(Pdivoom_huffman_tree_node ht, int n) { int i, k; int lnode, rnode; int min1, min2; for (i = 0; i < 2 * n - 1; i++) { //所有结点的相关域值初值 -1 ht[i].parent = ht[i].lchild = ht[i].rchild = -1; } for (i = n; i <= 2 * n - 2; i++) { min1 = min2 = 32767; lnode = rnode = -1; for (k = 0; k <= i - 1; k++) { if (ht[k].parent == -1) { //只在尚未构造二叉树中查找 if (ht[k].weight < min1) { //权重比左边小 min2 = min1; //保证左边的最小 rnode = lnode; min1 = ht[k].weight; //记录权重 lnode = k; //记录下标 } else if (ht[k].weight < min2) { //权重比右边小 min2 = ht[k].weight; rnode = k; } } } ht[i].weight = ht[lnode].weight + ht[rnode].weight; //合并后的权重 ht[i].lchild = lnode; //HT[i]作为父结点 ht[i].rchild = rnode; ht[lnode].parent = i; ht[rnode].parent = i; } } /** * * NAME divoom_huffman_create_code * * @brief 创建哈夫曼码 * * @param[in] ht 哈夫曼树 hc 存放哈夫曼码指针 n 字符个数 * * @author wangft * * @return none * */ void divoom_huffman_create_code(Pdivoom_huffman_tree_node ht, Pdivoom_huffman_code hc, int n) { int f; //父结点 int c, i; divoom_huffman_code h; for (i = 0; i < n; i++) { h.start = n; //开始位置,倒叙插入 h.cd[h.start + 1] = '\0'; c = i; //初始 h.ch = ht[i].ch; h.weight = ht[i].weight; f = ht[i].parent; //f 保存该结点父结点 while (f != -1) { //因为创建哈夫曼树时,所有无关都置 -1,所以根结点父结点为 -1,表示结束 if (ht[f].lchild == c) { //左边就压入 0 h.cd[h.start] = '0'; h.start--; } if (ht[f].rchild == c) { //右边就压入 1 h.cd[h.start] = '1'; h.start--; } c = f; //此时父结点当作子结点 f = ht[f].parent; //向上遍历,父结点进行同样操作 } h.start++; //记录哈夫曼编码最开始的字符位置 hc[i] = h; //一个哈夫曼结点的编码 } } /** * * NAME divoom_huffman_compress_init * * @brief 对要编码的数据先进行权值统计 * * @param[in] buff_in 要编码的数据 in_len 要编码的数据的长度 c_num 统计有多少个字符 * * @author wangft * * @return 返回字符权值表 * */ Pdivoom_huffman_data_weight divoom_huffman_compress_init(uint8 *buff_in, uint16 in_len, uint8 *c_num) { uint8 ch = 0, ch_num = 0; uint16 weight[CODE_SIZE] = {0}; Pdivoom_huffman_data_weight pdata_weight_array = NULL; uint16 i = 0, j = 0; for (i = 0; i < in_len; i++) { //统计字符的权值 ch = buff_in[i]; weight[ch]++; } for (i = 0; i < CODE_SIZE; i++) { if (weight[i] > 0) //统计有多少个字符 { ch_num++; } } pdata_weight_array = (Pdivoom_huffman_data_weight)divoom_malloc(sizeof(divoom_huffman_data_weight) * ch_num); if (pdata_weight_array == NULL) return NULL; memset(pdata_weight_array, 0, sizeof(divoom_huffman_data_weight) * ch_num); for (i = 0; i < CODE_SIZE; i++) { if (weight[i] > 0) { for (j = 0; j < ch_num; j++) { if (pdata_weight_array[j].weight == 0) { pdata_weight_array[j].weight = weight[i]; //记录该字符的概率 pdata_weight_array[j].ch = i; //记录字符 break; } } } } if (c_num) *c_num = ch_num; return pdata_weight_array; } /** * * NAME divoom_huffman_decode * * @brief 对编码字符串进行解码 * * @param[in] hc 哈夫曼编码 n 字符数 max 最大的字符编码长度 pbuffer 存放编码的缓冲区 buffer_len 编码缓冲区长度 buff_out 存放解码之后的数据缓冲区 out_len 存放解码之后的数据长度 unpre_num 未压缩的数据长度 * * @author wangft * * @return none * */ void divoom_huffman_decode(Pdivoom_huffman_code hc, int n, int max, uint8 *pbuffer, int buffer_len, uint8 *buff_out, uint16 *out_len, int unpre_num) { int size = 1; //比较长度 int ret = 0; //返回值 int index = 0, i = 0, len = 0; uint8 s[CODE_SIZE] = {0}; uint8 buf[8 + 1] = {0}; uint8 *cmp_buf = (uint8 *)divoom_malloc(max); if (cmp_buf == NULL) return ; memset(cmp_buf, 0, max); for (i = 0; i < buffer_len; i++) { //divoom_print("%x\n", pbuffer[i]); memset(buf, 0, 8); memset(cmp_buf, 0, max); divoom_huffman_byte_to_str(pbuffer[i], buf); //最后一个字节要特别处理 //divoom_print("%s\n", buf); size = 1; strcat(s, buf); //保存未比较过的哈夫曼码,比较过的则移除 //divoom_print("s: %s\n", s); len = strlen(s); if (i == buffer_len -1) //做一个尾部处理 { if (unpre_num % 8 != 0) { len = len - 8 + unpre_num % 8; } } while (size <= len) { strncpy(cmp_buf, s, size); //divoom_print("cmp_buf %s\n", cmp_buf); ret = divoom_huffman_compare(hc, n, cmp_buf); if (ret < 0) { size++; } else { buff_out[index] = hc[ret].ch; //存在则拷贝进去 //divoom_print("str[%d] %x\n", index, str[index]); index++; //同时把s中已经对应上的编码丢弃 memmove(s, s+size, len-size + 1); //移动字符串 memset(cmp_buf, 0, m
评论
    相关推荐
    • Huffman 编码
      实现了Huffman编码算法: 1、使用链表结构。 2、使用《数据结构》(严蔚敏,C语言版)中给出的算法; 3、增加预先排序的功能的算法
    • huffman编码
      huffman编码合集,里面收录了各种数据结构的Huffman编码
    • huffman 编码
      对一个灰度图像进行huffman编码,C++
    • 实现Huffman编码
      HUFFMAN编码又称哈夫曼编码,是一种可变长编码方式,是由美国数学家David Huffman创立的,是二叉树的一种特殊转化形式。编码的原理是:将使用次数多的代码转换成长度较短的代码,而使用次数少的可以使用较长的编码,...
    • huffman编码
      在MFC框架下实现huffman编码,同时计算平均码长,信息熵,编码效率
    • Huffman编码
      1.要求对文件进行Huffman编码的算法,以及对一编码文件进行解码的算法 2.熟练掌握二叉树的应用;具体要求如下: 最小冗余码/哈夫曼码
    • Huffman 编码
      VC++完全版 能够直接在VC6.0上运行
    • huffman编码
      huffman编码(编码加解码三个),这个编码是信息论以及各种数据结构的实验,都有用的东西
    • Huffman编码
      数据结构 C++ Huffman编码 对文件进行压缩,生成一个huf文件,还可以解压缩。
    • Huffman 编码
      哈夫曼压缩算法,刚开始学习的可以下载下来参考参考,代码注释比较完整