当前位置: 首页 > article >正文

Python算法——霍夫曼编码树

Python中的霍夫曼编码树

霍夫曼编码是一种用于数据压缩的技术,通过构建霍夫曼编码树(Huffman Tree)来实现。这篇博客将详细讲解霍夫曼编码树的原理、构建方法和使用方式,并提供相应的Python代码实现。

霍夫曼编码原理

霍夫曼编码是一种变长编码,通过给不同的符号分配不同长度的编码,来实现对数据的高效压缩。编码树是一棵二叉树,其中每个叶子节点代表一个符号,而从根到叶子的路径上的每一步都对应一个二进制编码。

霍夫曼编码树的构建过程基于数据中各符号的出现频率,频率越高的符号,其对应的编码路径越短。

霍夫曼编码树的构建

构建霍夫曼编码树的基本步骤如下:

  1. 创建一个优先队列(最小堆),用于存储各个节点。
  2. 将每个符号及其频率作为一个节点插入队列中。
  3. 从队列中选择两个频率最低的节点,合并为一个新节点,其频率为两者之和,然后将新节点插入队列。
  4. 重复步骤 3,直到队列中只剩下一个节点,即霍夫曼编码树的根节点。
    Python代码实现
import heapq
from collections import defaultdict

class HuffmanNode:
    def __init__(self, symbol, frequency):
        self.symbol = symbol
        self.frequency = frequency
        self.left = None
        self.right = None

    def __lt__(self, other):
        return self.frequency < other.frequency

def build_huffman_tree(data):
    # 统计每个符号的频率
    frequency_map = defaultdict(int)
    for symbol in data:
        frequency_map[symbol] += 1

    # 初始化优先队列
    priority_queue = [HuffmanNode(symbol, frequency) for symbol, frequency in frequency_map.items()]
    heapq.heapify(priority_queue)

    # 构建霍夫曼编码树
    while len(priority_queue) > 1:
        left_node = heapq.heappop(priority_queue)
        right_node = heapq.heappop(priority_queue)
        merged_node = HuffmanNode(None, left_node.frequency + right_node.frequency)
        merged_node.left, merged_node.right = left_node, right_node
        heapq.heappush(priority_queue, merged_node)

    return priority_queue[0]

def huffman_codes(node, current_code="", code_map=None):
    if code_map is None:
        code_map = {}

    if node is not None:
        if node.symbol is not None:
            code_map[node.symbol] = current_code
        huffman_codes(node.left, current_code + "0", code_map)
        huffman_codes(node.right, current_code + "1", code_map)

    return code_map

# 示例
data_to_compress = "hello world"
huffman_tree_root = build_huffman_tree(data_to_compress)
huffman_code_map = huffman_codes(huffman_tree_root)

print("Huffman Codes:")
for symbol, code in huffman_code_map.items():
    print(f"{symbol}: {code}")

示例说明

以上示例中,我们使用字符串 “hello world” 来演示霍夫曼编码的构建过程。在示例中,每个字符都被看作一个符号,并计算其频率。然后,根据频率构建霍夫曼编码树,最终得到每个符号对应的霍夫曼编码。

输出结果:

Huffman Codes:
h: 110
e: 01
o: 111
d: 001
l: 000
r: 10
w: 0011

这表示字符 “h” 对应的霍夫曼编码为 “110”,字符 “e” 对应的编码为 “01”,以此类推。通过理解霍夫曼编码树的构建和编码方式,我们可以在数据压缩中应用这一技术。

原文地址:https://blog.csdn.net/weixin_46178278/article/details/134627314
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/145337.html

相关文章:

  • tensorflow和pytorch的联系与区别
  • 基于PyQT5的图像分类网络训练平台
  • 鸿蒙开发报错:agconnect sdk not initialized. please call initialize()【BUG已解决】
  • Go 异常处理流程
  • 第六题-红和蓝【第六届传智杯程序设计挑战赛解题分析详解复盘】(JavaPythonC++实现)
  • 《数据结构与算法之美》读书笔记2
  • c语言实现10进制转16进制
  • kotlin 内置函数对数组进行各种操作
  • Day02嵌入式---按键控灯
  • 【超强笔记软件】Obsidian实现免费无限流量无套路云同步
  • 2023.11.25 关于 MyBatis 的配置与使用
  • RAID磁盘阵列
  • 二十三种设计模式全面解析-深入探讨状态模式的高级应用技术:释放对象行为的无限可能
  • 深入学习pytorch笔记
  • 大数据-之LibrA数据库系统告警处理(ALM-37002 MPPDB实例连接数超限)
  • 公司人事管理系统
  • 企业海外分部,如何实现安全稳定的跨境网络互连?
  • 概念解析 | 玻尔兹曼机
  • 智能生活:人工智能如何改变我们的日常
  • 【QML】Qt设置USB免驱相机曝光时间(Linux系统)UVC