【贪心算法】哈夫曼编码Python实现

哈夫曼编码

• 哈夫曼编码是广泛用于数据文件压缩的十分有效的编码方法，其压缩率通常为$20\%$到$90\%$
• 哈夫曼编码算法使用字符在文件中出现的频率表来建立一个用$0$、$1$串表示各字符的最优表示方式

---

不同编码方式对比

• 假设有一个数据文件包含$100000$个字符，要用压缩的方式存储它，该文件中共有$6$个不同字符出现，各字符出现的频率如下表所示

	$a$	$b$	$c$	$d$	$e$	$f$
频率（千次）	$45$	$13$	$12$	$16$	$9$	$5$

• 有多种方法表示文件中的信息，考察用$0$、$1$码串表示字符的方法，即每个字符用唯一的一个$0$、$1$串表示
• 若使用定长码，则表示$6$个不同的字符需要$3$位：$a=000$，$b=001$，$\cdots$，$f=101$，用这种方法对整个文件进行编码需要$300000$位
• 使用变长码要比使用定长码好得多，给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长，下表给出了一种变长码编码方案，其中$a$用一位串$0$表示，而字符$f$用$4$位串$1100$表示

	$a$	$b$	$c$	$d$	$e$	$f$
变长码	$0$	$101$	$100$	$111$	$1101$	$1100$

• 用这种编码方案，整个文件的总码长为$(45\times 1+13\times 3+12\times 3+16\times 3+9\times 4+5\times 4)\times 1000=224000$位，比用定长码方案好，总码长减小约$25\%$，事实上，这是该文件的最优编码方案

---

前缀码

• 对每一个字符规定一个$0$、$1$串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀，这种编码称为前缀码
• 编码的前缀性质可以使译码方法非常简单，由于任一字符的代码都不是其他字符代码的前缀，从编码文件中不断取出代表某一字符的前缀码，转换为原始字符串，即可逐个译出文件中的所有字符
  • 例如上表中的变长码就是一种前缀码，对于给定的$0$、$1$串$001011101$可以唯一地分解为$0$、$0$、$101$、$1101$，因而其译码为$aabe$
• 译码过程需要方便地取出编码的前缀，因此需要表示前缀码的合适的数据结构，为此可以用二叉树作为前缀编码的数据结构
• 在表示前缀码的二叉树中，树叶代表给定的字符，并将每个字符的前缀码看作从树根到代表该字符的树叶的一条路径
• 定长编码的二叉树表示

• 最优前缀编码的二叉树表示

• 最优前缀码的二叉树总是一棵完全二叉树，即树中任意结点都有$2$个儿子，在一般情况下，若$C$是字符集，表示其最优前缀码的二叉树中恰有$|C|$个叶子，每个叶子对应字符集中的一个字符，该二叉树恰有$|C|-1$个内部结点
• 给定编码字符集$C$及其频率分布$f$，即$C$中任一字符$c$以频率$f(c)$在数据文件中出现，$C$的一个前缀码编码方案对应一棵二叉树$T$，字符$c$在树中的深度记为$d_T(c)$，$d_T(c)$也是字符$c$的前缀码长，该编码方案的平均码长定义为$B(T)=\sum _{c\in C}f(c)d_T(c)$，使平均码长达到最小的前缀码编码方案称为$C$的最优前缀码

---

构造哈夫曼编码

• 哈夫曼提出了构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼算法

• 哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树$T$

• 算法以$|C|$个叶节点开始，执行$|C|-1$次的“合并”运算后产生最终要求的树$T$

• 首先用字符集$C$中每个字符$c$的频率$f(c)$初始化优先队列$Q$，然后不断地从优先队列$Q$中取出具有最小频率的两棵树$x$和$y$（$f(x)\le f(y)$），将它们合并为一棵新树$z$，$z$的频率是$x$和$y$的频率之和，新树$z$以$x$为其左儿子，以$y$为其右儿子，经过$n-1$次的合并后，优先队列中只剩下一棵树，即所要求的树$T$

---

哈夫曼算法的正确性

• 要证明哈夫曼算法的正确性，只要证明最优前缀码问题具有贪心选择性质和最优子结构性质

贪心选择性质

• 设$C$是编码字符集，$C$中字符$c$的频率为$f(c)$，又设$x$和$y$是$C$中具有最小频率的两个字符，则存在$C$的最优前缀码使$x$和$y$具有相同码长且仅最后一位编码不同

