繁體中文当前位置: 首页 > 图文教程 > 开发语言 > VC++ > 简单快速的哈夫曼编码
- VC++
- 用 auto_ptr 类模板帮助动态内存管理
- 走近 STL
- 一步一步学STL标准模板库
- 使用 <multimap> 库创建重复键关联容器
- 使用 <map> 库创建关联容器
- 用 vectors 改进内存的再分配
- 用函数模板实现和优化抽象操作
- STL 字符串类与 UNICODE 及其它......
- 如何在Dll中导出STL类
- 再谈“在STL列表（Lists）中插入不同类型的对象”
- 使用::std::vector<>作为管理动态数组的优先选择
- 三种常见中文内码的转换方法
- JNI 中文处理问题小结
- 构建 GB2312 汉字库的 unicode 码表
- 正则表达式简介
- 在非MFC程序中引用CString
- UTF-8与GB2312之间的互换
- 宽字符标量L"xx"在VC6.0/7.0和GNU g++中的不同实现
- 用VC++设计语法编辑器
- C语言中对时间和日期的处理
VC++ 中的 简单快速的哈夫曼编码
出处:互联网 整理: 软晨网（RuanChen.com） 发布: 2009-10-30 浏览: 80 ::
收藏到网摘: 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) 