霍夫曼编码

✍ dations ◷ 2024-09-20 16:42:01 #数据结构,无损压缩算法,编码理论,数据压缩

霍夫曼编码（英语：Huffman Coding），又译为哈夫曼编码、赫夫曼编码，是一种用于无损数据压缩的熵编码（权编码）算法。由美国计算机科学家大卫·霍夫曼（David Albert Huffman）在1952年发明。

在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现几率的方法得到的，出现几率高的字母使用较短的编码，反之出现几率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。

例如，在英文中，e的出现几率最高，而z的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时，e极有可能用一个比特来表示，而z则可能花去25个比特（不是26）。用普通的表示方法时，每个英文字母均占用一个字节，即8个比特。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。

霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln），N个权值Wi（i=1,2,...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,...n）。可以证明霍夫曼树的WPL是最小的。

1951年，霍夫曼在麻省理工学院（MIT）攻读博士学位，他和修读信息论课程的同学得选择是完成学期报告还是期末考试。导师罗伯特·法诺（Robert Fano）出的学期报告题目是：查找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，霍夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。霍夫曼使用自底向上的方法构建二叉树，避免了次优算法香农-范诺编码（Shannon–Fano coding）的最大弊端──自顶向下构建树。

1952年，于论文《一种构建极小多余编码的方法》（）中发表了这个编码方法。

霍夫曼树常处理符号编写工作。根据整组数据中符号出现的频率高低，决定如何给符号编码。如果符号出现的频率越高，则给符号的码越短，相反符号的号码越长。假设我们要给一个英文单字"F O R G E T"进行霍夫曼编码，而每个英文字母出现的频率分别列在。

（一）进行霍夫曼编码前，我们先创建一个霍夫曼树。

最后产生的树状图就是霍夫曼树，参考。
（二）进行编码

实现霍夫曼编码的方式主要是创建一个二叉树和其节点。这些树的节点可以存储在数组里，数组的大小为符号（symbols）数的大小n，而节点分别是终端节点（叶节点）与非终端节点（内部节点）。

一开始，所有的节点都是终端节点，节点内有三个字段：

1.符号（Symbol）

2.权重（Weight、Probabilities、Frequency）

3.指向父节点的链接（Link to its parent node）

而非终端节点内有四个字段：

1.权重（Weight、Probabilities、Frequency）

2.指向两个子节点的链接（Links to two child node）

3.指向父节点的链接（Link to its parent node）

基本上，我们用'0'与'1'分别代表指向左子节点与右子节点，最后为完成的二叉树共有n个终端节点与n-1个非终端节点，去除了不必要的符号并产生最佳的编码长度。

过程中，每个终端节点都包含着一个权重（Weight、Probabilities、Frequency），两两终端节点结合会产生一个新节点，新节点的权重是由两个权重最小的终端节点权重之总和，并持续进行此过程直到只剩下一个节点为止。

实现霍夫曼树的方式有很多种，可以使用优先队列（Priority Queue）简单达成这个过程，给与权重较低的符号较高的优先级（Priority），算法如下：

⒈把n个终端节点加入优先队列，则n个节点都有一个优先权Pi，1 ≤ i ≤ n

⒉如果队列内的节点数>1，则：

⒊最后在优先队列里的点为树的根节点（root）

而此算法的时间复杂度（ Time Complexity）为O（ log ）；因为有n个终端节点，所以树总共有2n-1个节点，使用优先队列每个循环须O（log ）。

此外，有一个更快的方式使时间复杂度降至线性时间（Linear Time）O（），就是使用两个队列（Queue）创件霍夫曼树。第一个队列用来存储n个符号（即n个终端节点）的权重，第二个队列用来存储两两权重的合（即非终端节点）。此法可保证第二个队列的前端（Front）权重永远都是最小值，且方法如下：

⒈把n个终端节点加入第一个队列（依照权重大小排列，最小在前端）

⒉如果队列内的节点数>1，则：

⒊最后在第一个队列的节点为根节点

虽然使用此方法比使用优先队列的时间复杂度还低，但是注意此法的第1项，节点必须依照权重大小加入队列中，如果节点加入顺序不按大小，则需要经过排序，则至少花了O（ log ）的时间复杂度计算。

