huffman压缩c

1. 算法解析：哈夫曼（huffman）压缩算法

本篇将介绍 哈夫曼压缩算法（Huffman compression）

众所周知，计算机存储数据时，实际上存储的是一堆0和1（二进制）。

如果我们存储一段字符：ABRACADABRA!

那么计算机会把它们逐一翻译成二进制，如A：01000001；B: 01000010; !: 00001010.

每个字符占8个bits, 这一整段字符则至少占12*8=96 bits。

但如果我们用一些特殊的值来代表这些字符，如：

图中，0代表A; 1111代表B；等等。此时，存储这段字符只需30bits，比96bits小多了，达到了压缩的目的。

我们需要这么一个表格来把原数据翻译成特别的、占空间较少的数据。同时，我们也可以用这个表格，把特别的数据还原成原数据。

首先，为了避免翻译歧义，这个表格需满足一个条件： 任何一个字符用的值都不能是其它字符的前缀 。

我们举个反例：A: 0; B: 01;这里，A的值是B的值的前缀。如果压缩后的数据为01xxxxxx,x为0或者1，那么这个数据应该翻译成A1xxxxxx, 还是Bxxxxxxx?这样就会造成歧义。

然后，不同的表格会有不同的压缩效果，如：

这个表格的压缩效果更好。

那么我们如何找到 最好的表格 呢？这个我们稍后再讲。

为了方便阅读，这个表格是可以写成一棵树的：

这棵树的节点左边是0，右边是1。任何含有字符的节点都没有非空子节点。（即上文提及的前缀问题。）

这棵树是在压缩的过程中建成的，这个表格是在树形成后建成的。用这个表格，我们可以很简单地把一段字符变成压缩后的数据，如：

原数据：ABRACADABRA!

表格如上图。

令压缩后的数据为S；

第一个字符是A，根据表格，A：11，故S=11;

第二个字符是B，根据表格，B：00，故S=1100;

第三个字符是R，根据表格，R：011，故S=1100011;

如此类推，读完所有字符为止。

压缩搞定了，那解压呢？很简单，跟着这棵树读就行了：

压缩后的数据S=11000111101011100110001111101

记住，读到1时，往右走，读到0时，往左走。

令解压后的字符串为D；

从根节点出发，第一个数是1，往右走：

第二个数是1，往右走：

读到有字符的节点，返回此字符，加到字符串D里。D:A;

返回根节点，继续读。

第三个数是0，往左走：

第四个数是0，往左走：

读到有字符的节点，返回此字符，加到字符串D里。D:AB;

返回根节点，继续读。

第五个数是0，往左走：

第六个数是1，往右走：

第七个数是1，往右走：

读到有字符的节点，返回此字符，加到字符串D里。D:ABR;

返回根节点，继续读。

如此类推，直到读完所有压缩后的数据S为止。

压缩与解压都搞定了之后 我们需要先把原数据读一遍，并把每个字符出现的次数记录下来。如：

ABRACADABRA!中，A出现了5次;B出现了2次;C出现了1次;D出现了1次;R出现了2次;!出现了1次。

理论上，出现频率越高的字符，我们给它一个占用空间越小的值，这样，我们就可以有最佳的压缩率

由于哈夫曼压缩算法这块涉及内容较多 ，文章篇幅很长；全文全方面讲解了Compose布局的各方面知识。更多Android前言技术进阶，我自荐一套《 完整的Android的资料，以及一些视频课讲解 》 现在私信发送“进阶”或者“笔记”即可免费获取

最后我想说：

对于程序员来说，要学习的知识内容、技术有太多太多，要想不被环境淘汰就只有不断提升自己，从来都是我们去适应环境，而不是环境来适应我们

技术是无止境的，你需要对自己提交的每一行代码、使用的每一个工具负责，不断挖掘其底层原理，才能使自己的技术升华到更高的层面

Android 架构师之路还很漫长，与君共勉

2. 哈夫曼编码的压缩实现

