霍夫曼编码 -{H|zh-hans:重定向;zh-hant:重新导向;}--{H|zh-cn:字符;zh-tw:字元;}--{H|zh-hans:文件; zh-hant:档案;}--{H|zh-hans:快捷方式; zh-hant:捷径;}--{H|zh-hans:项目;zh-hant:专案;zh-tw:计划;zh-hk:计划;zh-mo:计划;}--{H|zh-cn:计算机; zh-sg:电脑; zh-tw:电脑;}- 霍夫曼编码（），又译为哈夫曼编码、赫夫曼编码，是一种用于无损数据压缩的熵编码（权编码）演算法。由美国计算机科学家大卫·霍夫曼于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年，霍夫曼在麻省理工学院攻读博士学位，他和修读信息论课程的同学得选择是完成学期报告还是期末考试。导师罗伯特·法诺出的学期报告题目是：寻找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，霍夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。霍夫曼使用自底向上的方法构建二叉树，避免了次优算法香农-范诺编码的最大弊端──自顶向下构建树。 1952年，于论文《一种构建极小多余编码的方法》（-- ）中发表了这个编码方法。 一组符号（Symbol）和其对应的权重值（weight），其权重通常表示成-{zh-cn:概率;zh-tw:机率;}-（%）。 一组二元的前置码，其二元码的长度为最短。 符号集合formula_1，其S集合的大小为formula_2。 权重集合formula_3，其W集合不为负数且formula_4。 一组编码formula_5，其C集合是一组二进制编码且formula_6为formula_7相对应的编码，formula_8。 设formula_9为formula_10的加权的路径长，对所有编码formula_11，则formula_12 问题定义与解法. 范例. 霍夫曼树常处理符号编写工作。根据整组资料中符号出现的频率高低，决定如何给符号编码。如果符号出现的频率越高，则给符号的码越短，相反符号的号码越长。假设我们要给一个英文单字"F O R G E T"进行霍夫曼编码，而每个英文字母出现的频率分别列在"Fig.1"。 演算过程. （一）进行霍夫曼编码前，我们先建立一个霍夫曼树。 ⒈将每个英文字母依照出现频率由小排到大，最小在左，如"Fig.1"。 ⒉每个字母都代表一个终端节点（叶节点），比较F.O.R.G.E.T六个字母中每个字母的出现频率，将最小的两个字母频率相加合成一个新的节点。如"Fig.2"所示，发现F与O的频率最小，故相加2+3=5。 ⒊比较5.R.G.E.T，发现R与G的频率最小，故相加4+4=8。 ⒋比较5.8.E.T，发现5与E的频率最小，故相加5+5=10。 ⒌比较8.10.T，发现8与T的频率最小，故相加8+7=15。 ⒍最后剩10.15，没有可以比较的对象，相加10+15=25。 最后产生的树状图就是霍夫曼树，参考"Fig.2"。 （二）进行编码 1.给霍夫曼树的所有左链结'0'与右链结'1'。 2.从树根至树叶依序记录所有字母的编码，如"Fig.3"。 实现方法. 资料压缩. 实现霍夫曼编码的方式主要是创建一个二元树和其节点。这些树的节点可以储存在阵列里，阵列的大小为符号（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，则： ⑴从伫列中移除两个最小的Pi节点，即连续做两次remove（min（Pi）, Priority_Queue) ⑵产生一个新节点，此节点为（1）之移除节点之父节点，而此节点的权重值为（1）两节点之权重和 ⑶把（2）产生之节点加入优先伫列中 ⒊最后在优先伫列里的点为树的根节点（root） 而此演算法的时间复杂度（Time Complexity）为O("n" log "n")；因为有n个终端节点，所以树总共有2n-1个节点，使用优先伫列每个回圈须O(log "n")。 此外，有一个更快的方式使时间复杂度降至线性时间（Linear Time）O("n")，就是使用两个伫列（Queue）创件霍夫曼树。第一个伫列用来储存n个符号（即n个终端节点）的权重，第二个伫列用来储存两两权重的合（即非终端节点）。此法可保证最小值永远都是两个伫列的前端（Front）权重之一，且方法如下： ⒈把n个终端节点加入第一个伫列（依照权重大小排列，最小在前端） ⒉如果伫列内的节点数>1，则： ⑴从伫列前端移除两个最低权重的节点 ⑵将（1）中移除的两个节点权重相加合成一个新节点 ⑶加入第二个伫列 ⒊最后在第一个伫列的节点为根节点 虽然使用此方法比使用优先伫列的时间复杂度还低，但是注意此法的第1项，节点必须依照权重大小加入伫列中，如果节点加入顺序不按大小，则需要经过排序，则至少花了O("n" log "n")的时间复杂度计算。 但是在不同的状况考量下，时间复杂度并非是最重要的，如果我们今天考虑英文字母的出现频率，变数n就是英文字母的26个字母，则使用哪一种演算法时间复杂度都不会影响很大，因为n不是一笔庞大的数字。 资料解压缩. 简单来说，霍夫曼码树的解压缩就是将得到的前置码（Prefix Huffman code）转换回符号，通常借由树的追踪（Traversal），将接收到的位元串（Bits stream）一步一步还原。但是要追踪树之前，必须要先重建霍夫曼树；某些情况下，如果每个符号的权重可以被事先预测，那么霍夫曼树就可以预先重建，并且储存并重复使用，否则，传送端必须预先传送霍夫曼树的相关资讯给接收端。 最简单的方式，就是预先统计各符号的权重并加入至压缩之位元串，但是此法的运算量花费相当大，并不适合实际的应用。若是使用Canonical encoding，则可精准得知树重建的资料量只占"B·"2^"B"位元（其中B为每个符号的位元数（bits））。如果简单将接收到的位元串一个位元一个位元的重建，例如：'0'表示父节点，'1'表示终端节点，若每次读取到1时，下8个位元则会被解读是终端节点（假设资料为8-bit字母），则霍夫曼树则可被重建，以此方法，资料量的大小可能为2~320位元组不等。虽然还有很多方法可以重建霍夫曼树，但因为压缩的资料串包含"trailing bits"，所以还原时一定要考虑何时停止，不要还原到错误的值，如在资料压缩时时加上每笔资料的长度等。 基本性质. 考量到不同的应用领域以及该领域的平均性质，将会使用不同的通用机率，又或者，这个机率是可以从被压缩文本中的实际频率所取得。 最佳化. 原始的霍夫曼演算法是一个符号与符号间已知输入机率分布的最佳编码方式，也就是说将不相关的符号个别编码为如此的资料串流。然而，当符号间的限制被舍弃或是质量机率函数是未知的时候，如此方式则并非最佳化。此外，当这些符号之间不是互相独立，且分布不相同的时候，单一一个符号可能不足以实现最佳化。在这种情况之下，算术编码可能比起霍夫曼编码会有更佳的压缩能力。 虽然上述两种方法都可以组合任意数量的符号以实现更高效的编码效果，并且通常适应于实际的输入统计层面，但尽管最简单的版本比霍夫曼编码更慢且更复杂，算术编码不会显著增加其计算或算法复杂度。当输入概率不是精确已知或在流内显著变化时，这种灵活性特别有用。然而，霍夫曼编码通常更快，并且算术编码在历史上是专利问题的一些主题。因此，许多技术历来避免使用有利于霍夫曼和其他前缀编码技术的算术编码。截至2010年中期，随著早期专利的到期，这种替代霍夫曼编码的最常用技术已经进入公有领域。 对于具有均匀概率分布的一组符号，以及作为2的幂之成员，霍夫曼编码等同于简单的二进位制编码，例如 ASCII 编码。这反映了如此的事实：无论压缩方法是什么，这种输入都不可能进行压缩，或只是说对数据无所作为，比起压缩才是最佳选择。 在任何情况下，霍夫曼编码在所有方法中是最佳的方式，其中每个输入符号是具有二元机率的已知独立且相同分布的随机变量。前缀码，特别是霍夫曼编码，往往在小字母表上产生较差的效率，其中概率通常落在这些最佳（二元）点之间。当最可能符号的概率远超过0.5时，可能发生霍夫曼编码的最坏情况，使低效率的上限无限制。 在使用霍夫曼编码的同时，有两种相关的方法可以解决这种特定的低效问题。将固定数量的符号组合在一起（阻塞）通常会增加（并且永不减少）压缩。随著块的大小接近无穷大，霍夫曼编码理论上接近熵限制，即最佳压缩。然而，阻塞任意大的符号组是不切实际的，因为霍夫曼代码的复杂性在要编码的可能性的数量上是线性的，这是在块的大小中呈指数的数字。这限制了在实践中完成的阻塞量。 广泛使用的实际替代方案是行程编码。该技术在熵编码之前增加一步，特别是对重复符号进行执行次数的计数，然后对其进行编码。对于伯努力（Bernoulli）过程的简单情况，哥伦（Golomb）编码在编码游程长度的前缀码中是最佳的，这是通过霍夫曼编码技术证明的事实。使用改进的霍夫曼编码的传真机采用类似的方法。但是，游程编码并不像其他压缩技术那样适应许多输入类型。 变化. 霍夫曼编码有衍生出许多的许多变化，其中一些使用类似霍夫曼的算法，而其他一些算法找到最佳前缀码（例如，对输出施加不同的限制）。注意，在后一种情况下，该方法不需要像霍夫曼那样，实际上甚至不需要到多项式复杂度。 多元树霍夫曼编码. 多元树霍夫曼编码演算法使用字母集 {0, 1, ... , "n" − 1} ，来构建一棵 "n" 元树。霍夫曼在他的原始论文中考虑了这种方法。这与二进制（"n"=2）算法仅有的差别，就是它每次把 "n" 个最低权的符号合并，而不仅是两个最低权的符号。倘若 n ≥ 2, 则并非所有源字集都可以正确地形成用于霍夫曼编码的多元树。在这些情况下，必须添加额外的零概率占位符。这是因为该树必须为满的 "n" 叉树，所以每次合并会令符号数恰好减少 ("n" -1), 故这样的 "n" 叉树存在当且仅当源字的数量模 ("n" -1) 余 1. 对于二进制编码，任何大小的集合都可以形成这样的二叉树，因为 "n" -1 = 1. 自适应霍夫曼编码. 自适应霍夫曼编码的变化，涉及基于源符号序列中的最近实际频率动态地计算概率，以及改变编码树结构以匹配更新的概率估计。它在实践中很少使用，因为更新树的成本使其比优化的自适应算术编码慢，后者更灵活并且具有更好的压缩。 霍夫曼模板演算法. 在霍夫曼编码的实现中，通常会使用权重表示数值概率，但是上面给出的算法不需要这样;它只需要权重形成一个完全有序的可交换么半群，这意味著一种订购权重和添加权重的方法。霍夫曼模板算法使人们能够使用任何类型的权重（成本，频率，权重对，非数字权重）和许多组合方法之一（不仅仅是加法），这个问题首先应用于电路设计。 长度限制霍夫曼编码/最小变异霍夫曼编码. 长度限制霍夫曼编码. 长度受限的霍夫曼编码是一种变体，其目标仍然是实现最小加权路径长度，但是存在另外的限制，即每个码字的长度必须小于给定常数。包合并算法通过一种与霍夫曼演算法非常相似的简单贪婪方法解决了这个问题。 不相等成本霍夫曼编码. 在标准的霍夫曼编码问题中，假设集合中构成码字的每个符号具有相同的传输成本：长度为"N"位的码字总是具有"N"的成本，无论多少这些数字是0，有多少是1，等等。在这个假设下工作时，最小化消息的总成本和最小化数字总数是相同的。 具有不等字母成本的霍夫曼编码是没有这种假设的概括：由于传输介质的特性，编码字母表的字母可能具有不均匀的长度。一个例子是摩尔斯电码的编码字母表，其中'破折号'比'点'需要更长的发送时间，因此传输时间中破折号的成本更高。目标仍然是最小化加权平均码字长度，但仅仅最小化消息使用的符号数量已经不够了。没有算法以与传统霍夫曼编码相同的方式或相同的效率来解决这个问题，尽管它已经由卡普（Karp）解决，其解决方案已经针对哥林（Golin）的整数成本的情况进行了改进。 最佳字母二元树. 在标准霍夫曼编码问题中，假设任何码字可以对应于任何输入符号。在字母表中，输入和输出的字母顺序必须相同。 规范霍夫曼编码. 如果对应于按字母顺序排列的输入的权重是按数字顺序排列的，则霍夫曼代码具有与最佳字母代码相同的长度，这可以从计算这些长度中找到，从而不需要使用胡 - 塔克（Hu-Tucker）编码。由数字（重新）有序输入产生的代码有时被称为规范霍夫曼代码，并且由于易于编码/解码，通常是实践中使用的代码。用于找到该代码的技术有时被称为霍夫曼 - 香农 - 法诺编码，因为它像霍夫曼编码一样是最优的，但是在重量概率上是字母的，例如香农 - 法诺编码。 资料长度. 设符号集合formula_1，formula_14为formula_15发生的机率 ，formula_16为formula_17编码的长度 formula_18 ex: formula_19 formula_20 formula_21 formula_22 第三与第四个范例，同样是五种组合，机率分布越集中，则乱度越少 formula_23 Shannon编码定理： formula_24 ≤ formula_25 ≤ formula_24 formula_27 ，若使用formula_28进位的编码 霍夫曼码的平均编码长度：设formula_29，formula_30为资料长度 formula_30formula_32 ≤ formula_33 ≤ formula_30formula_32 formula_36 范例. (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) 假设formula_37是第L层的node，formula_38是第L+1层的node 则formula_39必须满足 假设结果为：白色占0、咖啡色10，蓝色110和红色111个bits 则结果为:60*1+20*2+20*3=160bits 相互比较两个结果huffman code 整整少了40bits的储存空间。 示范程式. // 以下为C++程式码，在G++下编译通过 // 仅用于示范如何根据权值建构霍夫曼树， // 没有经过性能上的优化及加上完善的异常处理。 using namespace std; const int size = 10; struct node { // 霍夫曼树节点结构 unsigned key; // 保存权值 node *lchild; // 左孩子指针 node *rchild; // 右孩子指针 deque forest; deque code; // 此处也可使用bitset node *ptr; int frequency[size] = {0}; void printCode(deque ptr); // 用于输出霍夫曼编码 bool compare( node *a, node *b) { return a->key key; int main(int argc, char *argv[]) { for (int i = 0; i key = frequency[i]; ptr->lchild = NULL; ptr->rchild = NULL; forest.push_back(ptr); } // 形成森林，森林中的每一棵树都是一个节点 // 从森林构建霍夫曼树 for (int i = 0; i key = forest[0]->key + forest[1]->key; ptr->lchild = forest[0]; ptr->rchild = forest[1]; forest.pop_front(); forest.pop_front(); forest.push_back(ptr); ptr = forest.front(); // ptr是一个指向根的指针 system("PAUSE"); return EXIT_SUCCESS; void printCode(deque ptr) { // deque for (int i = 0; i key = key; ret->weight = weight; ret->left = ret->right = NULL; return ret; hufflistp hufflist(){ hufflistp ret = (hufflistp)malloc(sizeof(HuffList)); ret->head = NULL; memset(ret->keys,0,sizeof(ret->keys[0])*256); ret->size = 0; return ret; Boolean insertHuffNode(hufflistp list,huffnodep node){ if(list == NULL || node == NULL || node->weight head; hufflistnodep* rootp = &(list->head); hufflistnodep* last = NULL; //当前指针的前驱指针 hufflistnodep tmp = (hufflistnodep)malloc(sizeof(HuffListNode)); tmp->node = node; tmp->next = NULL; if(node->key >= 0 && node->key keys[node->key] = node->weight; //添加key到keys字典 list->size++; for(;cur != NULL && cur->node->weight weight; cur = cur->next){ last = rootp; rootp = &(cur->next); tmp->next = cur; if(last == NULL){ //第一个元素 list->head = tmp; }else{ //向当前节点前面插入tmp节点 (*last)->next = tmp; return TRUE; huffnodep shiftHuffNode(hufflistp list){ if(list == NULL || list->head == NULL) return NULL; huffnodep ret = list->head->node; hufflistnodep next = list->head->next; free(list->head); list->head = next; list->size--; return ret; //通过huffman list构建 hufftreep hufftree(hufflistp list){ hufftreep tree = (hufftreep)malloc(sizeof(HuffTree)); tree->root = NULL; tree->size = 0; memset(tree->codes,0,sizeof(tree->codes)); huffnodep a = NULL; huffnodep b = NULL; huffnodep c = NULL; tree->size = 2 * list->size - 1; while(list->size > 1){ //hufflistp长度大于1 a = shiftHuffNode(list); b = shiftHuffNode(list); c = huffnode(-256,a->weight+b->weight); //新的节点 c->left = a; c->right = b; insertHuffNode(list,c); //将c压回list tree->root = c; //生成所有key的huffman编码 char codes[8092]; //huffman编辑路径 return genhuffcodes(tree,tree->root,codes,0); //获取文件内容的BUF huffbufp getFileBuf(const char* filename){ FILE* fp = fopen(filename,"r"); if(fp == NULL) return NULL; fseek(fp,0L,SEEK_END); int len = ftell(fp); rewind(fp); //重设 huffbufp ret = (huffbufp)malloc(sizeof(HuffBuf)); ret->code = (char*)malloc(len+1); ret->size = len; fread(ret->code,1,len,fp); fclose(fp); return ret; hufftreep genhuffcodes(hufftreep tree,huffnodep node,char codes[],int idx){ if(tree == NULL || node == NULL){ //到达底部 return NULL; if(node->left == NULL && node->right == NULL){ //叶子节点 int key = node->key; huffcodep code = (huffcodep)malloc(sizeof(HuffCode)); code->code = (char*)malloc(idx+1); code->size = idx; memcpy(code->code,codes,code->size); code->code[code->size] = '\0'; tree->codes[key] = code; codes[idx] = '1'; //右 genhuffcodes(tree,node->right,codes,idx+1); codes[idx] = '0'; //左 genhuffcodes(tree,node->left,codes,idx+1); return tree; //通过文件生成huffman list hufflistp getHuffListByFile(const char* filename){ huffbufp buf = getFileBuf(filename); if(buf == NULL) return NULL; hufflistp list = getHuffListByBuf(buf); free(buf->code); buf->code = NULL; free(buf); buf = NULL; return list; hufflistp getHuffListByBuf(huffbufp buf){ if(buf == NULL || buf->code == NULL) return NULL; char* code = buf->code; hufflistp list = hufflist(); for(int i = 0; code[i] != '\0'; i++){ unsigned char ch = code[i]; list->keys[ch]++; for(int i = 0; i keys[i] > 0){ //插入存在的字符 insertHuffNode(list,huffnode(i,list->keys[i])); return list; huffcodep getHuffCode(hufftreep tree,int key){ if(key = 0 && tree->codes[key] > 0){ return tree->codes[key]; return NULL; huffresultp getHuffCodesByFile(const char* filename){ huffbufp buf = getFileBuf(filename); //文件缓存 return getHuffCodesByBuf(buf); huffresultp getHuffCodesByBuf(huffbufp buf){ huffresultp result = (huffresultp)malloc(sizeof(HuffResult)); result->code = NULL; if(buf == NULL) return NULL; hufflistp list = getHuffListByBuf(buf); //huffman list result->tree = hufftree(list); int buf_len = buf->size; int len = 0; for(int i = 0; buf->code[i] != '\0'; i++){ int key = (unsigned char)buf->code[i]; huffcodep code = getHuffCode(result->tree,key); if(code == NULL){ printf("LLL:%c{%d}\n",key,key); return NULL; len+=code->size; result->code = (char*)malloc(len+1); result->code[0] = '\0'; for(int i = 0; buf->code[i] != '\0'; i++){ unsigned char key = buf->code[i]; huffcodep code = getHuffCode(result->tree,key); strncat(result->code,code->code,code->size); return result; huffbufp getOriginBuf(huffresultp result){ if(result == NULL || result->code == NULL || result->tree == NULL) return NULL; hufftreep tree = result->tree; char* code = result->code; int len = 0; for(int i = 0; code[i] != '\0';){ huffnodep root = tree->root; //根节点 while(root->left != NULL && root->right != NULL && code[i] != '\0'){ //双子节点存在 root = (code[i] == '0' ? root->left : root->right); i++; if((root->left != NULL || root->right != NULL) && code[i] == '\0'){ //错误 return NULL; len++; // printf("解析:%c{%s}\n",root->key,tree->codes[root->key]->code); huffbufp ret = (huffbufp)malloc(sizeof(HuffBuf)); ret->code = (char*)malloc(len+1); ret->code[0] = '\0'; ret->size = len; int idx = 0; for(int i = 0; code[i] != '\0';){ huffnodep root = tree->root; //根节点 while(root->left != NULL && root->right != NULL && code[i] != '\0'){ //双子节点存在 root = (code[i] == '0' ? root->left : root->right); i++; ret->code[idx++] = root->key; ret->code[idx] = '\0'; return ret; int putOriginToFile(huffresultp result,const char* filename){ if(result == NULL) return 0; // printf("res1[%d]:%s\n",(int)strlen(result->code),result->code); // huffbufp b = str2bin(result->code); // printf("%d\n",b->size); // printf("res2:%s\n",bin2str(b)); // return 0; huffbufp buf = str2bin(result->code); //huffman code转成buf int i = 0; int len = 0; for(i = 0; i tree->codes[i] > 0){ // len+= 5+result->tree->codes[i]->size; //key[1]:len[4]:size huffbufp keys = (huffbufp)malloc(sizeof(HuffBuf)); keys->code = (char*)malloc(len); keys->size = 0; //获取keys int idx = 0; for(i = 0; i tree->codes[i] > 0){ // keys->code[idx++] = i; //key int len = result->tree->codes[i]->size; memcpy(keys->code+idx,&len,4); //key size // printf("%c[%d]:%d{%s}\n",i,i,len,result->tree->codes[i]->code); idx+=4; huffbufp tmp = str2bin(result->tree->codes[i]->code); // printf("%d,%d\n",tmp->code[0],tmp->size); int tsize = toByte(tmp->size); memcpy(keys->code+idx,tmp->code,tsize); idx+=tsize; keys->size = idx; //诸多键的总空间 //写出标准文件 //HUF\n //size: 4b //keys //size: 4b //codes FILE* fp = fopen(filename,"w"); if(fp == NULL) return -1; fwrite("HUF\n",1,4,fp); fwrite(&idx,1,4,fp); //size fwrite(keys->code,1,keys->size,fp); //写入code fwrite(&(buf->size),1,4,fp); //size fwrite(buf->code,1,toByte(buf->size),fp); fclose(fp); return 4+4+keys->size+4+buf->size; huffbufp str2bin(char* str){ //二进制字符串转二进制数组 // printf("bin:%s\n",str); if(str == NULL) return NULL; huffbufp buf = (huffbufp)malloc(sizeof(HuffBuf)); int l = strlen(str); int size = (l / 8) + (l % 8 > 0); buf->code = (char*)malloc(l); memset(buf->code,0,l); for(int i = 0; i code[idx] |= (str[i] == '0' ? 0:1) « bi; buf->size = l; return buf; char* bin2str(huffbufp buf){ char* ret = (char*)malloc(buf->size+1); for(int i = 0; i size; i++){ int idx = i / 8; int offset = i % 8; ret[i] = (buf->code[idx] & (0x01 « offset)) ? '1' : '0'; ret[buf->size] = '\0'; return ret; huffbufp readHuffFile(const char* filename){ huffbufp buf = getFileBuf(filename); if(buf == NULL) return NULL; if(memcmp(buf->code,"HUF\n",4) != 0) return NULL; //文件不以BUF\n开头 huffresultp result = (huffresultp)malloc(sizeof(HuffResult)); //BUF\n //key size int key_size = *(int*)(buf->code+4); int base = 8; //偏移量 hufftreep tree = (hufftreep)malloc(sizeof(HuffTree)); tree->root = NULL; tree->size = 0; huffcodep* codes = tree->codes; //key对应代码 memset(codes,0,sizeof(huffcodep)*256); int oft = 0; for(;oft code[offset]; // printf("%d[%c]\n",key,key); int size = *(int*)(buf->code+offset+1); //长度 int byte = toByte(size); huffbufp htmp = (huffbufp)malloc(sizeof(HuffBuf)); //键对应代码 htmp->code = buf->code+offset+5; //缓存代码 htmp->size = size; //缓存大小 // printf("[%c]%d\n",key,key); huffcodep tmp = (huffcodep)malloc(sizeof(HuffCode)); tmp->size = size; //key的大小 tmp->code = bin2str(htmp); tree->codes[key] = tmp; tree->size++; //树的大小增加 huffnodep root = tree->root; if(root == NULL){ tree->root = huffnode(-256,0); root = tree->root; for(int i = 0; i size; i++){ char ch = tmp->code[i]; huffnodep node = NULL; if(ch == '0'){ node = root->left; if(node == NULL){ node = huffnode(-256,0); root->left = node; }else{ node = root->right; if(node == NULL){ node = huffnode(-256,0); root->right = node; if(i == tmp->size - 1) node->key = key; root = node; oft+=5+byte; huffbufp tmp = (huffbufp)malloc(sizeof(HuffBuf)); tmp->code = buf->code+base+oft+4; tmp->size = *(int*)(buf->code+base+oft); // printf("tmp size:%d\n",tmp->size); result->tree = tree; result->code = bin2str(tmp); // printf("%s\n",result->code); // for(int i = 0; i code); return getOriginBuf(result); 程序演示主文件: int main(){ huffbufp buf = (huffbufp)malloc(sizeof(HuffBuf)); buf->code = "this is just a test!"; buf->size = strlen(buf->code); huffresultp result = getHuffCodesByBuf(buf); //获取编码结果 printf("huffman: %s\n",result->code); huffbufp origin = getOriginBuf(result); //通过编码获取原始数据 printf("origin: %s\n",origin->code); return 0; 参考文献.