但是在不同的状况考量下，时间复杂度并非是最重要的，如果我们今天考虑英文字母的出现频率，变量n就是英文字母的26个字母，则使用哪一种算法时间复杂度都不会影响很大，因为n不是一笔庞大的数字。

简单来说，霍夫曼码树的解压缩就是将得到的前置码（Prefix Huffman code）转换回符号，通常借由树的追踪（Traversal），将接收到的位串（Bits stream）一步一步还原。但是要追踪树之前，必须要先重建霍夫曼树；某些情况下，如果每个符号的权重可以被事先预测，那么霍夫曼树就可以预先重建，并且存储并重复使用，否则，发送端必须预先发送霍夫曼树的相关信息给接收端。

最简单的方式，就是预先统计各符号的权重并加入至压缩之位串，但是此法的运算量花费相当大，并不适合实际的应用。若是使用Canonical encoding，则可精准得知树重建的数据量只占2^比特（其中B为每个符号的比特数（bits））。如果简单将接收到的位串一个比特一个比特的重建，例如：'0'表示父节点，'1'表示终端节点，若每次读取到1时，下8个比特则会被解读是终端节点（假设数据为8-bit字母），则霍夫曼树则可被重建，以此方法，数据量的大小可能为2~320字节不等。虽然还有很多方法可以重建霍夫曼树，但因为压缩的数据串包含"trailing bits"，所以还原时一定要考虑何时停止，不要还原到错误的值，如在数据压缩时时加上每笔数据的长度等。

考量到不同的应用领域以及该领域的平均性质，将会使用不同的通用几率，又或者，这个几率是可以从被压缩文本中的实际频率所获取。

原始的霍夫曼算法是一个符号与符号间已知输入几率分布的最佳编码方式，也就是说将不相关的符号个别编码为如此的数据流。然而，当符号间的限制被舍弃或是质量几率函数是未知的时候，如此方式则并非最优化。此外，当这些符号之间不是互相独立，且分布不相同的时候，单一一个符号可能不足以实现最优化。在这种情况之下，算术编码可能比起霍夫曼编码会有更佳的压缩能力。

虽然上述两种方法都可以组合任意数量的符号以实现更高效的编码效果，并且通常适应于实际的输入统计层面，但尽管最简单的版本比霍夫曼编码更慢且更复杂，算术编码不会显著增加其计算或算法复杂度。当输入概率不是精确已知或在流内显著变化时，这种灵活性特别有用。然而，霍夫曼编码通常更快，并且算术编码在历史上是专利问题的一些主题。因此，许多技术历来避免使用有利于霍夫曼和其他前缀编码技术的算术编码。截至2010年中期，随着早期专利的到期，这种替代霍夫曼编码的最常用技术已经进入公有领域。

对于具有均匀概率分布的一组符号，以及作为2的幂之成员，霍夫曼编码等同于简单的二进位制编码，例如 ASCII 编码。这反映了如此的事实：无论压缩方法是什么，这种输入都不可能进行压缩，或只是说对数据无所作为，比起压缩才是才是最佳选择。

在任何情况下，霍夫曼编码在所有方法中是最佳的方式，其中每个输入符号是具有二元几率的已知独立且相同分布的随机变量。前缀码，特别是霍夫曼编码，往往在小字母表上产生较差的效率，其中概率通常落在这些最佳（二元）点之间。当最可能符号的概率远超过0.5时，可能发生霍夫曼编码的最坏情况，使低效率的上限无限制。

在使用霍夫曼编码的同时，有两种相关的方法可以解决这种特定的低效问题。将固定数量的符号组合在一起（阻塞）通常会增加（并且永不减少）压缩。随着块的大小接近无穷大，霍夫曼编码理论上接近熵限制，即最佳压缩。然而，阻塞任意大的符号组是不切实际的，因为霍夫曼代码的复杂性在要编码的可能性的数量上是线性的，这是在块的大小中呈指数的数字。这限制了在实践中完成的阻塞量。

