Python描述数据结构学习之哈夫曼树篇

Python描述数据结构学习之哈夫曼树篇攻略

简介

本篇攻略旨在介绍哈夫曼树的概念、构建方法和应用场景，并结合Python代码进行演示。

哈夫曼树概念

哈夫曼树（Huffman Tree）又称最优树，它是一种带权路径长度最短的树。所谓带权路径长度，就是每个节点的权值乘以其到根节点的路径长度（即树的层数）之和。哈夫曼树广泛应用于数据压缩领域。

哈夫曼树构建方法

1. 首先将需要编码的字符按照出现的频率从小到大排序，构造出对应的权重序列weights。
2. 创建一个空的森林（即一组树），每个节点独立成树。
3. 依次取出权重序列中的最小值，将其作为左右子节点合并为一棵树，同时删除权重序列中的这两个节点，将新生成的树加入到森林中。
4. 重复步骤三，直到森林中只有一棵树为止，该树就是我们构建的哈夫曼树。

Python代码演示

HuffmanTree类定义

我们首先定义一个HuffmanTree类，用于存储哈夫曼树的节点和相关的操作方法。

class HuffmanTreeNode:  # 哈夫曼树节点类

    def __init__(self, weight, value=None):
        self.weight = weight    # 权值
        self.value = value      # 节点值（仅用于叶子节点）
        self.parent = None      # 父节点
        self.left_child = None  # 左子节点
        self.right_child = None # 右子节点


class HuffmanTree:

    def __init__(self, char_freq):
        self.char_freq = char_freq  # 字符-权值字典
        self.root = None            # 根节点
        self.leaves = []            # 叶子节点列表

    # 构造函数，根据char_freq创建哈夫曼树
    def build_tree(self):
        # 创建叶子节点
        for key, value in self.char_freq.items():
            node = HuffmanTreeNode(value, key)
            self.leaves.append(node)
        # 构建哈夫曼树
        while len(self.leaves) > 1:
            self.leaves.sort(key=lambda node: node.weight)  # 从小到大排序
            left_child = self.leaves.pop(0)                # 取出最小的节点作为左子节点
            right_child = self.leaves.pop(0)               # 取出次小的节点作为右子节点
            # 构建新节点
            weight = left_child.weight + right_child.weight
            parent = HuffmanTreeNode(weight)
            parent.left_child = left_child
            parent.right_child = right_child
            left_child.parent = parent
            right_child.parent = parent
            # 将新节点加入叶子节点列表中
            self.leaves.append(parent)
        self.root = self.leaves[0]    # 根节点为叶子节点列表中最后一个节点

调用HuffmanTree类

char_freq = {'a': 5, 'b': 4, 'c': 3, 'd': 2, 'e': 1}  # 构造字符-权值字典
tree = HuffmanTree(char_freq)   # 构建哈夫曼树
tree.build_tree()               # 构建过程

应用场景

哈夫曼树广泛应用于数据压缩领域。在压缩一个文件时，我们可使用哈夫曼编码将其中的字符表示为二进制码，并用更少的位数表示出出现概率较大的字符，用更多的位数表示出现概率较小的字符，从而达到压缩的效果。

示例演示

示例一：字符编码

为了将一个文件压缩，我们需要将其中的字符转换为哈夫曼编码（即二进制码）。下面是一个简单的示例：

mapping = tree.get_mapping()   # 获取字符-编码的映射

with open('test.txt', 'r') as f:
    text = f.read()
    encoded_text = ''
    for char in text:
        encoded_text += mapping[char]

在上述代码中，我们首先调用tree.get_mapping()方法获取字符-编码的映射，然后读取文件的每个字符，用相应的哈夫曼编码替换它，得到压缩后的字符串。

示例二：文件解码

压缩一个文件后，我们需要将其解压回原始文件。下面是一个简单的示例：

mapping = tree.get_mapping()   # 获取字符-编码的映射
reverse_mapping = dict([(value, key) for key, value in mapping.items()])

with open('compressed.bin', 'rb') as f:
    bit_string = ''
    byte = f.read(1)
    while byte != b'':
        byte = ord(byte)
        bits = bin(byte)[2:].rjust(8, '0')
        bit_string += bits
        byte = f.read(1)

current_code = ''
decompressed_text = ''
for bit in bit_string:
    current_code += bit
    if current_code in reverse_mapping:
        char = reverse_mapping[current_code]
        decompressed_text += char
        current_code = ''

print(decompressed_text)

在上述代码中，我们首先调用tree.get_mapping()方法获取字符-编码的映射，并创建一个相反的映射，即编码-字符的映射，用于解码。接着读取压缩后的二进制文件，将其每8个位分为一组，转换为一个字节，然后将每个字节转换为哈夫曼编码，读取完成后，我们依次从二进制字符串中取出位，拼接成编码，查询出对应的字符，并将其添加到解压后的字符串中。最终我们得到原始文件的字符串。