首页 > 其他分享 >哈夫曼编码及例程

哈夫曼编码及例程

时间:2023-09-30 10:08:29浏览次数:35  
标签:node 编码 哈夫曼 例程 char frequency table data


哈夫曼编码是一种常见的无损压缩算法,通过根据字符出现的频率构建一个最优编码树,将频率较高的字符用较短的编码表示,从而实现数据的压缩。下面是一个简单的例程来演示如何使用哈夫曼编码进行文本数据的压缩和解压缩。

压缩过程:

  1. 统计输入文本中每个字符的出现频率。
  2. 根据字符频率构建哈夫曼树。频率越高的字符离根节点越近。
  3. 根据哈夫曼树生成每个字符的编码,左子树路径上为0,右子树路径上为1。
  4. 使用生成的编码对输入文本中的每个字符进行替换,生成压缩后的二进制数据。

解压缩过程:

  1. 使用相同的字符频率构建哈夫曼树。
  2. 从根节点开始,按压缩数据的每一位依次遍历哈夫曼树。
  3. 如果遇到0,则移动到当前节点的左子树;如果遇到1,则移动到当前节点的右子树。
  4. 当到达叶子节点时,输出对应的字符,并返回根节点继续处理下一位。

以下是一个简单的Python例程,展示了如何使用哈夫曼编码来压缩和解压缩文本数据。

import heapq
from collections import defaultdict

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

def build_frequency_table(data):
    frequency_table = defaultdict(int)
    for char in data:
        frequency_table[char] += 1
    return frequency_table

def build_huffman_tree(frequency_table):
    heap = []
    for char, freq in frequency_table.items():
        node = HuffmanNode(char, freq)
        heapq.heappush(heap, (freq, id(node), node))

    while len(heap) > 1:
        freq1, _, left = heapq.heappop(heap)
        freq2, _, right = heapq.heappop(heap)
        merged_freq = freq1 + freq2
        merged_node = HuffmanNode(None, merged_freq)
        merged_node.left = left
        merged_node.right = right
        heapq.heappush(heap, (merged_freq, id(merged_node), merged_node))

    _, _, root = heapq.heappop(heap)
    return root

def build_encoding_table(root):
    encoding_table = {}

    def traverse(node, code):
        if node.char is not None:
            encoding_table[node.char] = code
        else:
            traverse(node.left, code + '0')
            traverse(node.right, code + '1')

    traverse(root, '')
    return encoding_table

def encode_text(data, encoding_table):
    encoded_data = ''
    for char in data:
        encoded_data += encoding_table[char]
    return encoded_data

def decode_text(encoded_data, root):
    decoded_data = ''
    node = root
    for bit in encoded_data:
        if bit == '0':
            node = node.left
        else:
            node = node.right

        if node.char is not None:
            decoded_data += node.char
            node = root

    return decoded_data

# 示例用法
text = "Hello, world!"
frequency_table = build_frequency_table(text)
huffman_tree = build_huffman_tree(frequency_table)
encoding_table = build_encoding_table(huffman_tree)
encoded_data = encode_text(text, encoding_table)
decoded_data = decode_text(encoded_data, huffman_tree)

print("原始文本:", text)
print("压缩后的数据:", encoded_data)
print("解压缩后的文本:", decoded_data)


这个例程包含了构建频率表、构建哈夫曼树、生成编码表、压缩和解压缩等步骤,可以对输入的文本进行压缩并恢复。

标签:node,编码,哈夫曼,例程,char,frequency,table,data
From: https://blog.51cto.com/u_15903730/7654051

