当前位置: 首页 > 图文教程 > 开发语言 > VC++ > 简单快速的哈夫曼编码

VC++
用VC++创建自定义向导程序
自定义 CRichEditCtrl 控件
Office 2000 风格的停泊、智能型菜单
黑客攻击手段之偷梁换柱
完善 CPopupText 类
让工具条显示256色图像
定制编辑框的上下文菜单
列表控件排序功能的实现
一个优秀的网格控件CGridCtrl
如何用代码动态添加控件
如何在编辑框中使用IAutoComplete接口
应用程序中添加“Coolbars”的简单方法
介绍一个有Toolbar功能的可重用类 CPopupText
在工具栏按钮上添加文本标签
类似Dreamweaver的颜色选择器
如何设置ListView控件的完全行(Full Row)选项
如何enable/disable菜单项
关于CEdit控件的透明 --作者：monsoon
动态菜单项、状态条提示、工具条提示问题
CAnimateCtrl::Open的使用问题

No. « 18 19 20 21 »

技术文章搜索

关键字

VC++ 中的 简单快速的哈夫曼编码

出处:互联网   整理: 软晨网（RuanChen.com）   发布: 2009-10-30   浏览: 73 ::
收藏到网摘: n/a

简单快速的哈夫曼编码

作者：Hatem Mostafa
译者：happyparrot

下载源代码

介绍

本文描述在网上能够找到的最简单，最快速的哈夫曼编码。本方法不使用任何扩展动态库，比如STL或者组件。只使用简单的C函数，比如：memset，memmove，qsort，malloc，realloc和memcpy。

因此，大家都会发现，理解甚至修改这个编码都是很容易的。



背景

哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。

编码使用

我用简单的C函数写这个编码是为了让它在任何地方使用都会比较方便。你可以将他们放到类中，或者直接使用这个函数。并且我使用了简单的格式，仅仅输入输出缓冲区，而不象其它文章中那样，输入输出文件。

bool CompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen);bool DecompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen);
要点说明

速度

为了让它(huffman.cpp)快速运行，我花了很长时间。同时，我没有使用任何动态库，比如STL或者MFC。它压缩1M数据少于100ms（P3处理器，主频1G）。

压缩

压缩代码非常简单，首先用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 nodepNode = &nodes[nParentNode++];// pop first childpNode->pLeft = PopNode(pNodes, nBackNode--, false);// pop second childpNode->pRight = PopNode(pNodes, nBackNode--, true);// adjust parent of the two poped nodespNode->pLeft->pParent = pNode->pRight->pParent = pNode;// adjust parent frequencypNode->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 codesfor(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值和对应的位序列）。

解压缩

解压