霍夫曼编码

这个句子“this is an example of a huffman tree”中得到的字母频率来建构霍夫曼树。句中字母的编码和频率如图所示。编码此句子需要135 bit（不包括保存树所用的空间）

字母	频率	编码
space	7	111
a	4	010
e	4	000
f	3	1101
h	2	1010
i	2	1000
m	2	0111
n	2	0010
s	2	1011
t	2	0110
l	1	11001
o	1	00110
p	1	10011
r	1	11000
u	1	00111
x	1	10010

霍夫曼编码（英语：Huffman Coding），又译为哈夫曼编码、赫夫曼编码，是一种用于无损数据压缩的熵编码（权编码）演算法。由美国计算机科学家大卫·霍夫曼于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年，于论文《一种构建极小多馀编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）中发表了这个编码方法。

问题定义与解法

Fig.1

Fig.2霍夫曼编码演算步骤, 左右树排列顺序可以加限制或不加限制

Fig.3

广义

• 给定

一组符号（Symbol）和其对应的权重值（weight），其权重通常表示成概率（%）。

• 欲知

一组二元的前置码，其二元码的长度为最短。

狭义

• 输入

符号集合$S=\left\{s_{1},s_{2},\cdots ,s_{n}\right\}$，其S集合的大小为$n$。

权重集合$W=\left\{w_{1},w_{2},\cdots ,w_{n}\right\}$，其W集合不为负数且$w_{i}=\mathrm {weight} \left(s_{i}\right),1\leq i\leq n$。

• 输出

一组编码$C\left(S,W\right)=\left\{c_{1},c_{2},\cdots ,c_{n}\right\}$，其C集合是一组二进制编码且$c_{i}$为$s_{i}$相对应的编码，$1\leq i\leq n$。

• 目标

设$L\left(C\right)=\sum _{i=1}^{n}{w_{i}\times \mathrm {length} \left(c_{i}\right)}$为$C$的加权的路径长，对所有编码$T\left(S,W\right)$，则$L\left(C\right)\leq L\left(T\right)$

范例

霍夫曼树常处理符号编写工作。根据整组资料中符号出现的频率高低，决定如何给符号编码。如果符号出现的频率越高，则给符号的码越短，相反符号的号码越长。假设我们要给一个英文单字"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）编码。由数字（重新）有序输入产生的代码有时被称为规范霍夫曼代码，并且由于易于编码/解码，通常是实践中使用的代码。用于找到该代码的技术有时被称为霍夫曼 - 香农 - 法诺编码，因为它像霍夫曼编码一样是最优的，但是在重量概率上是字母的，例如香农 - 法诺编码。

资料长度

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

• 熵（Entropy）:乱度

$entropy=-\sum _{j=1}^{J}{P\left(s_{j}\right)\times \ln {P\left(s_{j}\right)}}$

ex:
$P(S_{0})=1,entropy=0$
$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})=0.1,P(S_{4})=0.6,entropy=1.2275$
第三与第四个范例，同样是五种组合，机率分布越集中，则乱度越少

• 霍夫曼码平均长度

$mean\left(L\right)=\sum _{j=1}^{J}{P\left(s_{j}\right)\times \ L\left(s_{j}\right)}$

• 霍夫曼码的长度

Shannon编码定理： $entropy \over logk$ ≤ $mean\left(L\right)$ ≤ $entropy \over logk$ $+1$ ，若使用$k$进位的编码

霍夫曼码的平均编码长度：设$b=mean\left(L\right)N$，$N$为资料长度

$N$$entropy \over logk$ ≤ $b$ ≤ $N$$entropy \over logk$ $+N$

范例

• 当有100个位子，有白色占60%、咖啡色占20%，蓝色和红色各占10%，则该如何分配才能最佳化此座位?

(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}$是第L层的node，$S_{b}$是第L+1层的node

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

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

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

示范程式

// 以下為C++程式碼，在G++下編譯通過
// 僅用於示範如何根據權值建構霍夫曼樹，
// 沒有經過性能上的優化及加上完善的異常處理。
#include <cstdlib>
#include <iostream>
#include <deque>
#include <algorithm>

using namespace std;

const int size = 10;
struct node {                               // 霍夫曼樹節點結構
    unsigned key;                           // 保存權值
    node *lchild;                           // 左孩子指針
    node *rchild;                           // 右孩子指針
};
deque<node *> forest;
deque<bool> code;                           // 此處也可使用bitset
node *ptr;
int frequency[size] = {0};

void printCode(deque<bool> ptr);            // 用於輸出霍夫曼編碼

