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

文章目录

• • @[toc]
  • • 个人主页：[丷从心](https://blog.csdn.net/from__2023_11_28?type=blog)
    • 系列专栏：[贪心算法](https://blog.csdn.net/from__2023_11_28/category_12531823.html?spm=1001.2014.3001.5482)
    • 哈夫曼编码
    • 不同编码方式对比
    • 前缀码
    • 构造哈夫曼编码
    • 时间复杂性
    • `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$，$?$，$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$

---

时间复杂性

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

---

Python实现

from heapq import heappop, heappush
from collections import defaultdict


class 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.freq


def build_frequency_table(text):
    frequency_table = defaultdict(int)  # 存储字符频率的字典, 默认值为 0

    for char in text:
        frequency_table[char] += 1  # 统计字符频率

    return frequency_table


def 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_tree


def huffman_decoding(encoded_text, huffman_tree):
    decoded_text = ''
    current_node = huffman_tree

    for 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_text


text = "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!

---