霍夫曼编码是一种根据字符频率对字符进行编码的方法。每个字母都被分配了一个可变长度的二进制字符串,例如0101或111110,其中较短的长度对应于更常见的字母。为了实现这一点,构建了一个二叉树,使从根到任何叶子的路径唯一地映射到一个字符。遍历路径时,向左子级递减对应于前缀中的0,而向右递减对应于1。
下面是一个示例树(注意,只有叶节点有字母(:
*
/
* *
/ /
* a t *
/
c s
通过这种编码,猫将被表示为0000110111。
给定一个字符频率字典,构建一个霍夫曼树,并使用它来确定字符及其编码二进制字符串之间的映射。
构建Huffman树的步骤
输入是一组独特的字符及其出现频率,输出是霍夫曼树。
为每个唯一字符创建一个叶节点,并构建所有叶节点的最小堆(最小堆用作优先级队列频率字段用于比较最小堆中的两个节点。开始最不频繁的字符在根(
从最小堆中提取两个频率最小的节点。
创建一个频率等于两个节点频率之和的新内部节点。将第一个提取的节点作为其左子节点并且另一个提取的节点作为其右子节点。将此节点添加到最小堆。
重复步骤#2和#3,直到堆只包含一个节点。剩下的节点是根节点,树是完整的。
霍夫曼树构建过程及示例
请看本教程,这里描述了逐步构建树的过程。。