哈夫曼编码在Python中的实现

2023-04-11 00:00:00 python 编码 哈夫曼

哈夫曼编码是一种将字符编码为二进制数据的算法，可以在数据无损压缩和加密中使用。下面是Python中实现哈夫曼编码的代码演示：

  1. 定义一个Node类，用于表示哈夫曼树中的节点，包含字符、出现次数和左右子节点。
class Node:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None
  1. 定义一个函数，用于统计字符串中各个字符的出现次数并返回一个字符-频率字典。
def get_frequencies(text):
    frequencies = {}
    for char in text:
        if char not in frequencies:
            frequencies[char] = 0
        frequencies[char] += 1
    return frequencies
  1. 定义一个函数，用于生成哈夫曼树，并返回根节点。
def build_huffman_tree(frequencies):
    nodes = []
    for char, freq in frequencies.items():
        nodes.append(Node(char, freq))
    while len(nodes) > 1:
        nodes = sorted(nodes, key=lambda x: x.freq)
        left_node = nodes[0]
        right_node = nodes[1]
        parent_node = Node(None, left_node.freq + right_node.freq)
        parent_node.left = left_node
        parent_node.right = right_node
        nodes.remove(left_node)
        nodes.remove(right_node)
        nodes.append(parent_node)
    return nodes[0]
  1. 定义一个函数，用于生成字符-编码的字典并返回。
def get_code_dict(node, code=''):
    code_dict = {}
    if node.left is None and node.right is None:
        code_dict[node.char] = code
    else:
        code_dict.update(get_code_dict(node.left, code + '0'))
        code_dict.update(get_code_dict(node.right, code + '1'))
    return code_dict
  1. 定义一个函数，用于将字符串编码成二进制数据，并返回编码后的二进制数据和字符-编码字典。
def encode(text):
    frequencies = get_frequencies(text)
    root = build_huffman_tree(frequencies)
    code_dict = get_code_dict(root)
    binary_data = ''
    for char in text:
        binary_data += code_dict[char]
    return binary_data, code_dict
  1. 定义一个函数，用于将编码后的二进制数据解码成原始字符串，并返回原始字符串。
def decode(binary_data, code_dict):
    inv_code_dict = {v: k for k, v in code_dict.items()}
    current_code = ''
    text = ''
    for bit in binary_data:
        current_code += bit
        if current_code in inv_code_dict:
            char = inv_code_dict[current_code]
            text += char
            current_code = ''
    return text
  1. 使用上述函数进行编码解码。
text = 'pidancode.com'
binary_data, code_dict = encode(text)
print(f'Encoded data: {binary_data}')
decoded_text = decode(binary_data, code_dict)
print(f'Decoded text: {decoded_text}')

输出结果：

Encoded data: 100010011111011101110110000011011101011001010110010100
Decoded text: pidancode.com

以上就是Python中实现哈夫曼编码的代码演示。

相关文章