Huffman 算法原理
前缀码
在一个字符集中&＃xff0c;任何一个字符的编码都不是另一个字符编码的前缀&＃xff0c;即前缀码。 例如&＃xff0c;有两个码字 111 与 1111&＃xff0c;那么这两个码字就不符合前缀码的规则&＃xff0c;因为 111 是
1111 的前缀。放到二叉树里来讲&＃xff0c;只用叶子节点编码的码字才是前缀码&＃xff0c;如果同时使用 中间节点和叶子节点编码&＃xff0c;那结果就不是前缀码。因为压缩中经过编码的码字全部是前 缀码&＃xff0c;所以在对照码表解压的时候&＃xff0c;碰到哪个码字就是哪个码字&＃xff0c;不用担心出现某个字 符的编码是另一个字符的编码的前缀的情况&＃xff0c;该意识一定要具备。
关于前缀码&＃xff0c;下面一段话摘自《算法导论》&＃xff1a;“前缀码的作用是简化解码过程。由于 没有码字是其他码字的前缀&＃xff0c;编码文件的开始码字是无歧义的。我们可以简单的识别出 开始码字&＃xff0c;将其转换会原字符&＃xff0c;然后对编码文件剩余部分重复这种解码过程。
1111111 ? 111 1111 ? 1111 111
哈夫曼编码
哈夫曼设计了一个贪心算法来构造最优前缀码&＃xff0c;被称为哈夫曼编码&＃xff08;Huffman code&＃xff09;&＃xff0c; 其正确性证明依赖于贪心选择性质和最优子结构。哈夫曼编码可以很有效的压缩数据&＃xff0c;
具体压缩率依赖于数据本身的特性。这里我们先介绍几个概念&＃xff1a;码字、码字长度、定长 编码与变长编码。
每个字符可以用一个唯一的二进制串表示&＃xff0c;这个二进制串称为这个字符的码字&＃xff0c;这 个二进制串的长度称为这个码字的码字长度。码字长度固定就是定长编码&＃xff0c;码字长度不 同则为变长编码。变长编码可以达到比定长编码好得多的压缩率&＃xff0c;其思想是赋予高频字 符&＃xff08;出现频率高的字符&＃xff09;短&＃xff08;码字长度较短&＃xff09;码字&＃xff0c;赋予低频字符长码字。例如&＃xff0c;我们 用 ASCII 字符编辑一个文本文档&＃xff0c;不论字符在整个文档中出现的频率&＃xff0c;每个字符都要占 用一个字节&＃xff1b;如果我们使用变长编码的方式&＃xff0c;每个字符因在整个文档中的出现频率不同 导致码字长度不同&＃xff0c;有的可能占用一个字节&＃xff0c;而有的可能只占用一比特&＃xff0c;这个时候&＃xff0c;整 个文档占用空间就会比较小了。当然&＃xff0c;如果这个文本文档相当大&＃xff0c;导致每个字符的出现 频率基本相同&＃xff0c;那么此时所谓变长编码在压缩方面的优势就基本不存在了&＃xff08;这点要十分 明确&＃xff0c;这是为什么压缩要分块的原因之一&＃xff0c;后续源码分析会详细讲解&＃xff09;。
哈夫曼编码会自底向上构造出一棵对应最优编码的二叉树&＃xff0c;我们使用下面这个例子 来说明哈夫曼树的构造过程。首先&＃xff0c;我们已知在某个文本中有如下字符及其出现频率&＃xff0c;
| 字符 | a | b | c | d | e | f |
| 出现频率 | 45 | 13 | 12 | 16 | 9 | 5 |
构造过程如下图所示&＃xff1a;
图 1 到图 6 列除了整个哈夫曼树构造过程中的每个步骤。在一开始&＃xff0c;每个字符都已 经按照出现频率大小排好顺序&＃xff0c;在后续的步骤中&＃xff0c;每次都将频率最低的两棵树合并&＃xff0c;然 后用合并后的结果再次排序&＃xff08;注意&＃xff0c;排序不是目的&＃xff0c;目的是找到这时出现频率最低的两 项&＃xff0c;以便下次合并。gzip 源码中并没有专门去“排序”&＃xff0c;而是使用专门的数据结构把频率 最低的两项找到即可&＃xff09;。叶子节点用矩形表示&＃xff0c;每个叶子节点包含一个字符及其频率。中 间节点用圆圈表示&＃xff0c;包含其孩子节点的频率之和。中间节点指向左孩子的边标记为 0&＃xff0c; 指向右孩子的边标记为 1。一个字符的码字对应从根到其叶节点的路径上的边的标签序 列。图 1 为初始集合&＃xff0c;有六个节点&＃xff0c;每个节点对应一个字符&＃xff1b;图 2 到图 5 为中间步骤&＃xff0c;
图 6 为最终哈夫曼树。此时每个字符的编码都是前缀码。
哈夫曼压缩和解压文件
利用库中的优先级队列实现哈夫曼树&＃xff0c;最后基于哈夫曼树最终实现文件压缩。
1.统计文件中字符出现的次数&＃xff0c;利用优先级队列构建 Haffman 树&＃xff0c;生成 Huffman 编 码。构造过程可以使用 priority_queue 辅助&＃xff0c;每次 pq.top()都可以取出权值&＃xff08;频数&＃xff09;最小 的节点。每取出两个最小权值的节点&＃xff0c;就 new 出一个新的节点&＃xff0c;左右孩子分别指向它 们。然后把这个新节点 push 进优先队列。
2.压缩&＃xff1a;利用 Haffman 编码对文件进行压缩&＃xff0c;即在压缩文件中按顺序存入每个字符 的 Haffman 编码。 码表&＃xff08;实际存储是对应数值的概率&＃xff0c;然后调用程序生成码表&＃xff09; &＃43; 编码
3.将文件中出现的字符以及它们出现的次数写入配置文件中&＃xff0c;以便后续压缩使用。
4.解压缩&＃xff1a;利用配置文件重构 Haffman 树&＃xff0c;对文件进行减压缩。
HuffmanTree.hpp
#ifndef _HUFFMAN_TREE_H_
#define _HUFFMAN_TREE_H_
#include
#include
#include
#include
using namespace std;template
struct HuffmanTreeNode
{HuffmanTreeNode(const W &weight): _pLeft(NULL), _pRight(NULL), _pParent(NULL), _weight(weight){}HuffmanTreeNode
};template
class HuffmanTree
{typedef HuffmanTreeNode
public:HuffmanTree(): _pRoot(NULL){}HuffmanTree(W*array, size_t size, const W&invalid){_CreateHuffmantree(array, size, invalid);}void _Destroy(PNode&pRoot){//后序if (pRoot){_Destroy(pRoot->_pLeft);_Destroy(pRoot->_pRight);delete pRoot;pRoot &＃61; NULL;}}~HuffmanTree(){_Destroy(_pRoot);}PNode GetRoot(){return _pRoot;}
private: //构建哈夫曼树void _CreateHuffmantree(W*array, size_t size, const W&invalid){struct PtrNodeCompare{bool operator()(PNode n1, PNode n2)//重载“&＃xff08;&＃xff09;”{return n1->_weight
};
#endif
FileCompress.hpp
/*利用库中的优先级队列实现哈夫曼树&＃xff0c;最后基于哈夫曼树最终实现文件压缩。
描述&＃xff1a; 1.统计文件中字符出现的次数&＃xff0c;利用优先级队列构建Haffman树&＃xff0c;生成Huffman编码。 构造过程可以使用priority_queue辅助&＃xff0c;每次pq.top()都可以取出权值&＃xff08;频数&＃xff09;最小的节点。每取出两个最小权值的节点&＃xff0c;就new出一个新的节点&＃xff0c;左右孩子分别指向它们。然后把这个新节点push进优先队列。 2.压缩&＃xff1a;利用Haffman编码对文件进行压缩&＃xff0c;即在压缩文件中按顺序存入每个字符的Haffman编码。 3.将文件中出现的字符以及它们出现的次数写入配置文件中&＃xff0c;以便后续压缩使用。 4.解压缩&＃xff1a;利用配置文件重构Haffman树&＃xff0c;对文件进行减压缩。
*/
#ifndef _FILE_COMPRESS_H_
#define _FILE_COMPRESS_H_
#include "HuffmanTree.hpp"
#include
#include
#include
#include
using namespace std;unsigned long getFileSize(const char *path)
{unsigned long filesize &＃61; -1;FILE *fp;fp &＃61; fopen(path, "r");if(fp &＃61;&＃61; NULL)return filesize;fseek(fp, 0L, SEEK_END);filesize &＃61; ftell(fp);fclose(fp);return filesize;
}typedef unsigned int CountType;
typedef unsigned char CharType;
struct CharInfo
{CharType _ch;//字符CountType _count;//次数string _code;//编码bool operator!&＃61;(const CharInfo &info){return _count !&＃61; info._count;}CharInfo operator&＃43;(const CharInfo &info){CharInfo ret;ret._count &＃61; _count &＃43; info._count;return ret;}bool operator<(const CharInfo &info){return _count > info._count;}
};class FileCompress
{typedef HuffmanTreeNode
};#endif
main.cpp
/** &＃64;Author: your name* &＃64;Date: 2020-06-04 16:21:01* &＃64;LastEditTime: 2020-06-04 19:13:01* &＃64;LastEditors: Please set LastEditors* &＃64;Description: In User Settings Edit* &＃64;FilePath: \huffman\main.cpp*/
/*利用库中的优先级队列实现哈夫曼树&＃xff0c;最后基于哈夫曼树最终实现文件压缩。
描述&＃xff1a; 1.统计文件中字符出现的次数&＃xff0c;利用优先级队列构建Haffman树&＃xff0c;生成Huffman编码。 构造过程可以使用priority_queue辅助&＃xff0c;每次pq.top()都可以取出权值&＃xff08;频数&＃xff09;最小的节点。每取出两个最小权值的节点&＃xff0c;就new出一个新的节点&＃xff0c;左右孩子分别指向它们。然后把这个新节点push进优先队列。 2.压缩&＃xff1a;利用Haffman编码对文件进行压缩&＃xff0c;即在压缩文件中按顺序存入每个字符的Haffman编码。 3.将文件中出现的字符以及它们出现的次数写入配置文件中&＃xff0c;以便后续压缩使用。 4.解压缩&＃xff1a;利用配置文件重构Haffman树&＃xff0c;对文件进行减压缩。
*/#include "FileCompress.hpp"
#include
#include
#include
#include
// 编译 g&＃43;&＃43; -o huffman main.cpp HuffmanTree.hpp FileCompress.hpp -std&＃61;c&＃43;&＃43;11
int main(int argc, char** argv)
{if (argc !&＃61; 2){std::cout <<"usage: " <
g&＃43;&＃43; -o huffman main.cpp HuffmanTree.hpp FileCompress.hpp -std&＃61;c&＃43;&＃43;11
![[大整数乘法] java代码实现](https://img1.php1.cn/3cd4a/24c6f/9f3/0133bb25da242824.jpeg)
京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有 