• 哈夫曼树、哈夫曼编码/解码

    哈夫曼树

    哈夫曼树的基本介绍

    哈夫曼树构建步骤图解

    创建哈夫曼树代码实现

    1. """ 创建哈夫曼树 """
    2. class EleNode:
    3.     """ 节点类 """
    4.     def __init__(self, value: int):
    5.         self.value = value
    6.         self.left = None  # 指向左子节点
    7.         self.right = None  # 指向右子节点
    8.  
    9.     def __str__(self):
    10.         return f"Node [value={self.value}]"
    11.  
    12.     def pre_order(self):
    13.         """前序遍历二叉树"""
    14.         if self is None:
    15.             return
    16.         # 先输出父节点
    17.         print(self, end=' => ')
    18.         # 左子树不为空则递归左子树
    19.         if self.left is not None:
    20.             self.left.pre_order()
    21.         # 右子树不为空则递归右子树
    22.         if self.right is not None:
    23.             self.right.pre_order()
    24.  
    25.  
    26. class HuffmanTree:
    27.     arr: list = None
    28.  
    29.     def __init__(self, arr):
    30.         self.arr = arr
    31.  
    32.     def create_huffman_tree(self) -> EleNode:
    33.         # 对 arr 列表进行升序排序
    34.         self.arr.sort()
    35.         # 遍历数组，将每个数组元素构建成一个 Node 节点
    36.         # 将 Node 节点加入到一个新列表中
    37.         node_list = []
    38.         for i in self.arr:
    39.             node_list.append(EleNode(i))
    40.  
    41.         # 循环进行以下步骤，直到列表中只剩下一棵二叉树，此时该二叉树就是哈夫曼树
    42.         while len(node_list) > 1:
    43.             # 取出权值序列中最小的两课二叉树（即列表中的前两个元素）构建一棵新的二叉树
    44.             left = node_list.pop(0)
    45.             right = node_list.pop(0)
    46.             # 新二叉树的根节点的权值=两个节点权值之和
    47.             parent = EleNode(left.value + right.value)
    48.             # 让新二叉树的左右节点分别指向两个最小的节点
    49.             parent.left = left
    50.             parent.right = right
    51.             # 将新二叉树根据根节点的大小插入到序列中的指定位置
    52.             i = 0
    53.             n = len(node_list)
    54.             while i < n:
    55.                 if node_list[i].value >= parent.value:
    56.                     node_list.insert(i, parent)  # 找到了根节点存放的位置
    57.                     break
    58.                 i += 1
    59.             else:
    60.                 # 循环结束表示新的二叉树的权值最大，在node_list列表中没有比它大的
    61.                 # 所以添加到列表最后
    62.                 node_list.append(parent)
    63.  
    64.         # 此时列表中只有一棵二叉树，即所求的哈夫曼树
    65.         # 返回哈夫曼树的根结点
    66.         return node_list[0]
    67.  
    68.  
    69. huffman = HuffmanTree([13, 7, 8, 3, 29, 6, 1])
    70. node = huffman.create_huffman_tree()
    71. node.pre_order()

    哈夫曼编码

    基本介绍

    哈夫曼编码原理剖析

    哈夫曼编码的实例

    思路分析

    代码实现

    1. """ 哈夫曼编码 """
    2. class CodeNode:
    3.     def __init__(self, data: int, weight: int):
    4.         self.data = data  # 存放字符对应的ASCII码值
    5.         self.weight = weight  # 存放字符在字符串中出现的次数
    6.         self.left = None
    7.         self.right = None
    8.  
    9.     def __str__(self):
    10.         return f"Node[data={chr(self.data) if self.data else None}, weight={self.weight}]"
    11.  
    12.     def pre_order(self):
    13.         """二叉树的前序遍历"""
    14.         print(self)
    15.         if self.left:
    16.             self.left.pre_order()
    17.         if self.right:
    18.             self.right.pre_order()
    19.  
    20.  
    21. class HuffmanCode:
    22.     # 哈夫曼编码表
    23.     # 存储每个字符对应的编码
    24.     # key为对应的字符，val为字符对应的编码
    25.     huffman_code_tab = {}
    26.     # 记录哈夫曼二进制编码字符串最后一个段的长度
    27.     # 即会将哈夫曼二进制字符串按八位进行分割，分割到最后一个时长度可不为8
    28.     # 所以用一个变量存储最后一段二进制字符串的长度，在解码的时候会用到
    29.     last_char_len = 0
    30.  
    31.     def create_huffman_tree(self, s: str) -> CodeNode:
    32.         """
    33.         构建哈夫曼编码二叉树
    34.         :param s: 要编码的字符串
    35.         :return:
    36.         """
    37.         # 遍历字符串，统计每一个字符出现的次数，并将结果放入字典
    38.         kw = {}
    39.         for ch in s:
    40.             ascii_code = ord(ch)
    41.             if kw.get(ascii_code):  # 如果该字符出现过，则直接将其次数加1
    42.                 kw[ascii_code] += 1
    43.             else:  # 如果没出现过，则出现次数为1
    44.                 kw[ascii_code] = 1
    45.  
    46.         # 按照字符出现的次数对字典进行排序
    47.         kw = sorted(kw.items(), key=lambda kv: (kv[1], kv[0]))
    48.         # 遍历字典，将每个元素构建成一个 Node 节点
    49.         # 将 Node 节点加入到一个新列表中
    50.         node_list = []
    51.         for k, v in kw:
    52.             # print(chr(k),'=', v, end=', ')
    53.             node_list.append(CodeNode(k, v))
    54.  
    55.         # 循环进行以下步骤，直到列表中只剩下一棵二叉树，此时该二叉树就是哈夫曼树
    56.         while len(node_list) > 1:
    57.             # 取出权值序列中最小的两课二叉树（即列表中的前两个元素）构建一棵新的二叉树
    58.             left = node_list.pop(0)
    59.             right = node_list.pop(0)
    60.             # 新二叉树的根节点的权值=两个节点权值之和
    61.             parent = CodeNode(None, left.weight + right.weight)
    62.             # 让新二叉树的左右节点分别指向两个最小的节点
    63.             parent.left = left
    64.             parent.right = right
    65.             # 将新二叉树根据根节点的大小插入到序列中的指定位置
    66.             n = len(node_list)
    67.             i = 0
    68.             while i < n:
    69.                 if node_list[i].weight >= parent.weight:
    70.                     node_list.insert(i, parent)  # 找到了根节点存放的位置
    71.                     break
    72.                 i += 1
    73.             else:
    74.                 # 循环结束表示新的二叉树的权值最大，在node_list列表中没有比它大的
    75.                 # 所以添加到列表最后
    76.                 node_list.append(parent)
    77.  
    78.         # 此时列表中只有一棵二叉树，即所求的哈夫曼树
    79.         # 返回哈夫曼树的根结点
    80.         return node_list[0]
    81.  
    82.     def get_huffman_code_tab(self, ele_node: CodeNode, code: str, code_str: str):
    83.         """
    84.         遍历所创建的哈夫曼树，得到所有叶子节点（叶子结点即要得到的字符）的编码
    85.         这里规定左节点为0，右节点为1
    86.         :param ele_node: 传入的要遍历的树的根节点，初始为根节点
    87.         :param code: 表示所选择的路径是左节点还是右节点
    88.         :param code_str: 每个字符对应的编码
    89.         :return:
    90.         """
    91.         code_str += code  # 拼接编码
    92.         if ele_node.data is None:
    93.             # 表示是非叶子节点，因为在创建哈夫曼树时设置了为叶子结点的data为空
    94.             # code_str += code
    95.             if ele_node.left:
    96.                 self.get_huffman_code_tab(ele_node.left, '0', code_str)
    97.             if ele_node.right:
    98.                 self.get_huffman_code_tab(ele_node.right, '1', code_str)
    99.         else:  # 是叶子节点
    100.             self.huffman_code_tab[chr(ele_node.data)] = code_str
    101.  
    102.     def huffman_zip(self, s: str) -> list:
    103.         """
    104.         利用哈夫曼编码表把字符串中的每一个字符转换成对应的编码
    105.         即将一个字符串根据哈夫曼编码进行压缩，得到一个压缩后的结果
    106.         :param s: 要转换的字符串
    107.         :return: 返回编码后的列表
    108.         """
    109.         res = ''
    110.         # 遍历字符串，将每一个字符转换成对应的编码，并将所有编码拼接起来
    111.         # "i like like like java do you like a java" => 以下形式
    112.         # 1100111111101110001011111110111000101111111011100010100001011000101011
    113.         # 001100001011001000011001110111111101110001011010100001011000101
    114.         for i in s:
    115.             res += self.huffman_code_tab[i]
    116.         # 将得到的编码字符串按八位进行分割，将每八位转换成一个int，并将int存放到列表中
    117.         code_list = []
    118.         i = 0
    119.         n = len(res)
    120.         while i < n:
    121.             num = int(res[i:i + 8], 2)  # 将二进制字符串转换为整数
    122.             code_list.append(num)
    123.             i += 8
    124.             if i < n <= i + 8:  # 已经分割到了最后一部分，记录该部分的长度
    125.                 self.last_char_len = n - i
    126.  
    127.         return code_list
    128.  
    129.     def huffman_decode(self, code_list) -> str:
    130.         """
    131.         将哈夫曼编码进行解压，得到一个可阅读的字符串
    132.         :param code_list: 要解压的哈夫曼编码列表
    133.         :return: 解码后的字符串
    134.         """
    135.         # 将哈夫曼编码列表转换成对应的二进制字符串
    136.         # [415, 476, 95, 476, 95, 476, 80, 177, 345, 389, 400, 206, 254, 226, 212, 44, 5] =>
    137.         # 1100111111101110001011111110111000101111111011100010100001011000101011
    138.         # 001100001011001000011001110111111101110001011010100001011000101
    139.         code_str = ''  # 存储对应的二进制字符串
    140.         count = 0
    141.         n = len(code_list)
    142.         for i in code_list:
    143.             t = "{:08b}".format(i)  # 将整数转换为二进制字符串
    144.             code_str += t
    145.             count += 1
    146.             if count == n - 1:
    147.                 break
    148.         code_str += "{:0{k}b}".format(code_list[count], k=self.last_char_len)
    149.  
    150.         # 将哈夫曼编码表的键值互换
    151.         # 比如原来的是'a': '001' => 变成 '001': 'a'
    152.         code_tab = {}
    153.         for k, v in self.huffman_code_tab.items():
    154.             code_tab[v] = k
    155.  
    156.         # 遍历二进制字符串
    157.         j = 0
    158.         i = 1
    159.         n = len(code_str)
    160.         res_code = ''  # 解码后的字符串
    161.         while i <= n:
    162.             t = code_str[j:i]
    163.             ch = code_tab.get(t)
    164.             if ch:
    165.                 res_code += ch
    166.                 j = i
    167.             i += 1
    168.         return res_code
    169.  
    170.  
    171. s = "i like like like java do you like a java"
    172. # s = "I love python hahha nihao"
    173. huffman = HuffmanCode()
    174. root_node = huffman.create_huffman_tree(s)
    175. huffman.get_huffman_code_tab(root_node, '', '')
    176. huffman_code_list = huffman.huffman_zip(s)
    177. decode_str = huffman.huffman_decode(huffman_code_list)
    178. print(decode_str)

    使用哈夫曼编码压缩文件的注意事项（代码胜省略）

  • 相关阅读:
    【Java】从Java代码到网络编程，三次握手又该如何理解
    解决Vue发布后新旧包切换点击路由报错问题
    hashSet解析
    学会这些Jmeter插件，才能设计出复杂性能测试场景
    6W+字记录实验全过程 | 探索Alluxio经济化数据存储策略
    一次较波折的MySQL调优
    oracle connect by详解
    day02 Nacos集群配置、Feign远程调用和统一网关Gateway
    Linux系统的定时任务
    7 SpringBoot与Elasticsearch
  • 原文地址：https://blog.csdn.net/2301_77659011/article/details/133962929