压缩代码非常简单，首先用ASCII值初始化511个哈夫曼节点：
CHuffmanNode nodes[511];
for(int nCount = 0; nCount < 256; nCount++)
nodes[nCount].byAscii = nCount;
其次，计算在输入缓冲区数据中，每个ASCII码出现的频率：
for(nCount = 0; nCount < nSrcLen; nCount++)
nodes[pSrc[nCount]].nFrequency++;
然后，根据频率进行排序：
qsort(nodes, 256, sizeof(CHuffmanNode), frequencyCompare);
哈夫曼树，获取每个ASCII码对应的位序列：
int nNodeCount = GetHuffmanTree(nodes); 构造哈夫曼树非常简单，将所有的节点放到一个队列中，用一个节点替换两个频率最低的节点，新节点的频率就是这两个节点的频率之和。这样，新节点就是两个被替换节点的父节点了。如此循环，直到队列中只剩一个节点（树根）。
// parent node
pNode = &nodes[nParentNode++];
// pop first child
pNode->pLeft = PopNode(pNodes, nBackNode--, false);
// pop second child
pNode->pRight = PopNode(pNodes, nBackNode--, true);
// adjust parent of the two poped nodes
pNode->pLeft->pParent = pNode->pRight->pParent = pNode;
// adjust parent frequency
pNode->nFrequency = pNode->pLeft->nFrequency + pNode->pRight->nFrequency; 有一个好的诀窍来避免使用任何队列组件。ASCII码只有256个，但实际分配了511个(CHuffmanNode nodes[511])，前255个记录ASCII码，而用后255个记录哈夫曼树中的父节点。并且在构造树的时候只使用一个指针数组(ChuffmanNode *pNodes[256])来指向这些节点。同样使用两个变量来操作队列索引(int nParentNode = nNodeCount;nBackNode = nNodeCount –1)。
接着，压缩的最后一步是将每个ASCII编码写入输出缓冲区中：
int nDesIndex = 0;
// loop to write codes
for(nCount = 0; nCount < nSrcLen; nCount++)
{
*(DWORD*)(pDesPtr+(nDesIndex>>3)) |=
nodes[pSrc[nCount]].dwCode << (nDesIndex&7);
nDesIndex += nodes[pSrc[nCount]].nCodeLength;
}
(nDesIndex>>3): >>3 以8位为界限右移后到达右边字节的前面
(nDesIndex&7): &7 得到最高位.
此外，在压缩缓冲区中，必须保存哈夫曼树的节点以及位序列，这样才能在解压缩时重新构造哈夫曼树（只需保存ASCII值和对应的位序列）。 解压缩比构造哈夫曼树要简单的多，将输入缓冲区中的每个编码用对应的ASCII码逐个替换就可以了。只要记住，这里的输入缓冲区是一个包含每个ASCII值的编码的位流。因此，为了用ASCII值替换编码，我们必须用位流搜索哈夫曼树，直到发现一个叶节点，然后将它的ASCII值添加到输出缓冲区中：
int nDesIndex = 0;
DWORD nCode;
while(nDesIndex < nDesLen)
{
nCode = (*(DWORD*)(pSrc+(nSrcIndex>>3)))>>(nSrcIndex&7);
pNode = pRoot;
while(pNode->pLeft)
{
pNode = (nCode&1) ? pNode->pRight : pNode->pLeft;
nCode >>= 1;
nSrcIndex++;
}
pDes[nDesIndex++] = pNode->byAscii;
}

3. Huffman编码不适合图像压缩么，为什么。有相关的资料么。能给我看看不QQ504278770

下面是我从网上搜索到的资料，希望对你有帮助。

1.哈夫曼图像压缩算法引言

随着网络与多媒体技术的兴起，人们需要存储和传输的数据越来越多，数据量越来越大，以前带宽有限的传输网络和容量有限的存储介质难以满足用户的需求。

特别是声音、图像和视频等媒体在人们的日常生活和工作中的地位日益突出，这个问题越发显得严重和迫切。如今，数据压缩技术早已是多媒体领域中的关键技术之一。

Huffman(哈夫曼)算法在上世纪五十年代初提出来了，它是一种无损压缩方法，在压缩过程中不会丢失信息熵，而且可以证明Huffman算法在无损压缩算法中是最优的。Huffman原理简单，实现起来也不困难，在现在的主流压缩软件得到了广泛的应用。对应用程序、重要资料等绝对不允许信息丢失的压缩场合，Huffman算法是非常好的选择。

2.哈夫曼图像压缩算法原理

Huffman编码是1952年由Huffman提出的对统计独立信源能达到最小平均码长的编码方法。这一年，他发表了着名论文“A Method for the Construction of Minimum Rendancy Codes”，即最短冗余码的构造方法.之后，Huffman编码及其一些改进方法一直是数据压缩领域的研究热点之一。

Huffman码是一种变长码，其基本思想是：先统计图像(已经数字化)中各灰度出现的概率，出现概率较大的赋以较短的码字，而出现概率较小的则赋以较长的码字。我们可以用下面的框图来表示Huffman编码的过程：

在整个编码过程中，统计图像各灰度级出现的概率和编码这两步都很简单，关键的是Huffman树的构造。不但编码的时候需要用到这颗树，解码的时候也必须有这颗树才能完成解码工作，因此，Huffman树还得完整的传输到解码端。

Huffman树的构造可以按照下面图2的流程图来完成。首先对统计出来的概率从小到大进行排序，然后将最小的两个概率相加;到这儿的时候，先把已经加过的两个概率作为树的两个节点，并把他们从概率队列中删除;然后把相加所得的新概率加入到队列中，对这个新队列进行排序。