广泛使用的实际替代方案是行程编码。该技术在熵编码之前增加一步，特别是对重复符号进行运行次数的计数，然后对其进行编码。对于伯努力（Bernoulli）过程的简单情况，哥伦（Golomb）编码在编码游程长度的前缀码中是最佳的，这是通过霍夫曼编码技术证明的事实。使用改进的霍夫曼编码的传真机采用类似的方法。但是，游程编码并不像其他压缩技术那样适应许多输入类型。

霍夫曼编码有派生出许多的许多变化，其中一些使用类似霍夫曼的算法，而其他一些算法找到最佳前缀码（例如，对输出施加不同的限制）。注意，在后一种情况下，该方法不需要像霍夫曼那样，实际上甚至不需要到多项式复杂度。

多元树霍夫曼编码算法使用字母集 {0, 1, ... , − 1} ，来构建一棵元树。霍夫曼在他的原始论文中考虑了这种方法。这与二进制（=2）算法仅有的差别，就是它每次把个最低权的符号合并，而不仅是两个最低权的符号。倘若 n ≥ 2, 则并非所有源字集都可以正确地形成用于霍夫曼编码的多元树。在这些情况下，必须添加额外的零概率占位符。这是因为该树必须为满的叉树，所以每次合并会令符号数恰好减少 ( -1), 故这样的叉树存在当且仅当源字的数量模 ( -1) 余 1. 对于二进制编码，任何大小的集合都可以形成这样的二叉树，因为 -1 = 1.

自适应霍夫曼编码的变化，涉及基于源符号序列中的最近实际频率动态地计算概率，以及改变编码树结构以匹配更新的概率估计。它在实践中很少使用，因为更新树的成本使其比优化的自适应算术编码慢，后者更灵活并且具有更好的压缩。

在霍夫曼编码的实现中，通常会使用权重表示数值概率，但是上面给出的算法不需要这样;它只需要权重形成一个完全有序的可交换幺半群，这意味着一种订购权重和添加权重的方法。霍夫曼模板算法使人们能够使用任何类型的权重（成本，频率，权重对，非数字权重）和许多组合方法之一（不仅仅是加法），这个问题首先应用于电路设计。

长度受限的霍夫曼编码是一种变体，其目标仍然是实现最小加权路径长度，但是存在另外的限制，即每个码字的长度必须小于给定常量。包合并算法通过一种与霍夫曼算法非常相似的简单贪婪方法解决了这个问题。

在标准的霍夫曼编码问题中，假设集合中构成码字的每个符号具有相同的传输成本：长度为位的码字总是具有的成本，无论多少这些数字是0，有多少是1，等等。在这个假设下工作时，最小化消息的总成本和最小化数字总数是相同的。

具有不等字母成本的霍夫曼编码是没有这种假设的概括：由于传输介质的特性，编码字母表的字母可能具有不均匀的长度。一个例子是摩尔斯电码的编码字母表，其中'破折号'比'点'需要更长的发送时间，因此传输时间中破折号的成本更高。目标仍然是最小化加权平均码字长度，但仅仅最小化消息使用的符号数量已经不够了。没有算法以与传统霍夫曼编码相同的方式或相同的效率来解决这个问题，尽管它已经由卡普（Karp）解决，其解决方案已经针对哥林（Golin）的整数成本的情况进行了改进。

在标准霍夫曼编码问题中，假设任何码字可以对应于任何输入符号。在字母表中，输入和输出的字母顺序必须相同。

如果对应于按字母顺序排列的输入的权重是按数字顺序排列的，则霍夫曼代码具有与最佳字母代码相同的长度，这可以从计算这些长度中找到，从而不需要使用胡 - 塔克（Hu-Tucker）编码。由数字（重新）有序输入产生的代码有时被称为规范霍夫曼代码，并且由于易于编码/解码，通常是实践中使用的代码。用于找到该代码的技术有时被称为霍夫曼 - 香农 - 法诺编码，因为它像霍夫曼编码一样是最优的，但是在重量概率上是字母的，例如香农 - 法诺编码。

设符号集合 $S=\left\{s_{1},s_{2},\cdots ,s_{n}\right\}$ $S = \left\{s_{1},s_{2},\cdots,s_{n}\right\}$ ， $P\left(s_{j}\right)$ $P\left(s_{j}\right)$ 为 $s_{j}$ $s_{j}$ 发生的几率， $L\left(s_{j}\right)$ $L\left(s_{j}\right)$ 为 $s_{j}$ $s_{j}$ 编码的长度

