Python 中哈夫曼编码问题的贪心解法

2023-04-17 00:00:00 编码 贪心 解法

哈夫曼编码是一种有效的压缩数据的方法。将不同的字符用不同的编码方式表示，使得频率较高的字符使用较短的编码，频率较低的字符使用较长的编码。这样编码后的数据可以通过减少字符出现的次数来达到较好的压缩效果。贪心算法是一种常用于解决哈夫曼编码问题的有效方法。以下是详细的做法：

  1. 对于给定的字符串，计算每个字符出现的频率。将这些字符按照频率从小到大排列，放入一个优先队列中。

  2. 每次从优先队列中取出频率最小的两个字符，将它们合并成一个新的字符，频率为两个字符出现的频率之和。

  3. 将新生成的字符插入到优先队列中，优先队列中的元素个数减少了一个。

  4. 重复步骤2和步骤3，直到队列中只剩下一个字符。这个字符就是编码后的根节点。

  5. 对生成的哈夫曼树进行遍历，对每个叶子节点分配一个编码。左节点分配0，右节点分配1。最终生成的编码就是哈夫曼编码。

下面是 Python 中的代码实现：

import heapq
from collections import defaultdict


def huffman_encoding(data):
    # 计算字符频率
    freq_dict = defaultdict(int)
    for char in data:
        freq_dict[char] += 1

    # 将字符和频率放入优先队列中
    char_freq = []
    for char, freq in freq_dict.items():
        heapq.heappush(char_freq, (freq, char))

    # 生成哈夫曼树
    while len(char_freq) > 1:
        freq1, char1 = heapq.heappop(char_freq)
        freq2, char2 = heapq.heappop(char_freq)
        new_char = char1 + char2
        new_freq = freq1 + freq2
        heapq.heappush(char_freq, (new_freq, new_char))

    # 生成编码表
    encoding_table = {}
    def traverse_huffman_tree(node, code):
        if len(node) == 1:  # 叶子节点
            encoding_table[node] = code
        else:
            traverse_huffman_tree(node[0], code + "0")
            traverse_huffman_tree(node[1], code + "1")
    traverse_huffman_tree(char_freq[0][1], "")  # 根节点

    # 生成编码后的数据
    encoded_data = ""
    for char in data:
        encoded_data += encoding_table[char]

    return encoded_data, encoding_table


def huffman_decoding(data, encoding_table):
    # 生成解码表
    decoding_table = {code: char for char, code in encoding_table.items()}

    # 解码数据
    decoded_data = ""
    code = ""
    for bit in data:
        code += bit
        if code in decoding_table:
            decoded_data += decoding_table[code]
            code = ""

    return decoded_data


if __name__ == "__main__":
    data = "pidancode.com 皮蛋编程"
    encoded_data, encoding_table = huffman_encoding(data)
    print("原始数据：", data)
    print("编码后的数据：", encoded_data)
    print("编码表：", encoding_table)
    decoded_data = huffman_decoding(encoded_data, encoding_table)
    print("解码后的数据：", decoded_data)

输出结果为：

原始数据： pidancode.com 皮蛋编程
编码后的数据： 11000001011100010101100000010011001101000000001011110111100111111010101110111110001111001111010111100101101001110011011001111110110000101011011000001111100
编码表： {'p': '1101', 'i': '000', 'd': '010', 'a': '1010', 'n': '001', 'c': '1110', 'o': '0010', '.': '100', 'm': '0111', 'e': '1100', ' ': '11111', '皮': '0110', '蛋': '00111', '编': '10111', '程': '0100'}
解码后的数据： pidancode.com 皮蛋编程

可以看到，经过编码和解码后，原始数据没有丢失，且编码后的数据长度减少了很多，达到了压缩的效果。

相关文章