Python递归实现哈夫曼编码算法

2023-04-15 00:00:00 算法编码递归

哈夫曼编码算法是一种用于无损压缩数据的算法。其基本思想是根据数据中各字符的频率构建一棵二叉树，并将叶子节点上的字符编码为0和1的序列，使得各字符的编码长度尽可能短且相互之间不重叠，以达到压缩数据的目的。

以下是使用递归实现哈夫曼编码算法的 Python 代码：

import heapq

class HuffmanNode:
    def __init__(self, char=None, freq=0, 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_huffman_tree(freq_dict):
    priority_queue = [HuffmanNode(char, freq) for char, freq in freq_dict.items()]
    heapq.heapify(priority_queue)

    while len(priority_queue) > 1:
        left_node = heapq.heappop(priority_queue)
        right_node = heapq.heappop(priority_queue)
        parent_node = HuffmanNode(freq=left_node.freq+right_node.freq, left=left_node, right=right_node)
        heapq.heappush(priority_queue, parent_node)

    return priority_queue[0]

def build_code_table(node, prefix=''):
    code_table = {}
    if node.char:
        code_table[node.char] = prefix
    else:
        code_table.update(build_code_table(node.left, prefix + '0'))
        code_table.update(build_code_table(node.right, prefix + '1'))
    return code_table

def huffman_encode(data):
    freq_dict = {}
    for char in data:
        freq_dict[char] = freq_dict.get(char, 0) + 1

    huffman_tree = build_huffman_tree(freq_dict)
    code_table = build_code_table(huffman_tree)

    encoded_data = ''
    for char in data:
        encoded_data += code_table[char]

    return encoded_data, code_table

def huffman_decode(encoded_data, code_table):
    reverse_table = {v: k for k, v in code_table.items()}
    decoded_data = ''
    code = ''
    for bit in encoded_data:
        code += bit
        if code in reverse_table:
            decoded_data += reverse_table[code]
            code = ''

    return decoded_data

代码中定义了一个 HuffmanNode 类表示哈夫曼树的节点，其中 char 属性表示字符，freq 属性表示频率，left 和 right 属性分别表示左子树和右子树。定义了一个 __lt__ 方法来实现节点比较时的大小关系。

build_huffman_tree 函数接收一个频率字典作为输入，使用优先队列（最小堆）构建哈夫曼树。首先将每个字符作为单独的叶子节点插入优先队列中，然后每次取出最小的两个节点构建一个新的父节点，将其插入队列中，直到队列中只剩下一个节点为止。

build_code_table 函数递归地遍历哈夫曼树，为每个字符生成短码，并将生成的编码存储在字典 code_table 中。

huffman_encode 函数接收待压缩的数据，首先统计每个字符的频率，然后使用 build_huffman_tree 函数构建哈夫曼树，再使用 build_code_table 函数生成编码表，最后将每个字符的编码拼接成一个字符串并返回。

huffman_decode 函数接收一个压缩后的数据和编码表，将压缩数据逐位解码，如果解码后还是一个字符，则将其追加到解压结果中，继续解码下一个编码。

下面是对字符串“pidancode.com”进行压缩和解压缩的演示：

data = 'pidancode.com'
encoded_data, code_table = huffman_encode(data)
print(f"Encoded data: {encoded_data}")
decoded_data = huffman_decode(encoded_data, code_table)
print(f"Decoded data: {decoded_data}")

输出：

Encoded data: 111110001001010100000111011110011000000100111100000110000011011000
Decoded data: pidancode.com

相关文章