ex:
$P(S_{0})=1,entropy=0$ $P(S_{0})=1,entropy=0$
$P(S_{0})=P(S_{1})=0.5,entropy=0.6931$ $P(S_{0})=P(S_{1})=0.5,entropy=0.6931$
$P(S_{0})=P(S_{1})=P(S_{2})=P(S_{3})=P(S_{4})=0.2,entropy=1.6094$ $P(S_{0})=P(S_{1})=P(S_{2})=P(S_{3})=P(S_{4})=0.2,entropy=1.6094$
$P(S_{0})=P(S_{1})=P(S_{2})=P(S_{3})=0.1,P(S_{4})=0.6,entropy=1.2275$ $P(S_{0})=P(S_{1})=P(S_{2})=P(S_{3})=0.1,P(S_{4})=0.6,entropy=1.2275$
第三与第四个示例，同样是五种组合，几率分布越集中，则乱度越少

霍夫曼码的平均编码长度：设 $b=mean\left(L\right)N$ $b = mean \left(L \right) N$ ， $N {\displaystyle N}$ $N$ 为数据长度

(a)direct:
假设结果为：白色为00、咖啡色01，蓝色10和红色11个bits则结果为:100*2 = 200bits
(b)huffman code: (must be satisfy the following conditions，if not change the node)
(1) 所有码皆在Coding Tree的端点，再下去没有分枝(满足一致解码跟瞬间解码)
(2) 几率越大，code length越短；几率越小，code length越长
(3) 假设 $S_{a}$ $S_{a}$ 是第L层的node， $S_{b}$ $S_{b}$ 是第L+1层的node

   則 $P(S_{a})\geq P(S_{b})$  $P(S_{a})\geq P(S_{b})$ 必須滿足

假设结果为：白色占0、咖啡色10，蓝色110和红色111个bits
则结果为:60*1+20*2+20*3=160bits

相互比较两个结果huffman code 整整少了40bits的存储空间。

 1 // 以下為C++程式碼，在G++下編譯通過 2 // 僅用於示範如何根據權值建構霍夫曼樹， 3 // 沒有經過性能上的優化及加上完善的異常處理。 4 #include <cstdlib> 5 #include <iostream> 6 #include <deque> 7 #include <algorithm> 8  9 using namespace std;10 11 const int size = 10;12 struct node {                               // 霍夫曼樹節點結構13     unsigned key;                           // 保存權值14     node *lchild;                           // 左孩子指針15     node *rchild;                           // 右孩子指針16 };17 deque<node *> forest;18 deque<bool> code;                           // 此處也可使用bitset19 node *ptr;20 int frequency = {0};21 22 void printCode(deque<bool> ptr);            // 用於輸出霍夫曼編碼23 24 bool compare( node *a, node *b) {25     return a->key < b->key;26 }27 int main(int argc, char *argv) {28     for (int i = 0; i < size; i++) {29         cin >> frequency;                // 輸入10個權值30         ptr = new node;31         ptr->key = frequency;32         ptr->lchild = NULL;33         ptr->rchild = NULL;34         forest.push_back(ptr);35     } // 形成森林，森林中的每一棵樹都是一個節點36     // 從森林構建霍夫曼樹37     for (int i = 0; i < size - 1; i++) {38         sort(forest.begin(), forest.end(), compare);39         ptr = new node;40         // 以下代碼使用下標索引隊列元素，具有潛在危險，使用時請注意41         ptr->key = forest->key + forest->key;42         ptr->lchild = forest;43         ptr->rchild = forest;44         forest.pop_front();45         forest.pop_front();46         forest.push_back(ptr);47     }48     ptr = forest.front(); // ptr是一個指向根的指針49     system("PAUSE");50     return EXIT_SUCCESS;51 }52 53 void printCode(deque<bool> ptr) {54     // deque<bool>55     for (int i = 0; i < ptr.size(); i++) {56         if (ptr)57             cout << "1";58         else59             cout << "0";60     }61 }

哈夫曼编码c代码

