哈夫曼编码(Huffman Coding)

哈夫曼编码哈夫曼编码 哈夫曼编码 Huffman Coding 是一种编码方式 哈夫曼编码是可变字长编码 VL C 的一种 Huffman 于 1952 年提出一种编码方法 该方法完全依据字符出现概率来 构造异字头的平均长 度最短的码字 有时称之为最佳编码 一般就叫作Huffman 编码 以哈夫曼树 即最优二叉树 带权路径长度最小的二叉树 经常应用于数据压 缩 在计算机信息处理中 哈夫曼编码 是一种一致性编码法 又称 熵编码法 用于数据的无损耗压缩 这一术语是指使用一张特殊的编码表将源字符 例如某文件 中的一个符号 进行编码 这张编码表的特殊之处在于 它是根据每一个源字符出现的 估算概率而建立起来的 出现概率高的字符使用较短的编码 反之出现概率低的则使用 较长的编码 这便使编码之后的字符串的平均期望长度降低 从而达到无损压缩数据的 目的 这种方法是由 David A Huffman 发展起来的 例如 在英文中 e 的出现 概率很高 而 z 的出现概率则最低 当利用哈夫曼编码对一篇英文进行压缩时 e 极有可能用一个位 bit 来表示 而 z 则可能花去 25 个位 不是 26 用普通的表示 方法时 每个英文字母均占用一个字节 byte 即 8 个位 二者相比 e 使用了一 般编码的 1 8 的长度 z 则使用了 3 倍多 倘若我们能实现对于英文中各个字母出现 概率的较准确的估算 就可以大幅度提高无损压缩的比例 本文描述在网上能够找到的最简单 最快速的哈夫曼编码 本方法不使用任何扩展 动态库 比如 STL 或者组件 只使用简单的 C 函数 比如 memset memmove qsort malloc realloc 和 memcpy 因此 大家都会发现 理解甚至修改这个编码都是很容易的 背景 哈夫曼压缩是个无损的压缩算法 一般用来压缩文本和程序文件 哈夫曼压缩属于 可变代码长度算法一族 意思是个体符号 例如 文本文件中的字符 用一个特定长度 的位序列替代 因此 在文件中出现频率高的符号 使用短的位序列 而那些很少出现 的符号 则用较长的位序列 编码使用 我用简单的 C 函数写这个编码是为了让它在任何地方使用都会比较方便 你可以 将他们放到类中 或者直接使用这个函数 并且我使用了简单的格式 仅仅输入输出缓 冲区 而不象其它文章中那样 输入输出文件 bool CompressHuffman BYTE pSrc int nSrcLen BYTE bool DecompressHuffman BYTE pSrc int nSrcLen BYTE 要点说明 速度 为了让它 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 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 nFre quency 这里我用了一个好的诀窍来避免使用任何队列组件 我先前就直到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 3 nodes pSrc nCount dwCode 3 3 以 8 位为界限右移后到达右边字节的前面 nDesIndex DWORD nCode while nDesIndex 3 nSrcIndex pNode pRoot while pNode pLeft pNode nCode nCode 1 nSrcIndex pDes nDesIndex pNode byAscii 过程 include include include include include define M 10 typedef struct Fano Node char ch float weight FanoNode M typedef struct node int start int end struct node next LinkQueueNode typedef struct LinkQueueNode front LinkQueueNode rear LinkQueue void EnterQueue LinkQueue q int s int e LinkQueueNode NewNode NewNode LinkQueueNode malloc sizeof LinkQueueNode if NewNode NULL NewNode start s NewNode end e NewNode next NULL q rear next NewNode q rear NewNode else printf Error 按权分组 void Divide FanoNode f int s int m int e int i float sum sum1 sum 0 for i s i e i sum f weight m s sum1 0 for i s ifabs sum 2 sum1 2 f weight i 1 m if m i break main int i j n max m h M int sta mid end float w char c fc M M FanoNode FN LinkQueueNode p LinkQueue Q 初始化队 Q Q front LinkQueueNode malloc sizeof LinkQueueNode Q rear Q front Q front next NULL printf t FanoCoding n printf Please input the number of node 输入信息 scanf d i 1 while i n printf d weight and node i scanf f c for j 1 j i j if FN ch FN j ch printf Same node n break if i j i for i 1 i n i 排序 max i 1 for j max j n j max FN max weight FN j weight j max if FN weight FN max weight w FN weight FN weight FN max weight FN max weight w c FN ch FN ch FN max ch FN max ch c for i 1 ifront next NULL p Q front next 出队 Q front next p next if p Q rear Q rear Q front sta p start end p end free p Divide FN sta 按权分组 for i sta i m i fc h 0 h if sta m EnterQueue Q sta m else fc sta h sta 0 for i m 1 i end i fc h 1 h if m sta fc end h end 0 else EnterQueue Q m 1 end for i 1 i n i 打印编码信息 printf c FN ch printf s n fc system pause include include include include define N 100 define M 2 N 1 typedef char HuffmanCode 2 M typedef struct char weight int parent int LChild int RChild HTNode Huffman M 1 typedef struct Node int weight 叶子结点的权值 char c 叶子结点 int num 叶子结点的二进制码的长度 WNode WeightNode N 产生叶子结点的字符和权值 void CreateWeight char ch int s WeightNode CW int p int i j k int tag p 0 for i 0 ch 0 i tag 1 for j 0 j i j if ch j ch tag 0 break if tag CW p c ch CW p weight 1 for k i 1 ch k 0 k if ch ch k CW p weight s i 创建 HuffmanTree void CreateHuffmanTree Huffman ht WeightNode w int n int i j int s1 s2 for i 1 i n i ht weight w weight ht parent 0 ht LChild 0 ht RChild 0 for i n 1 i 2 n 1 i ht weight 0 ht parent 0 ht LChild 0 ht parent 0 for i n 1 i 2 n 1 i for j 1 j i 1 j if ht j parent break s1 j 找到第一个双亲不为零的结点 for j ht j weight j s1 ht s1 parent i ht LChild s1 for j 1 j i 1 j if ht j parent break s2 j 找到第一个双亲不为零的结点 for j ht j weight j s2 ht s2 parent i ht RChild s2 ht weight ht s1 weight ht s2 weight 叶子结点的编码 void CrtHuffmanNodeCode Huffman ht char ch HuffmanCode h WeightNo de weight int m int n int i j k c p start char cd cd char malloc n sizeof char cd n 1 0 for i 1 i n i start n 1 c i p ht parent while p start if ht p LChild c cd start 0 else cd start 1 c p p ht p parent weight num n start h char malloc n start sizeof char p 1 strcpy h system pause 所有字符的编码 void CrtHuffmanCode char ch HuffmanCode h HuffmanCode hc WeightN ode weight int n int m int i j k for i 0 i m i for k 1 k n k 从 weight k c 中查找与 ch 相等的下标 K if ch weight k c break hc char malloc weight k num 1 sizeof char for j 0 j weight k num j hc j h k j 解码 void TrsHuffmanTree Huffman ht WeightNode w HuffmanCode hc int n int m int i 0 j p printf StringInformation n while i m p 2 n 1 for j 0 hc j 0 j if hc j 0 p ht p LChild else p ht p RChild printf c w p c 打印原信息 i main int i n m s1 s2 j n 为叶子结点的个数 char ch N w N ch N 存放输入的字符串 Huffman ht 二叉数 HuffmanCode h hc h 存放叶子结点的编码 hc 存放所有结点的编码 WeightNode weight 存放叶子结点的信息 printf t HuffmanCoding n printf please input information gets ch 输入字符串 CreateWeight ch 产生叶子结点信息 m 为字符串 ch 的长 度 printf WeightInformation n Node 输出叶子结点的字符与权值 for i 1 i n i printf c weight c printf nWeight for i 1 i n i printf d weight weight CreateHuffmanTree 产生 Huffman 树 printf n HuffamnTreeInformation n for i 1 i 2 n 1 i 打印 Huffman 树的信息 printf t d d d d n i ht weight ht parent ht LChild ht RChild CrtHuffmanNodeCode ht ch 叶子结点的编码 printf NodeCode n 打印叶子结点的编码 for i 1 i n i printf t c weight c printf s n h CrtHuffmanCode ch h 所有字符的编码 printf StringCode n 打印字符串的编码 for i 0 i m i printf s hc system pause TrsHuffmanTree ht weight hc n m 解码 system pause Matlab 中简易实现 Huffman 编译码 n input Please input the total number hf zeros 2 n 1 5 hq for ki 1 n hf ki 1 ki hf ki 2 input Please input the frequency hq hq hf ki 2 end for ki n 1 2 n 1 hf ki 1 ki mhq1 min