文章目录
  1. 1. Huffman
    1. 1.1. Huffman 树
    2. 1.2. Huffman 树的构造
    3. 1.3. Huffman 编码
    4. 1.4. 参考

Huffman

Huffman 树

树是一种非常重要的非线性结构,它是数据元素(在树中称为结点)按该分支关系组织起来的结构。若干颗互不相交的树所构成的集合成为森林。

  • 路径和路径长度:在一棵树中,从一个结点往下可以到达的孩子或孙子结点之间的通路,成为路径。通路中分支数目称为路径长度。若规定根结点的层号为 ${1}$,则从根结点到第 ${L}$ 层结点的路径长度为 ${L-1}$。
  • 结点的权和带权路径长度:若为树中结点赋予一个具体含有某种意义的(非负)数值,则这个数值成为该结点的权,结点的带权路径长度是指,从根结点到该结点之间的路径长度与该结点的权的乘积。
  • 树的带权路径长度:树的带权路径长度规定为所有叶子结点的带权路径长度之和。

二叉树 是每个结点最多有两个子树的有序树。两个子树通常被称为 左子树右子树,定义中的 有序 是指两个子树有左右之分,顺序不能颠倒。

给定 ${n}$ 个权值作为 ${n}$ 个子结点,构造一棵二叉树,若它的带权路径长度达到最小,则称这样的二叉树为 最优二叉树,也称为 Huffman 树

Huffman 树的构造

词频越大的词离根结点越近。

  1. 将 ${\{w_1, w_2, \cdots, w_n\}}$ 看成是有 ${n}$ 棵树的森林,其中每棵树仅有一个结点。
  2. 在森林中,选出两个根结点的权值最小的的树合并,作为一棵新树的左、右子树,且新树的根结点为其左、右子树根结点权值之和。
  3. 从森林中删除选取的两棵树,并将新树加入森林。
  4. 重复第 2、3 步,直到森林中只剩一棵树为止,该树即为所求的 Huffman 树。

若叶结点的个数为 ${n}$,则构造的 Huffman 树中新增结点的个数为 ${n-1}$。通常有一个 约定,在合并树的过程中,统一将词频交大的作为左子结点,词频较小的作为右子结点。由于第 2 步中,每次需要选择权值最小的连个结点,可以通过构建一个 最小堆 来维护/优化。

若叶子结点的个数为 ${n}$,则构造的 Huffman 树中新增结点的个数为 ${n-1}$,总的结点个数为 ${2n -1}$。

Huffman 编码

在数据通信的过程中,通常的编码方式有两种:等长编码不等长编码,如果有些字符出现的频次非常高,而有些字符出现的频次非常低,那么对于高频词,使用较短的编码,对于低频词,使用较长的编码,来优化整段数据。

不等长编码为前缀编码,即要求一个字符的编码不能是另一个字符编码的前缀,Huffman 二叉树有效地解决了这个问题,频次越高的结点(词)离根节点越近,左子树用 ${0}$ 编码,右子树用 ${1}$ 编码,那么从根节点到叶子结点,所得到的编码序列,就是这个词的 huffman 编码。

对于平均编码长度,计算方式为编码长度的期望:

参考

  1. Word2Vec中的数学原理详解
  2. 哈夫曼(huffman)树和哈夫曼编码
文章目录
  1. 1. Huffman
    1. 1.1. Huffman 树
    2. 1.2. Huffman 树的构造
    3. 1.3. Huffman 编码
    4. 1.4. 参考