什么是哈夫曼树？哈夫曼编码的实现-js教程-PHP中文网

什么是哈夫曼树？哈夫曼编码的实现

幻夢星雲

发布： 2025-08-19 13:06:02

原创

1135人浏览过

哈夫曼编码是一种基于字符出现频率的变长编码方式，通过构建带权路径长度最小的哈夫曼树实现数据压缩，其中频率高的字符被分配短编码，频率低的字符被分配长编码，从而有效减少数据存储或传输的位数，其核心实现包括使用优先队列构建哈夫曼树和从树根递归生成编码，python中可通过heapq模块高效完成节点的选取与合并，最终生成最优前缀编码，该方法广泛应用于文件压缩、图像编码、网络传输和数据存储等领域，具有压缩效率高、实现简单等优点，但也存在需预先统计频率、对均匀分布数据压缩效果差以及编码静态不易动态调整等局限性，总体上体现了信息论中概率与编码长度反比关系的经典思想，是一种至今仍被广泛使用的无损压缩技术。

什么是哈夫曼树？哈夫曼编码的实现

哈夫曼树是一种特殊的二叉树，它的每个叶子节点都带有一个权值，而树的带权路径长度（即所有叶子节点的权值乘以其到根节点的路径长度之和）达到最小。哈夫曼编码利用哈夫曼树的特性，为出现频率不同的字符分配不同长度的编码，频率高的字符编码短，频率低的字符编码长，从而达到数据压缩的目的。

哈夫曼编码的实现

哈夫曼编码的实现主要分为两步：构建哈夫曼树和生成哈夫曼编码。

构建哈夫曼树
- 首先，将每个字符及其出现的频率视为一个独立的节点，构成一个森林。
- 然后，从森林中选取两个权值最小的节点，合并成一个新的节点，新节点的权值为这两个节点权值之和。将新节点作为这两个节点的父节点，并将这两个节点从森林中移除，将新节点加入森林。
- 重复上述步骤，直到森林中只剩下一个节点，这个节点就是哈夫曼树的根节点。
生成哈夫曼编码

文心快码
文心快码（Comate）是百度推出的一款AI辅助编程工具

35

查看详情
- 从哈夫曼树的根节点开始，向左的路径标记为0，向右的路径标记为1。
- 每个叶子节点的哈夫曼编码就是从根节点到该叶子节点的路径上的0和1的序列。

如何用Python实现哈夫曼编码？

Python实现哈夫曼编码的关键在于优先队列的使用，它可以高效地找到权值最小的两个节点。

import heapq

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

    def __lt__(self, other): # 用于优先队列的比较
        return self.freq < other.freq

def build_huffman_tree(frequencies):
    """构建哈夫曼树"""
    heap = [Node(char, freq) for char, freq in frequencies.items()]
    heapq.heapify(heap) # 将列表转换为堆

    while len(heap) > 1:
        node1 = heapq.heappop(heap)
        node2 = heapq.heappop(heap)

        merged_node = Node(None, node1.freq + node2.freq)
        merged_node.left = node1
        merged_node.right = node2

        heapq.heappush(heap, merged_node)

    return heapq.heappop(heap) # 返回根节点

def generate_huffman_codes(node, code="", huffman_codes={}):
    """生成哈夫曼编码"""
    if node.char:
        huffman_codes[node.char] = code
        return

    generate_huffman_codes(node.left, code + "0", huffman_codes)
    generate_huffman_codes(node.right, code + "1", huffman_codes)

    return huffman_codes

def huffman_encoding(text):
    """哈夫曼编码主函数"""
    frequencies = {}
    for char in text:
        frequencies[char] = frequencies.get(char, 0) + 1

    huffman_tree = build_huffman_tree(frequencies)
    huffman_codes = generate_huffman_codes(huffman_tree)

    encoded_text = "".join([huffman_codes[char] for char in text])
    return encoded_text, huffman_codes

# 示例
text = "hello world"
encoded_text, huffman_codes = huffman_encoding(text)
print("Encoded text:", encoded_text)
print("Huffman codes:", huffman_codes)

登录后复制