证明

• 设二叉树$T$表示$C$的任意一个最优前缀码，下面证明可以对$T$进行适当修改后，得到一棵新的二叉树$T^{{}^{\prime \prime }}$，使得在新树中，$x$和$y$是最深叶子且为兄弟，同时新树$T^{{}^{\prime \prime }}$表示的前缀码也是$C$的最优前缀码，如果能做到，则$x$和$y$在$T^{{}^{\prime \prime }}$表示的最优前缀码中就具有相同的码长且仅最后一位编码不同
• 设$b$和$c$是二叉树$T$的最深叶子且为兄弟，不失一般性，可设$f(b)\le f(c)$，$f(x)\le f(y)$，由于$x$和$y$是$C$中具有最小频率的两个字符，故$f(x)\le f(b)$，$f(y)\le f(c)$
• 首先在树$T$中交换叶子$b$和$x$的位置得到树$T^{{}^{\prime }}$，然后在树$T^{{}^{\prime }}$中再交换叶子$c$和$y$的位置，得到树$T^{{}^{\prime \prime }}$，如下图所示

• 由此可知，树$T$和$T^{{}^{\prime }}$表示的前缀码的平均码长之差为

$$\begin{array}{rl}B(T)-B(T^{{}^{\prime }})& =\sum _{c\in C}f(c)d_T(c)-\sum _{c\in C}f(c)d_{T^{{}^{\prime }}}(c)\\ & =f(x)d_T(x)+f(b)d_T(b)-f(x)d_{T^{{}^{\prime }}}(x)-f(b)d_{T^{{}^{\prime }}}(b)\\ & =f(x)d_T(x)+f(b)d_T(b)-f(x)d_T(b)-f(b)d_T(x)\\ & =(f(b)-f(x))(d_T(b)-d_T(x))\ge 0\end{array}$$

• 类似地，可以证明在$T^{{}^{\prime }}$中交换$y$与$c$的位置也不增加平均码长，即$B(T^{{}^{\prime }})-B(T^{{}^{\prime \prime }})$也是非负的
• 由此可知，$B(T^{{}^{\prime \prime }})\le B(T^{{}^{\prime }})\le B(T)$，另一方面，$T$表示的前缀码是最优的，故$B(T)\le B(T^{{}^{\prime \prime }})$，因此$B(T)=B(T^{{}^{\prime \prime }})$，即$T^{{}^{\prime \prime }}$表示的前缀码也是最优前缀码，且$x$和$y$具有最长的码长，同时仅最后一位编码不同

最优子结构性质

• 设$T$是表示字符集$C$的一个最优前缀码的完全二叉树，$C$中字符$c$的出现频率为$f(c)$，设$x$和$y$是树$T$中的两个叶子且为兄弟，$z$是它们的父亲，若将$z$看作具有频率$f(z)=f(x)+f(y)$的字符，则树 T ′ = T − { x , y } T^{'} = T - \set{x , y} T′=T−{x,y}表示字符集 C ′ = ( C − { x , y } ) ∪ { z } C^{'} = (C - \set{x , y}) \cup \set{z} C′=(C−{x,y})∪{z}的一个最优前缀码

证明

• 首先证明$T$的平均码长$B(T)$可用$T^{{}^{\prime }}$的平均码长$B(T^{{}^{\prime }})$来表示
• 事实上，对任意 c ∈ C − { x , y } c \in C - \set{x , y} c∈C−{x,y}有$d_T(c)=d_{T^{{}^{\prime }}}(c)$，故$f(c)d_T(c)=f(c)d_{T^{{}^{\prime }}}(c)$
• 另一方面，$d_T(x)=d_T(y)=d_{T^{{}^{\prime }}}(z)+1$，故$\begin{array}{rl}f(x)d_T(x)+f(y)d_T(y)& =(f(x)+f(y))(d_{T^{{}^{\prime }}}(z)+1)\\ & =f(x)+f(y)+f(z)d_{T^{{}^{\prime }}}(z)\end{array}$
• 由此可知，$B(T)=B(T^{{}^{\prime }})+f(x)+f(y)$
• 若$T^{{}^{\prime }}$表示的字符集$C^{{}^{\prime }}$的前缀码不是最优的，则有$T^{{}^{\prime \prime }}$表示的$C^{{}^{\prime }}$的前缀码使得$B(T^{{}^{\prime \prime }})<B(T^{{}^{\prime }})$，由于$z$被看作$C^{{}^{\prime }}$中的一个字符，故$z$在$T^{{}^{\prime \prime }}$中是一树叶，若将$x$和$y$加入树$T^{{}^{\prime \prime }}$中作为$z$的儿子，则得到表示字符集$C$的前缀码的二叉树$T^{{}^{\prime \prime \prime }}$，且有$B(T^{{}^{\prime \prime \prime }})=B(T^{{}^{\prime \prime }})+f(x)+f(y)<B(T^{{}^{\prime }})+f(x)+f(y)=B(T)$，这与$T$的最优性矛盾，故$T^{{}^{\prime }}$表示的$C^{{}^{\prime }}$的前缀码是最优的