如此反复，直到最后两个概率相加为1的时候停止。这样，Huffman树就建立起来了。

3. 哈夫曼图像压缩算法软件实现

这儿，我们以Turbo C为例来说明软件实现Huffman图像压缩算法的一些关键技术。

为了叙述方便，我们不妨假设处理的图像的灰度级变化范围从0到255，即具有256个灰度级。我们先来统计输入图像的概率，实际上是要统计各个灰度级在整幅图像中出现的次数。为此，我们先定义一个具有256个元素的数组。

然后对输入图像信号进行扫描，每出现一个灰度，就把它存入实现定义好的一个数组中的相应元素中(让这个元素的值自增1)。最后，通过读取数组中各元素的值就可以求出各个灰度出现的频数。

接下来就该构造Huffman树了。为了构造Huffman树，我们要用到C语言中链表的概念。我们必须用一个结构体来表示Huffman树的节点。对于每个节点而言我们需要这样几个信息：本节点的权重(就是灰度的频数)、指向父节点的指针和分别指向左右子叶节点的指针。于是，我们可以定义这样一个结构体：

Struct Node{

Floatweight;

Node * father;

Node * left;

Node * right;}Huffman_Node

我们需要先确定权最低的两个自由结点，这将是最初的left和right节点。然后建立这两个结点的父结点，并让它的权等于这两个结点的权之和。

接着将这个父结点增加到自由结点的序列中，而两个子结点则从序列中去掉。重复前面的步骤直到只剩下一个自由结点，这个自由结点就是Huffman树的根。

Huffman编码树作为一个二叉树从叶结点逐步向上建立。Huffman树建立好以后，为了把权、概率等数值转化码字，我们还得对整个Huffman树进行扫描。请注意，在建立Huffman树的时候，我们是从树叶开始的，而在对Huffman树分配码字的时候却刚好相反，是从树根开始，沿着各个树枝的走向“顺藤摸瓜”似的对各个系数进行编码。

对于一个节点的两个子节点(left和right)，其中一个节点对应的位为0，而另一个结点则人为地设置成为l。解码的时候也是完全相同的一颗Huffman树完成的。下面的循环是实现压缩的关键语句之一[ 1 ]。

for (i = length-1; i >= 0; ――i) {

if ((current_code >> i) & 1)

thebyte |= (char) (1 << curbit);

if (--curbit < 0) {

putc (thebyte, ofile);

thebyte = 0;

curbyte++;

curbit = 7;

}

}

注意：这几行代码执行了数据压缩的功能，但是还没有生成编码和解码所需要的代码表。

4.哈夫曼图像压缩算法性能评价

我们主要从三方面[ 2 ]来评价Huffman的性能：

(1)压缩比的大小;

(2)恢复效果的好坏，也就是能否尽可能的恢复原始数据;

(3)算法的简单易用性以及编、解码的速度。

首先分析一下对压缩比的影响因素(不同的着作中对压缩比的定义不尽相同，这儿我们采用如下定义：压缩比等于压缩之前的以比特计算的数据量比上压缩之后的数据量)。对于Huffman编码来说，我们因为要用额外的位保存和传输Huffman树而“浪费”掉一些存储位，也就是说，为了编、解码的方便，我们把本已减少的数据量又增加了一些。

如果文件比较大的话，这一点多余的数据根本算不了什么，所占比例很小。但是，如果压缩的文件本来就很小的话，那么这笔数据就很可观了。一般来说，经典的Huffman算法的压缩比不是很高，这是无损压缩的“通病”。

第二点就不用说了，由于它是无损压缩，能够完全恢复压缩之前图像的本来面貌。

最后，让我们来分析一下Huffman压缩方法的速度问题。大家在第三节中已经看到了，在压缩的过程中，我们进行了两次扫描，第一次是为了统计各个灰度出现的频数而扫描整幅图像，第二次则是为了分配码字而扫描整个Huffman树。

这样一来，对较大的文件进行编码时，频繁的磁盘读写访问必然会降低数据编码的速度，如果用于网络的话，还会因此带来一些延时，不利于实时压缩和传输。另外，Huffman算法的编码和解码的速度是不对称的，解码快于编码，因为解码不需要生成Huffman树的环节。

5.图像压缩算法结束语

Huffman算法目前已经得到了广泛的应用，软件和硬件都已经实现。基于Huffman经典算法的缺陷，不少人提出了一些自适应算法。前面的算法中，Huffman树是整个图像全部输入扫描完成后构造出来的，而自适应算法(或称动态算法)则不必等到全部图像输入完成才开始树的构造，并且可以根据后面输入的数据动态的对Huffman树进行调整。实际上，实用的Huffman树都是经过某种优化后的动态算法。

网络资源