huffman.h文件

 1 #ifndef __HUFFMAN_H__ 2 #define __HUFFMAN_H__ 3 #include<stdio.h> 4 #include<stdlib.h> 5 #include<string.h> 6  7 #define START printf("=====start=====\n") 8 #define END printf("=====end=====\n") 9 #define toByte(n) ((n) / 8 + ((n) % 8 > 0))10 11 typedef struct HuffListNode HuffListNode,*hufflistnodep;12 typedef struct HuffNode HuffNode,*huffnodep;13 typedef struct HuffTree HuffTree,*hufftreep;14 typedef struct HuffCode HuffCode,*huffcodep;15 typedef struct HuffList HuffList,*hufflistp;16 typedef struct HuffResult HuffResult,*huffresultp;17 typedef struct HuffCode HuffBuf,*huffbufp;  //缓存类型18 19 struct HuffListNode{20     huffnodep node;     //huffman节点21     hufflistnodep next; //后继节点22 };  //huffman频率节点23 24 struct HuffList{25     hufflistnodep head;         //头结点26     int keys;              //键值字典27     int size;                   //链表长度28 };29 30 struct HuffNode{31     int key;            //键32     int weight;         //权重33     huffnodep left;     //左节点34     huffnodep right;    //右节点35 };  //huffman节点36 37 struct HuffCode{38     char* code; //huffman code39     int size;   //huffman code size40 };41 42 struct HuffTree{43     huffnodep root;         //根44     huffcodep codes;   //key对应的代码45     int size;               //大小46 };  //huffman树47 48 struct HuffResult{49     char* code;      //生成的代码50     hufftreep tree;  //对应的哈夫曼树51 };52 53 #ifndef __BOOLEAN__54 #define __BOOLEAN__55 typedef enum{56     FALSE = 0,57     TRUE = 1,58 }Boolean;59 #endif60 61 huffnodep huffnode(int key,int weight); //初始化huffman节点62 hufflistp hufflist();   //初始化hufflist63 Boolean insertHuffNode(hufflistp list,huffnodep node);  //向指定的节点链表添加一个节点64 huffnodep shiftHuffNode(hufflistp list);    //删除第一个节点65 hufftreep hufftree(hufflistp list);   //构建一棵huffman tree66 huffbufp getFileBuf(const char* filename); //获取文件的buf67 hufftreep genhuffcodes(hufftreep tree,huffnodep node,char codes,int idx);  //获取当前节点之下的节点的huffman编码68 hufflistp getHuffListByFile(const char* filename); //根据文件创建huffman链表69 hufflistp getHuffListByBuf(huffbufp buf); //根据文件buf创建huffman链表70 huffcodep getHuffCode(hufftreep tree,int key);  //获取指定键值的huffcode71 huffresultp getHuffCodesByFile(const char* filename);     //获取文件的huffman code72 huffresultp getHuffCodesByBuf(huffbufp buf);    //通过buf获取codes73 huffbufp getOriginBuf(huffresultp result);       //从result中解析出原始的字符串74 huffbufp str2bin(char* str); //二进制字符串转二进制数组75 int putOriginToFile(huffresultp result,const char* filename);   //将result存储到filename中76 char* bin2str(huffbufp buf);    //二进制数组转二进制字符串77 huffbufp readHuffFile(const char* filename); //解析huff文件78 #endif

