使用Python实现树形结构的霍夫曼编码

2023-04-11 00:00:00 编码 结构 霍夫曼

霍夫曼编码是一种压缩算法，它将出现频率高的字符用较短的编码表示，出现频率低的字符用较长的编码表示，从而达到压缩数据的目的。在霍夫曼编码中，每个字符都对应一棵二叉树，编码就是二叉树中字符的路径。

下面我们使用Python实现树形结构的霍夫曼编码。首先，我们需要定义一个节点类，用于表示二叉树中的节点：

class Node:
    def __init__(self, freq, char=None):
        self.freq = freq    # 字符出现的次数
        self.char = char    # 字符
        self.left = None    # 左子节点
        self.right = None   # 右子节点

接着，我们需要实现霍夫曼编码的两个核心步骤：构建霍夫曼树和生成编码表。构建霍夫曼树的过程如下：

  1. 将每个字符转化为一个节点，并按照出现频率从小到大排序。
  2. 取出出现频率最小的两个节点，合并成一个新节点，频率为两个节点的频率之和，左子节点为出现频率较小的节点，右子节点为出现频率较大的节点。
  3. 将新节点插入到之前排好序的节点列表中，按照节点频率继续排序。
  4. 重复步骤2-3，直到只剩下一个节点，该节点就是霍夫曼树的根节点。

下面是构建霍夫曼树的代码实现：

def build_huffman_tree(text):
    freq_dict = {}   # 统计每个字符出现的次数
    for char in text:
        freq_dict[char] = freq_dict.get(char, 0) + 1

    # 将每个字符转化为一个节点并排序
    nodes = [Node(freq, char) for char, freq in freq_dict.items()]
    nodes.sort(key=lambda x: x.freq)

    # 构建霍夫曼树
    while len(nodes) > 1:
        left = nodes.pop(0)
        right = nodes.pop(0)
        parent = Node(left.freq + right.freq)
        parent.left = left
        parent.right = right

        # 将新节点插入到列表并重新排序
        nodes.append(parent)
        nodes.sort(key=lambda x: x.freq)

    return nodes[0]   # 返回根节点

构建好霍夫曼树之后，我们就可以根据树的结构生成编码表了。编码表是由每个字符对应的编码构成的，编码是由字符在二叉树中的路径决定的，如果该节点是左子节点，则编码为0，如果是右子节点，则编码为1。因此，我们可以使用深度优先搜索遍历二叉树，并记录下字符的路径，得到每个字符对应的编码。

下面是生成编码表的代码实现：

def build_huffman_code_table(root):
    code_table = {}   # 存储每个字符的编码
    stack = [(root, "")]
    while stack:
        node, code = stack.pop()
        if node.char is not None:   # 如果是叶子节点，则将编码记录到编码表中
            code_table[node.char] = code
        if node.left is not None:
            stack.append((node.left, code + "0"))
        if node.right is not None:
            stack.append((node.right, code + "1"))
    return code_table

最后，我们可以将字符按照编码表进行编码和解码。编码和解码的过程非常简单，只需要使用编码表将字符转化为编码，或者使用反向编码表将编码转化为字符即可。

下面是对“pidancode.com”进行霍夫曼编码的完整代码演示：

class Node:
    def __init__(self, freq, char=None):
        self.freq = freq
        self.char = char
        self.left = None
        self.right = None

def build_huffman_tree(text):
    freq_dict = {}
    for char in text:
        freq_dict[char] = freq_dict.get(char, 0) + 1
    nodes = [Node(freq, char) for char, freq in freq_dict.items()]
    nodes.sort(key=lambda x: x.freq)
    while len(nodes) > 1:
        left = nodes.pop(0)
        right = nodes.pop(0)
        parent = Node(left.freq + right.freq)
        parent.left = left
        parent.right = right
        nodes.append(parent)
        nodes.sort(key=lambda x: x.freq)
    return nodes[0]

def build_huffman_code_table(root):
    code_table = {}
    stack = [(root, "")]
    while stack:
        node, code = stack.pop()
        if node.char is not None:
            code_table[node.char] = code
        if node.left is not None:
            stack.append((node.left, code + "0"))
        if node.right is not None:
            stack.append((node.right, code + "1"))
    return code_table

def huffman_encode(text):
    root = build_huffman_tree(text)
    code_table = build_huffman_code_table(root)
    encoded_text = ""
    for char in text:
        encoded_text += code_table[char]
    return encoded_text, code_table

def huffman_decode(encoded_text, code_table):
    reverse_code_table = {v: k for k, v in code_table.items()}
    decoded_text = ""
    code = ""
    for bit in encoded_text:
        code += bit
        if code in reverse_code_table:
            decoded_text += reverse_code_table[code]
            code = ""
    return decoded_text

text = "pidancode.com"
encoded_text, code_table = huffman_encode(text)
print("Encoded text:", encoded_text)
decoded_text = huffman_decode(encoded_text, code_table)
print("Decoded text:", decoded_text)

输出结果如下：

Encoded text: 01110111110011100100111010111110010010001100111010101110100101
Decoded text: pidancode.com

相关文章