bool compare( node *a, node *b) {
    return a->key < b->key;
}
int main(int argc, char *argv[]) {
    for (int i = 0; i < size; i++) {
        cin >> frequency[i];                // 輸入10個權值
        ptr = new node;
        ptr->key = frequency[i];
        ptr->lchild = NULL;
        ptr->rchild = NULL;
        forest.push_back(ptr);
    } // 形成森林，森林中的每一棵樹都是一個節點
    // 從森林構建霍夫曼樹
    for (int i = 0; i < size - 1; i++) {
        sort(forest.begin(), forest.end(), compare);
        ptr = new node;
        // 以下代碼使用下標索引隊列元素，具有潛在危險，使用時請注意
        ptr->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<bool> ptr) {
    // deque<bool>
    for (int i = 0; i < ptr.size(); i++) {
        if (ptr[i])
            cout << "1";
        else
            cout << "0";
    }
}

霍夫曼编码C代码

huffman.h文件

#ifndef __HUFFMAN_H__
#define __HUFFMAN_H__
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define START printf("=====start=====\n")
#define END printf("=====end=====\n")
#define toByte(n) ((n) / 8 + ((n) % 8 > 0))

typedef struct HuffListNode HuffListNode,*hufflistnodep;
typedef struct HuffNode HuffNode,*huffnodep;
typedef struct HuffTree HuffTree,*hufftreep;
typedef struct HuffCode HuffCode,*huffcodep;
typedef struct HuffList HuffList,*hufflistp;
typedef struct HuffResult HuffResult,*huffresultp;
typedef struct HuffCode HuffBuf,*huffbufp;  //缓存类型

struct HuffListNode{
    huffnodep node;     //huffman节点
    hufflistnodep next; //后继节点
};  //huffman频率节点

struct HuffList{
    hufflistnodep head;         //头结点
    int keys[256];              //键值字典
    int size;                   //链表长度
};

struct HuffNode{
    int key;            //键
    int weight;         //权重
    huffnodep left;     //左节点
    huffnodep right;    //右节点
};  //huffman节点

struct HuffCode{
    char* code; //huffman code
    int size;   //huffman code size
};

struct HuffTree{
    huffnodep root;         //根
    huffcodep codes[256];   //key对应的代码
    int size;               //大小
};  //huffman树

struct HuffResult{
    char* code;      //生成的代码
    hufftreep tree;  //对应的霍夫曼树
};

#ifndef __BOOLEAN__
#define __BOOLEAN__
typedef enum{
    FALSE = 0,
    TRUE = 1,
}Boolean;
#endif

huffnodep huffnode(int key,int weight); //初始化huffman节点
hufflistp hufflist();   //初始化hufflist
Boolean insertHuffNode(hufflistp list,huffnodep node);  //向指定的节点链表添加一个节点
huffnodep shiftHuffNode(hufflistp list);    //删除第一个节点
hufftreep hufftree(hufflistp list);   //构建一棵huffman tree
huffbufp getFileBuf(const char* filename); //获取文件的buf
hufftreep genhuffcodes(hufftreep tree,huffnodep node,char codes[],int idx);  //获取当前节点之下的节点的huffman编码
hufflistp getHuffListByFile(const char* filename); //根据文件创建huffman链表
hufflistp getHuffListByBuf(huffbufp buf); //根据文件buf创建huffman链表
huffcodep getHuffCode(hufftreep tree,int key);  //获取指定键值的huffcode
huffresultp getHuffCodesByFile(const char* filename);     //获取文件的huffman code
huffresultp getHuffCodesByBuf(huffbufp buf);    //通过buf获取codes
huffbufp getOriginBuf(huffresultp result);       //从result中解析出原始的字符串
huffbufp str2bin(char* str); //二进制字符串转二进制数组
int putOriginToFile(huffresultp result,const char* filename);   //将result存储到filename中
char* bin2str(huffbufp buf);    //二进制数组转二进制字符串
huffbufp readHuffFile(const char* filename); //解析huff文件
#endif

huffman.c文件:

#include "huffman.h"

huffnodep huffnode(int key,int weight){
    huffnodep ret = (huffnodep)malloc(sizeof(HuffNode));
    ret->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 <= -256) return FALSE;
    hufflistnodep cur = list->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 < 256){
        list->keys[node->key] = node->weight;   //添加key到keys字典
    }
    list->size++;

    for(;cur != NULL  && cur->node->weight < node->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 < 256; i++){
        if(list->keys[i] > 0){   //插入存在的字符
            insertHuffNode(list,huffnode(i,list->keys[i]));
        }
    }

    return list;
}

huffcodep getHuffCode(hufftreep tree,int key){
    if(key < 256 && 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 < 256; i++){
        if(result->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 < 256; i++){
        if(result->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 < l; i++){
        int idx = i/8;
        int bi = i%8;
        buf->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 < buf->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 < key_size;){
        int offset = base+oft;
        unsigned char key = buf->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 < tmp->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 < 256; i++){
    //     if(codes[i]!=NULL){
    //         printf("%c[%d]:%s\n",i,i,codes[i]->code);
    //     }
    // }

    return getOriginBuf(result);
}

程序演示主文件:

#include"huffman.h"

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;
}

参考文献

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 16.3, pp. 385–392.

外部链接

• 有关霍夫曼压缩技术的原文：D.A. Huffman, "A method for the construction of minimum-redundancy codes", Proceedings of the I.R.E., sept 1952, pp 1098-1102
• 霍夫曼树图形演示 （页面存档备份，存于互联网档案馆）
• Animation of the Huffman Algorithm: Algorithm Simulation by Simon Mescal
• Background story: Profile: David A. Huffman, Scientific American, Sept. 1991, pp. 54-58
• n-ary Huffman Template Algorithm
• Huffman codes' connection with Fibonacci and Lucas numbers （页面存档备份，存于互联网档案馆）
• Fibonacci connection between Huffman codes and Wythoff array
• Sloane A098950 Minimizing k-ordered sequences of maximum height Huffman tree
• Computing Huffman codes on a Turing Machine
• Mordecai J. Golin, Claire Kenyon, Neal E. Young "Huffman coding with unequal letter costs （页面存档备份，存于互联网档案馆）", STOC 2002 （页面存档备份，存于互联网档案馆）: 785-791
• Huffman Coding, implemented in python