繁體中文当前位置: 首页 > 图文教程 > 开发语言 > VC++ > 简单快速的哈夫曼编码
- VC++
- 在Dialog中使用Menu和Toolbar
- 如何定制对话框中的回车键
- 再谈 Windows 2000 “打开”文件对话框
- Windows2000新型Open对话框的使用
- Windows SDK 非模态对话框的消息处理
- VC6中使用CHtmlView在对话框控制中显示HTML文件
- Windows 2000 UI 新特点之四：其他类型的外壳扩展
- Windows 2000 UI 新特点之二：自定义文件夹栏目
- Windows 2000 UI 新特点之三：搜索管理器
- Windows 2000 UI 新特点之一：信息条提示（Infotip）
- 数据库异步操作(ADODB)
- VC++：小编谈自动注册数据源(DSN)
- VC++：小编分享面向对象特征及其优点
- VC++：VC++中Windows 3.x的协同多任务
- VC++：小编浅谈VC++中的CRecordset类
- VC++：小编浅谈ODBC概念，了解ODBC不在是难事
- VC++：小编谈用ODBC创建表
- VC++：小编浅谈用DAO创建表
- VC++：浅析VC++中传统控件的控件通知消息
- VC++：小编浅谈静态控件
VC++ 中的 简单快速的哈夫曼编码
出处:互联网 整理: 软晨网（RuanChen.com） 发布: 2009-10-30 浏览: 67 ::
收藏到网摘: n/a
简单快速的哈夫曼编码 作者：Hatem Mostafa 译者：happyparrot 下载源代码 因此，大家都会发现，理解甚至修改这个编码都是很容易的。 哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。 编码使用 我用简单的C函数写这个编码是为了让它在任何地方使用都会比较方便。你可以将他们放到类中，或者直接使用这个函数。并且我使用了简单的格式，仅仅输入输出缓冲区，而不象其它文章中那样，输入输出文件。 bool CompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen);bool DecompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen);要点说明 速度 压缩 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;}
注意：在压缩缓冲区中，我们必须保存哈夫曼树的节点以及位序列，这样我们才能在解压缩时重新构造哈夫曼树（只需保存ASCII值和对应的位序列）。 解压缩 |
评论 (0) 