相关文章

  • ​​pandas.get_dummies()​​ 是一个用于执行独热编码(One-Hot Encoding)的 pandas 函
    pandas.get_dummies()是一个用于执行独热编码(One-HotEncoding)的pandas函数。它用于将分类(或离散)特征转换为模型可以处理的二进制格式,以便更好地在机器学习算法中使用。独热编码将每个不同的类别值转换为一个新的二进制特征列,其中每个列代表一个类别,并且只有一个值为1,其余为0......
  • 样例程序分析
    下面通过Robot.java的类,继续分析Java程序的应用。Java程序的运行结果是在控制台输出测试信息,信息的内容为 “Hi,”加上输入的name信息。首先来看一下Robot.java的类,核心代码如下。具体的源代码可以查看本书附带源码的chapter1-helloworld目录下的内容。publicclassRobot{p......
  • golang编码规范
     目录[-]golang编码规范gofmt注释命名控制结构函数(必须)错误处理panicimport缩写参数传递接受者 golang编码规范注:此文档参考官方指南EffectiveGolang和GolangCodeReviewComments进行整理,力图与官方及社区编码风格保持一致。gofmt大部分的格式问题可以通过gofmt解决,gofmt自动......
  • 人人FED CSS编码规范
    浏览器特效支持规范为了页面性能考虑,如果浏览器不支持CSS3相关属性的,则该浏览器的某些特效将不再支持,属性的支持情况如下表所示: 圆角阴影动画文字阴影透明背景渐变空间变换Chrome5+YYYYYYYFirefox4+YYYYYYYSafari5+YYYYYYYOperaYYYYYNYIE9+YYNNYNYChrome5-NNYYYYYFirefox4-NN......
  • Idea-无法将中文的十六进制编码自动还原为中文
    问题描述:在idea工具中,部分中文内容,只能显示原始的unicode编码,不能还原为中文。如: message对应的中文内容为:操作成功。但是在idea中只能显示:unicode类型的编码。但是System.out.println(message);又能显示正常中文。 问题原因:文件的编码格式为UTF-8,而Idea......
  • 合合信息、上海大学、华南理工大学发布业内首个古彝文编码“大字典” ,为古文字打造“
    “乌蒙山连着山外山,月光洒向了响水滩。”近期在各大短视频平台爆火的《奢香夫人》你听过吗?奢香夫人是一位彝族“巾帼英雄”,这首同名歌曲早在2009年便已发布,如今突然“翻红”,不仅体现了大众对于少数民族文化高涨的兴趣,也见证着优秀的传统文化不息的生命力。文字是文化的重要载体,古......
  • CH573 CH582 CH579蓝牙从机(Peripheral)/主机(Central)例程讲解一(蓝牙主从机收发数据
    原文链接:https://www.cnblogs.com/risc5-ble/p/15994545.html前言:蓝牙从机,顾名思义,就是一个蓝牙从设备,可以不断发送广播等待与主机建立连接进行通信,建立连接后,可以通知主机,也可以收到主机发的信息,一般使用BLE调试助手(安卓应用市场可下载),ios可使用Lightblue来进行调试通信等......
  • pbjs 无法编码 bytes 类型数据问题的解决方案
    问题背景之前写过一篇《使用脚本收发protobuf协议数据》,通过pbjs命令可以将protobuf二进制数据转换为json:>pbjsmsg.proto--decodeProbeIpv6Response<response.bin{"selfAddr":{"addrV6":"2409:8900:7900:8f0d:ecd9:4aee:aa3:7ad","port......
  • 使用 goland 的模板提高编码效率
    整体步骤来自chatgpt概述我觉得编译器有几个很提效的工具:快捷键、代码补全和代码模板。前两个没啥可说的,今天想分享的是代码模板。在Goland里被称之为LiveTemplates。在代码里输入forr,随后会出现如下的可选项,选中按下回车后,会自动生活一个forrange的遍历模板,通过ta......
  • 基于方向编码的模板匹配算法matlab仿真
    1.算法运行效果图预览  2.算法运行软件版本MATLAB2022a 3.算法理论概述       模板匹配是一种常见的计算机视觉方法,用于在一幅图像中寻找指定的模板。它在目标检测、图像识别、物体跟踪等领域中有广泛的应用。基于方向编码的模板匹配算法是一种改进的模板......