huffman.c文件:

  1 #include "huffman.h"  2   3 huffnodep huffnode(int key,int weight){  4     huffnodep ret = (huffnodep)malloc(sizeof(HuffNode));  5     ret->key = key;  6     ret->weight = weight;  7     ret->left = ret->right = NULL;  8   9     return ret; 10 } 11  12 hufflistp hufflist(){ 13     hufflistp ret = (hufflistp)malloc(sizeof(HuffList)); 14     ret->head = NULL; 15     memset(ret->keys,0,sizeof(ret->keys)*256); 16     ret->size = 0; 17  18     return ret; 19 } 20  21 Boolean insertHuffNode(hufflistp list,huffnodep node){ 22     if(list == NULL || node == NULL || node->weight <= -256) return FALSE; 23     hufflistnodep cur = list->head; 24     hufflistnodep* rootp = &(list->head); 25     hufflistnodep* last = NULL; //当前指针的前驱指针 26     hufflistnodep tmp = (hufflistnodep)malloc(sizeof(HuffListNode)); 27     tmp->node = node; 28     tmp->next = NULL; 29     if(node->key >= 0 && node->key < 256){ 30         list->keys = node->weight;   //添加key到keys字典 31     } 32     list->size++; 33  34     for(;cur != NULL  && cur->node->weight < node->weight; cur = cur->next){ 35         last = rootp; 36         rootp = &(cur->next); 37     } 38  39     tmp->next = cur; 40     if(last == NULL){   //第一个元素 41         list->head = tmp; 42     }else{  //向当前节点前面插入tmp节点 43         (*last)->next = tmp; 44     } 45  46     return TRUE; 47 } 48  49 huffnodep shiftHuffNode(hufflistp list){ 50     if(list == NULL || list->head == NULL) return NULL; 51     huffnodep ret = list->head->node; 52     hufflistnodep next = list->head->next; 53     free(list->head); 54     list->head = next; 55     list->size--; 56  57     return ret; 58 } 59  60 //通过huffman list构建 61 hufftreep hufftree(hufflistp list){ 62     hufftreep tree = (hufftreep)malloc(sizeof(HuffTree)); 63     tree->root = NULL; 64     tree->size = 0; 65     memset(tree->codes,0,sizeof(tree->codes)); 66  67     huffnodep a = NULL; 68     huffnodep b = NULL; 69     huffnodep c = NULL; 70     tree->size = 2 * list->size - 1; 71     while(list->size > 1){  //hufflistp长度大于1 72         a = shiftHuffNode(list); 73         b = shiftHuffNode(list); 74         c = huffnode(-256,a->weight+b->weight);    //新的节点 75         c->left = a; 76         c->right = b; 77         insertHuffNode(list,c); //将c压回list 78     } 79     tree->root = c; 80  81     //生成所有key的huffman编码 82     char codes;   //huffman编辑路径 83  84     return genhuffcodes(tree,tree->root,codes,0); 85 } 86  87 //获取文件内容的BUF 88 huffbufp getFileBuf(const char* filename){ 89     FILE* fp = fopen(filename,"r"); 90     if(fp == NULL) return NULL; 91     fseek(fp,0L,SEEK_END); 92     int len = ftell(fp); 93     rewind(fp); //重设 94     huffbufp ret = (huffbufp)malloc(sizeof(HuffBuf)); 95     ret->code = (char*)malloc(len+1); 96     ret->size = len; 97     fread(ret->code,1,len,fp); 98     fclose(fp); 99 100     return ret;101 }102 103 hufftreep genhuffcodes(hufftreep tree,huffnodep node,char codes,int idx){104     if(tree == NULL || node == NULL){   //到达底部105         return NULL;106     }107 108     if(node->left == NULL && node->right == NULL){  //叶子节点109         int key = node->key;110         huffcodep code = (huffcodep)malloc(sizeof(HuffCode));111         code->code = (char*)malloc(idx+1);112         code->size = idx;113         memcpy(code->code,codes,code->size);114         code->code = '\0';115         tree->codes = code;116     }{117         codes = '1'; //右118         genhuffcodes(tree,node->right,codes,idx+1);119         codes = '0'; //左120         genhuffcodes(tree,node->left,codes,idx+1);121     }122 123     return tree;124 }125 126 //通过文件生成huffman list127 hufflistp getHuffListByFile(const char* filename){128     huffbufp buf = getFileBuf(filename);129     if(buf == NULL) return NULL;130 131     hufflistp list = getHuffListByBuf(buf);132     free(buf->code);133     buf->code = NULL;134     free(buf);135     buf = NULL;136 137     return list;138 }139 140 hufflistp getHuffListByBuf(huffbufp buf){141     if(buf == NULL || buf->code == NULL) return NULL;142 143     char* code = buf->code;144 145     hufflistp list = hufflist();146     for(int i = 0; code != '\0'; i++){147         unsigned char ch = code;148         list->keys++;149     }150 151     for(int i = 0; i < 256; i++){152         if(list->keys > 0){   //插入存在的字符153             insertHuffNode(list,huffnode(i,list->keys));154         }155     }156 157     return list;158 }159 160 huffcodep getHuffCode(hufftreep tree,int key){161     if(key < 256 && key >= 0 && tree->codes > 0){162         return tree->codes;163     }164     return NULL;165 }166 167 huffresultp getHuffCodesByFile(const char* filename){168     huffbufp buf = getFileBuf(filename);   //文件缓存169     return getHuffCodesByBuf(buf);170 }171 172 huffresultp getHuffCodesByBuf(huffbufp buf){173     huffresultp result = (huffresultp)malloc(sizeof(HuffResult));174     result->code = NULL;175 176     if(buf == NULL) return NULL;177 178     hufflistp list = getHuffListByBuf(buf); //huffman list179 180     result->tree = hufftree(list);181     int buf_len = buf->size;182     int len = 0;183     for(int i = 0; buf->code != '\0'; i++){184         int key = (unsigned char)buf->code;185         huffcodep code = getHuffCode(result->tree,key);186         if(code == NULL){187             printf("LLL:%c{%d}\n",key,key);188             return NULL;189         }190         len+=code->size;191     }192     result->code = (char*)malloc(len+1);193     result->code = '\0';194     for(int i = 0; buf->code != '\0'; i++){195         unsigned char key = buf->code;196         huffcodep code = getHuffCode(result->tree,key);197         strncat(result->code,code->code,code->size);198     }199 200     return result;201 }202 203 huffbufp getOriginBuf(huffresultp result){204     if(result == NULL || result->code == NULL || result->tree == NULL) return NULL;205     hufftreep tree = result->tree;206     char* code = result->code;207     int len = 0;208     for(int i = 0; code != '\0';){209         huffnodep root = tree->root;    //根节点210         while(root->left != NULL && root->right != NULL && code != '\0'){   //双子节点存在211             root = (code == '0' ? root->left : root->right);212             i++;213         }214         if((root->left != NULL || root->right != NULL) && code == '\0'){ //错误215             return NULL;216         }217         len++;218         // printf("解析:%c{%s}\n",root->key,tree->codes->code);219     }220 221     huffbufp ret = (huffbufp)malloc(sizeof(HuffBuf));222     ret->code = (char*)malloc(len+1);223     ret->code = '\0';224     ret->size = len;225 226     int idx = 0;227     for(int i = 0; code != '\0';){228         huffnodep root = tree->root;    //根节点229         while(root->left != NULL && root->right != NULL && code != '\0'){   //双子节点存在230             root = (code == '0' ? root->left : root->right);231             i++;232         }233         ret->code = root->key;234     }235     ret->code = '\0';236 237     return ret;238 }239 240 int putOriginToFile(huffresultp result,const char* filename){241     if(result == NULL) return 0;242     // printf("res1:%s\n",(int)strlen(result->code),result->code);243     // huffbufp b = str2bin(result->code);244     // printf("%d\n",b->size);245     // printf("res2:%s\n",bin2str(b));246     // return 0;247 248     huffbufp buf = str2bin(result->code);   //huffman code转成buf249     int i = 0;250     int len = 0;    251     for(i = 0; i < 256; i++){252         if(result->tree->codes > 0){ //253             len+= 5+result->tree->codes->size;   //key:len:size254         }255     }256     huffbufp keys = (huffbufp)malloc(sizeof(HuffBuf));257     keys->code = (char*)malloc(len);258     keys->size = 0;259     //获取keys260     int idx = 0;261     for(i = 0; i < 256; i++){262         if(result->tree->codes > 0){ //263             keys->code = i;    //key264             int len = result->tree->codes->size;265             memcpy(keys->code+idx,&len,4);    //key size266             // printf("%c:%d{%s}\n",i,i,len,result->tree->codes->code);267             idx+=4;268             huffbufp tmp = str2bin(result->tree->codes->code);269             // printf("%d,%d\n",tmp->code,tmp->size);270             int tsize = toByte(tmp->size);271             memcpy(keys->code+idx,tmp->code,tsize);272             idx+=tsize;273         }274     }275 276     keys->size = idx;   //诸多键的总空间277     278     //写出标准文件279     //HUF\n280     //size: 4b281     //keys282     //size: 4b283     //codes284     FILE* fp = fopen(filename,"w");285     if(fp == NULL) return -1;286     fwrite("HUF\n",1,4,fp);287     fwrite(&idx,1,4,fp);    //size288     fwrite(keys->code,1,keys->size,fp); //写入code289     fwrite(&(buf->size),1,4,fp);    //size290     fwrite(buf->code,1,toByte(buf->size),fp);291     fclose(fp);292 293     return 4+4+keys->size+4+buf->size;294 }295 296 297 huffbufp str2bin(char* str){ //二进制字符串转二进制数组298     // printf("bin:%s\n",str);299     if(str == NULL) return NULL;300     huffbufp buf = (huffbufp)malloc(sizeof(HuffBuf));301     int l = strlen(str);302     int size = (l / 8) + (l % 8 > 0);303 304     buf->code = (char*)malloc(l);305     memset(buf->code,0,l);306     for(int i = 0; i < l; i++){307         int idx = i/8;308         int bi = i%8;309         buf->code |= (str == '0' ? 0:1) << bi;310     }311     buf->size = l;312 313     return buf;314 }315 316 char* bin2str(huffbufp buf){317     char* ret = (char*)malloc(buf->size+1);318     for(int i = 0; i < buf->size; i++){319         int idx = i / 8;320         int offset = i % 8;321         ret = (buf->code & (0x01 << offset)) ? '1' : '0';322     }323     ret = '\0';324 325     return ret;326 }327 328 huffbufp readHuffFile(const char* filename){329     huffbufp buf = getFileBuf(filename);330     if(buf == NULL) return NULL;331 332     if(memcmp(buf->code,"HUF\n",4) != 0) return NULL;   //文件不以BUF\n开头333     huffresultp result = (huffresultp)malloc(sizeof(HuffResult));334     //BUF\n335     //key size336     int key_size = *(int*)(buf->code+4);337     int base = 8; //偏移量338     hufftreep tree = (hufftreep)malloc(sizeof(HuffTree));339     tree->root = NULL;340     tree->size = 0;341     huffcodep* codes = tree->codes;   //key对应代码342     memset(codes,0,sizeof(huffcodep)*256);343     344     int oft = 0;345     for(;oft < key_size;){346         int offset = base+oft;347         unsigned char key = buf->code;348         // printf("%d\n",key,key);349         int size = *(int*)(buf->code+offset+1); //长度350         int byte = toByte(size);351         huffbufp htmp = (huffbufp)malloc(sizeof(HuffBuf));352         //键对应代码353         htmp->code = buf->code+offset+5;    //缓存代码354         htmp->size = size;  //缓存大小355         // printf("%d\n",key,key);356         huffcodep tmp = (huffcodep)malloc(sizeof(HuffCode));357         tmp->size = size;   //key的大小358         tmp->code = bin2str(htmp);359         tree->codes = tmp;360         tree->size++;   //树的大小增加361         huffnodep root = tree->root;362         if(root == NULL){363             tree->root = huffnode(-256,0);364             root = tree->root;365         }366         for(int i = 0; i < tmp->size; i++){367             char ch = tmp->code;368             huffnodep node = NULL;369             if(ch == '0'){370                 node = root->left;371                 if(node == NULL){372                     node = huffnode(-256,0);373                 }374                 root->left = node;375             }else{376                 node = root->right;377                 if(node == NULL){378                     node = huffnode(-256,0);379                 }380                 root->right = node;381             }382             if(i == tmp->size - 1)383                 node->key = key;384             root = node;385         }386         oft+=5+byte;387     }388 389     huffbufp tmp = (huffbufp)malloc(sizeof(HuffBuf));390     tmp->code = buf->code+base+oft+4;391     tmp->size = *(int*)(buf->code+base+oft);392     // printf("tmp size:%d\n",tmp->size);393     result->tree = tree;394     result->code = bin2str(tmp);395     // printf("%s\n",result->code);396 397     // for(int i = 0; i < 256; i++){398     //     if(codes!=NULL){399     //         printf("%c:%s\n",i,i,codes->code);400     //     }401     // }402 403     return getOriginBuf(result);404 }