总结

• 由贪心选择性质和最优子结构性质立即推出哈夫曼算法是正确的，即哈夫曼算法产生$C$的一棵最优前缀编码树

---

Python实现

from heapq import heappop, heappush
from collections import defaultdictclass HuffmanNode:def __init__(self, char, freq, left=None, right=None):self.char = char  # 节点代表的字符self.freq = freq  # 节点对应字符的频率self.left = left  # 左子节点self.right = right  # 右子节点def __lt__(self, other):return self.freq < other.freqdef build_frequency_table(text):frequency_table = defaultdict(int)  # 存储字符频率的字典, 默认值为 0for char in text:frequency_table[char] += 1  # 统计字符频率return frequency_tabledef build_huffman_tree(frequency_table):priority_queue = []  # 存储 Huffman 节点的优先队列(最小堆)for char, freq in frequency_table.items():node = HuffmanNode(char, freq)heappush(priority_queue, node)  # 将每个字符的频率作为优先级, 构建最小堆while len(priority_queue) > 1:left_node = heappop(priority_queue)  # 弹出频率最小的节点作为左子节点right_node = heappop(priority_queue)  # 弹出频率次小的节点作为右子节点parent_freq = left_node.freq + right_node.freq  # 父节点的频率是左右子节点频率之和parent_node = HuffmanNode(None, parent_freq, left_node, right_node)heappush(priority_queue, parent_node)  # 将父节点插入优先队列return heappop(priority_queue)  # 返回最后剩余的根节点def generate_codes(node, current_code, codes):if node.char:codes[node.char] = current_code  # 如果节点代表一个字符, 将字符和对应的编码存入字典else:generate_codes(node.left, current_code + '0', codes)  # 递归生成左子树编码, 将当前编码加上 '0'generate_codes(node.right, current_code + '1', codes)  # 递归生成右子树编码, 将当前编码加上 '1'def huffman_encoding(text):frequency_table = build_frequency_table(text)  # 构建字符频率表huffman_tree = build_huffman_tree(frequency_table)  # 构建 Huffman 树codes = {}  # 存储字符和对应的 Huffman 编码的字典generate_codes(huffman_tree, '', codes)  # 生成 Huffman 编码encoded_text = ''.join(codes[char] for char in text)  # 将文本编码为 Huffman 编码return encoded_text, huffman_treedef huffman_decoding(encoded_text, huffman_tree):decoded_text = ''current_node = huffman_treefor bit in encoded_text:if bit == '0':current_node = current_node.left  # 如果是 '0', 移动到左子节点else:current_node = current_node.right  # 如果是 '1', 移动到右子节点if current_node.char:  # 如果当前节点代表一个字符decoded_text += current_node.char  # 将字符添加到解码文本中current_node = huffman_tree  # 重置当前节点为根节点return decoded_texttext = 'Hello, Huffman!'
print(f'原始文本: {text}')encoded_text, huffman_tree = huffman_encoding(text)
print(f'编码后的文本: {encoded_text}')decoded_text = huffman_decoding(encoded_text, huffman_tree)
print(f'解码后的文本: {decoded_text}')

原始文本: Hello, Huffman!
编码后的文本: 01110100010010100010110110111000111111000110111001001
解码后的文本: Hello, Huffman!

---

时间复杂性

• 算法用最小堆实现优先队列$Q$，初始化优先队列需要$O(n)$计算时间，由于最小堆的删除结点和插入结点运算均需$O(\log n)$时间，$n-1$次的合并共需要$O(n\log n)$计算时间
• 因此，关于$n$个字符的哈夫曼算法的计算时间为$O(n\log n)$

---