in Algorithm

霍夫曼树和霍夫曼编码

一、定义

霍夫曼树

又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的路径长度是从树根到每一结点的路径长度之和,记为 WPL =(W1*L1 + W2*L2 + W3*L3 +...+ Wn*Ln)N个权值 Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为 Li(i=1,2,...n)。可以证明霍夫曼树的 WPL 是最小的。

Huffman tree & encoding

霍夫曼编码

是一种基于霍夫曼树的用于无损数据压缩的熵编码(权编码)算法。

由于霍夫曼树具有 WPL 最小的特性,可认为霍夫曼树中权值越大的叶子结点路径越短,可用霍夫曼树所有叶子结点的路径生成编码方案,其特点是权重越大的结点路径编码越短,反之则越长。

用途

按照 Wikipedia 的说法:

霍夫曼树常处理符号编写工作。根据整组资料中符号出现的频率高低,决定如何给符号编码。如果符号出现的频率越高,则给符号的码越短,相反符号的号码越长。

显然,这种编码适用于对高频出现的数据进行编码上的无损压缩,只要知道如何构造一颗霍夫曼树,就能对生成的编码进行解码。

二、实现

霍夫曼树的结点

结点包含如下要素:

  • data: 存储的数据(本例中为单个字符)
  • weight: 权重
  • leftChild/rightChild: 下接的左右子树(形成一个递归的二叉树结构)
  • IsLeaf(): 判断本结点是否为叶子结点
  • 构造函数

结点的实现:

霍夫曼树的概念结构

树本身是一个概念结构, 包含如下要素:

  • nodesTree: 结点数据(用于生成霍夫曼树)
  • codingMap: 字符和它的编码映射关系
  • huffmanTree: 运行时生成的最优二叉树(霍夫曼树)
  • PickMinWeightNode(): 从结点数据中选择一个 weight 最小的结点
  • CalcWPL(): 生成某个结点的 WPL
  • GenerateCodingMap(): 生成字符和它的编码映射关系
  • WPL: 加权路径长度
  • GetHuffmanCode(): 获取字符的编码
  • Encode(): 编码(tuple 元素分别为编码的 字符串 和 布尔串 形式)
  • Decode(): 解码
  • 构造函数

树的构造

  • 不断地查找结点数据 nodesTree 中 weight 最小的结点,并将其从nodesTree 中删除,每两个最小结点以组成一颗新的结点,其 weight 为两结点 weight 之和,两结点成为新结点的左右子结点,将新结点再次回入到 nodesTree 中
  • 重复以上过程,直至清空 nodesTree
  • 生成的 huffmanTree 即为最优二叉树
  • 使用 huffmanTree 生成编码表
  • 使用 huffmanTree 算出 WPL

查找权重最小的结点

生成编码表

路径编码方法:

  • 任一结点到其左子结点编码为 “0”
  • 任一结点到其右子结点编码为”1″

任一叶结点的编码,就是由根到叶结点的路径编码串

树的 WPL

编码

解码

三、小结

要利用好霍夫曼编码,需在生成树结构前,提炼出大部分应用场景中数据结点(字符或是词组之类元数据)的使用频率,以此做为结点的权重,方能最大化使用编码的收益。

打赏作者
您的支持将激励我继续创作!

您的支持将鼓励我们继续创作!

[微信] 扫描二维码打赏

[支付宝] 扫描二维码打赏

Write a Comment

Comment