哈弗曼编码
Amethodfortheco
structio
ofmi
imumredu
da
cycodes
耿国华1数据结构1北京高等教育出版社2005182190
严蔚敏吴伟民数据结构C语言版M北京清华大学出版社1997
冯桂林其伟陈东华信息论与编码技术M北京清华大学出版社2007
刘大有唐海鹰孙舒杨等数据结构M北京高等教育出版社2001
压缩实现
速度要求
为了让它huffma
cpp快速运行，同时不使用任何动态库，比如STL或者MFC。它压
缩1M数据少于100ms（P3处理器，主频1G）
。
压缩过程
压缩代码非常简单，首先用ASCII值初始化511个哈夫曼节点：
CHuffma
Node
odes511
fori
t
Cou
t0
Cou
t256
Cou
t
odes
Cou
tbyAscii
Cou
t
其次，计算在输入缓冲区数据中，每个ASCII码出现的频率：
for
Cou
t0
Cou
t
SrcLe
Cou
t
odespSrc
Cou
t
Freque
cy
然后，根据频率进行排序：
qsort
odes256sizeofCHuffma
Nodefreque
cyCompare
哈夫曼树，获取每个ASCII码对应的位序列：
i
t
NodeCou
tGetHuffma
Tree
odes
构造哈夫曼树
构造哈夫曼树非常简单，将所有的节点放到一个队列中，用一个节点替换两个频率最低
的节点，新节点的频率就是这两个节点的频率之和。这样，新节点就是两个被替换节点的父
f节点了。如此循环，直到队列中只剩一个节点（树根）。
pare
t
ode
pNode
odes
Pare
tNode
popfirstchild
pNodepLeftPopNodepNodes
BackNodefalse
popseco
dchild
pNodepRightPopNodepNodes
BackNodetrue
adjustpare
tofthetwopoped
odes
pNodepLeftpPare
tpNodepRightpPare
tpNode
adjustpare
tfreque
cy
pNode
Freque
cypNodepLeft
Freque
cy

pNodepRight
Freque
cy
注意事项
有一个好的诀窍来避免使用任何队列组件。ASCII码只有256个，但实际分配了511个
CHuffma
Node
odes511，前255个记录ASCII码，而用后255个记录哈夫曼树中的
父节点。并且在构造树的时候只使用一个指针数组Chuffma
NodepNodes256来指向这
些节点。同样使用两个变量来操作队列索引i
t
Pare
tNode
NodeCou
t
BackNode
NodeCou
t1。
接着，压缩的最后一步是将每个ASCII编码写入输出缓冲区中：
i
t
DesI
dex0
looptowritecodes
for
Cou
t0
Cou
t
SrcLe
Cou
t
DWORDpDesPtr
DesI
dex3
odespSrc
Cou
tdwCode
DesI
dex7
DesI
dex
odespSrc
Cou
t
CodeLe
gth

DesI
dex33以8位为界限右移后到达右边字节的前面
f
DesI
dex77得到最高位
此外，在压缩缓冲区中，必须保存哈夫曼树的节点以及位序列，这样才能在解压缩时重
新构造哈夫曼树（只需保存ASCII值和对应的位序列）。
解压缩
解压缩比构造哈夫曼树要简单的多，将输入缓r