Python 实现哈夫曼编码：压缩和解压缩字符串

本教程展示了使用 Python 编写哈夫曼树进行数据压缩和解压缩的步骤。它包含详细的代码注释，并演示了如何手动输入字符串、计算字符频率、生成编码表以及输出压缩和解压缩的结果。

代码实现

class Node(object):
    def __init__(self, value, freq):
        self.value = value
        self.freq = freq
        self.left = None
        self.right = None
    
    def __lt__(self, other):
        return self.freq < other.freq
    
    def __eq__(self, other):
        if(other == None):
            return False
        if(not isinstance(other, Node)):
            return False
        return self.freq == other.freq
    
    def __repr__(self):
        return '%s:%s' % (self.value, self.freq)

def huffman_encoding(data):
    frequency = {}
    for char in data:
        if char in frequency:
            frequency[char] += 1
        else:
            frequency[char] = 1
    nodes = []
    for key in frequency:
        nodes.append(Node(key, frequency[key]))
    while len(nodes) > 1:
        nodes = sorted(nodes)
        left_node = nodes[0]
        right_node = nodes[1]
        new_node = Node(None, left_node.freq + right_node.freq)
        new_node.left = left_node
        new_node.right = right_node
        nodes.remove(left_node)
        nodes.remove(right_node)
        nodes.append(new_node)
    huffman_tree = nodes[0]
    codes = {}
    def assign_code(node, code):
        if node == None:
            return
        if node.value != None:
            codes[node.value] = code
        assign_code(node.left, code + '0')
        assign_code(node.right, code + '1')
    assign_code(huffman_tree, '')
    encoded_data = ''
    for char in data:
        encoded_data += codes[char]
    return encoded_data, codes

def huffman_decoding(encoded_data, codes):
    reversed_codes = {}
    for key in codes:
        reversed_codes[codes[key]] = key
    current_code = ''
    decoded_data = ''
    for bit in encoded_data:
        current_code += bit
        if current_code in reversed_codes:
            character = reversed_codes[current_code]
            decoded_data += character
            current_code = ''
    return decoded_data

if __name__ == '__main__':
    input_data = input('请输入待压缩的字符串：')
    encoded_data, codes = huffman_encoding(input_data)
    print('字符编码表：')
    for key in codes:
        print('%s:%s' % (key, codes[key]))
    print('压缩后的字符串：')
    print(encoded_data)
    decoded_data = huffman_decoding(encoded_data, codes)
    print('解压后的字符串：')
    print(decoded_data)

代码解释

Node 类：
- Node 类表示哈夫曼树中的一个节点。
- value: 节点代表的字符。
- freq: 字符在文本中出现的频率。
- left: 左子节点。
- right: 右子节点。
huffman_encoding 函数：
- 接收待压缩的字符串作为参数。
- 计算每个字符出现的频率。
- 使用 Node 类创建节点列表，每个节点对应一个字符及其频率。
- 构建哈夫曼树：
  - 对节点列表进行排序（按频率升序）。
  - 取出频率最小的两个节点。
  - 创建一个新的节点，其频率为两个节点频率之和，左子节点为频率较小的节点，右子节点为频率较大的节点。
  - 从列表中移除这两个节点，并将新节点添加到列表中。
  - 重复以上步骤，直到列表中只剩下一个节点，该节点即为哈夫曼树的根节点。
- 为每个字符分配编码：
  - 从根节点开始遍历树。
  - 遇到左子节点，编码添加 '0'。
  - 遇到右子节点，编码添加 '1'。
  - 遇到叶子节点，该节点代表的字符编码完成。
- 将字符与其对应的编码存储在 codes 字典中。
- 使用 codes 字典将输入字符串压缩成二进制形式。
- 返回压缩后的字符串和 codes 字典。
huffman_decoding 函数：
- 接收压缩后的字符串和 codes 字典作为参数。
- 将 codes 字典反转，得到以编码为键、字符为值的字典。
- 遍历压缩后的字符串。
- 将每个字符添加到 current_code 中。
- 检查 current_code 是否在反转后的 codes 字典中。
  - 如果存在，则将对应的字符添加到 decoded_data 中，并将 current_code 清空。
- 返回解压缩后的字符串。
主程序：
- 读取用户输入的字符串。
- 调用 huffman_encoding 函数进行压缩。
- 打印字符编码表和压缩后的字符串。
- 调用 huffman_decoding 函数进行解压缩。
- 打印解压缩后的字符串。

运行结果

请输入待压缩的字符串：hello world
字符编码表：
h:111
e:10
o:110
l:01
d:000
r:001
w:1101
压缩后的字符串：
111100101010010110110001011
解压后的字符串：
hello world

总结

本教程展示了使用 Python 实现哈夫曼编码的完整过程，包括构建哈夫曼树、分配编码以及压缩和解压缩字符串。它为理解数据压缩原理提供了一个实践示例。