tags: [‘C/C++’, ‘’]
原文链接：
说起 的算法原理其实很简单，难在实现过程中对细节的控制，比如 字串流转换成 比特流，比特流转换回 字串流，这类操作极易出错；再比如要使 解码过程效率更高，需要让 游标指针在逐个获取 比特位的过程中高效地从根节点移动到目标节点，从而获取目标节点对应的解码字符；再就是针对解码所必须的 字符集频率表如何设计才能最大限度减少体积 。总之我的体会就是，若要亲手实现一个各方面鲁棒性良好的Code 其过程并不那么轻松 。
输入数据测试
【C语言实现Huffman的编码和解码】为检测Tree的构建是否正常，我写了一个测试功能，可以输入字符以及频率来构建一颗Tree，并打印Tree的 树形图和 编码表，下面展示的是我以数据 {A:1, B:2, C:3, D:4}的构建效果：
文件的字符集频率表的设计
下面说说文件的压缩和解压，文件存储不光要存储压缩数据，还需要在文件头部额外存储 字符集频率表，目的是为了文件解压时，可根据 字符集频率表重新构建回Tree，进而在构建的Tree上将压缩数据解码成原始数据 。字符集频率表应最大限度减少体积，这样才能降低文件的总体积 。所以根据上述说法，文件内容将分为两部分： 文件头部信息块和 数据区，文件头部信息块内含 文件头标识和 字符集频率表 。
还是拿上面的数据 {A:1, B:2, C:3, D:4}为案例，我的 文件头部信息块设计如下：
文件头的两个字节是类型标识 ：FX，用来标识这是一个压缩文件，通过扫描文件头标识，可判断对该文件的操作是压缩还是解压 。
文件头标识之后是 字符集频率表，第一个字节是表长，特别注意，它的值在 0 ~ 255之间，表示的表长的范围是 1 ~ 256之间，所以字符集 {A:1, B:2, C:3, D:4}的表长是3而不是4 。接下来以每5个字节代表一个字符信息块，其中1个字节存储字符编码剩下4个字节存储该字符的频率，例如 A的频率是1，所以4个字节中存放的是 {0,0,0,1}，由此可见我的设计尚有压缩空间，如果我用2个 比特位标识该字符的频率所占用的字节数，那么4个字节的占用将压缩到1个字节，整个 字符集频率表在理想状况下能缩小一倍以上 。如我目前存储上述 字符集频率表信息需要 1+5*4=21字节，采用这种方式能压缩到 1+2*4=9字节 。这点留待以后再优化吧 。
文件的压缩和解压测试
拿源文件本身来测试压缩和解压：
文章插图
源程序
程序仅使用C的常用标准库函数，且编写采用 C89标准，其目的是为了让程序拥有更广泛的适应性，以下是程序的关键代码，可供参考：
/********************************************* Huffman Code Demo* Copyright (C) i@foxzzz.com** C implementation of the Huffman Code's* encoding and decoding.*********************************************/#include #include #include #include #include /*数据列表长度*/#define LIST_SIZE 256/*构建Huffman树需要产生的森林长度*/#define FOREST_SIZE (LIST_SIZE * 2 - 1)/*单个数据产生的Huffman编码文本串的最大容量*/#define CODE_MAX 2048/*文件路径长度*/#define PATH_MAX 1024/*文件头标识*/const char FILE_HEADER_FLAG[] = { 'F', 'X' };/*节点标识*/enum {NODE_FLAG_ROOT,/*根节点*/NODE_FLAG_LEFT,/*左孩子节点*/NODE_FLAG_RIGHT/*右孩子节点*/};/*节点类型*/enum {NODE_TYPE_DATA,/*数据节点*/NODE_TYPE_BLANK/*空节点*/};/*文件类型*/enum {FILE_TYPE_NULL,/*读取出错*/FILE_TYPE_ENCODE,/*原始数据文件*/FILE_TYPE_DECODE,/*压缩数据文件*/};/*字节类型*/typedef unsigned char Byte;/*Huffman树节点*/typedef struct _tNode {int type;/*节点类型*/int data;/*节点数据*/int weight;/*节点权重*/char code[CODE_MAX];/*Huffman编码*/struct _tNode* left;/*左孩子*/struct _tNode* right;/*右孩子*/}Node, * pNode;/*Huffman树信息*/typedef struct _tHuffmanTree {pNode root;/*根节点*/int total/*总字节数*/;}HuffmanTree, * pHuffmanTree;/*得到当前时间戳*/struct timeval startTimestamp() {struct timeval stamp;gettimeofday(&stamp, NULL);return stamp;}/*计算从时间戳到当前时间的毫秒*/double endTimestamp(struct timeval start) {int diff_sec = 0;double start_msec = 0;double end_msec = 0;struct timeval end;gettimeofday(&end, NULL);diff_sec = (int)(end.tv_sec - start.tv_sec);start_msec = (double)start.tv_usec / 1000.0;end_msec = (diff_sec * 1000) + ((double)end.tv_usec / 1000.0);return (end_msec - start_msec);}/*创建Huffman树的数据节点*/pNode createDataNode(int data, int weight) {pNode node = (pNode)malloc(sizeof(Node));memset(node, 0, sizeof(Node));node->type = NODE_TYPE_DATA;node->data = http://www.kingceram.com/post/data;node->weight = weight;return node;}/*创建Huffman树的空节点*/pNode createBlankNode(int weight) {pNode node = (pNode)malloc(sizeof(Node));memset(node, 0, sizeof(Node));node->type = NODE_TYPE_BLANK;node->weight = weight;return node;}/*将Huffman树节点添加到森林列表*/void addNodeToList(pNode nodelist[], int size, pNode node) {int index;for (index = 0; index
- 48K到16K 基于C语言实现PCM音频流或音频文件重采样
- 计算机底层加法/乘法实现
- 物联网规则引擎设计
- 自定义vue组件--实现多图片上传
- 含源码，用Python实现浪漫烟花
- 八 音频——C语言生成正弦波并用 I2S 输出
- 一 MATLAB智能算法实现
- 这款实现 C++、Java、Python 代码互译的工具，很强！
- matlab实现 特征值分解用于数据压缩
- fifo2mig_axi 基于 DDR3 的串口传图帧缓存系统设计实现