go实现哈夫曼编码

news/2024/6/15 14:48:14/文章来源:https://blog.csdn.net/mawanbing/article/details/137130985

package main
 
import (
    "bytes"
    "fmt"
)
 
// 定义节点类型
type Node struct {
    Weight int
    Left   *Node
    Right  *Node
}
 
// 构建哈夫曼树
func buildHuffmanTree(weights []int) *Node {
    var nodes []*Node
    for _, weight := range weights {
        nodes = append(nodes, &Node{Weight: weight})
    }
 
    for len(nodes) > 1 {
        // 排序节点,按照权重从小到大
        sortNodes(nodes)
 
        // 取出最小的两个节点创建新节点
        a, b := nodes[0], nodes[1]
        newNode := &Node{Weight: a.Weight + b.Weight, Left: a, Right: b}
 
        // 删除已经处理的两个节点
        nodes = append(nodes[:0], nodes[2:]...)
 
        // 将新节点加入到节点列表中
        nodes = append(nodes, newNode)
    }
 
    return nodes[0]
}
 
// 对节点列表进行排序
func sortNodes(nodes []*Node) {
    for i := range nodes {
        for j := i; j > 0 && nodes[j].Weight < nodes[j-1].Weight; j-- {
            nodes[j], nodes[j-1] = nodes[j-1], nodes[j]
        }
    }
}
 
// 哈夫曼编码
func huffmanEncoding(root *Node, encoding map[byte]string) {
    var traverse func(node *Node, code string)
    traverse = func(node *Node, code string) {
        if node.Left == nil && node.Right == nil {
            encoding[byte(node.Weight)] = code
            return
        }
        traverse(node.Left, code+"0")
        traverse(node.Right, code+"1")
    }
 
    traverse(root, "")
}
 
// 哈夫曼解码
func huffmanDecoding(root *Node, data string) string {
    var result bytes.Buffer
    current := root
    for i := range data {
        if current.Left == nil && current.Right == nil {
            result.WriteByte(byte(current.Weight))
            current = root
            continue
        }
        if data[i] == '0' {
            current = current.Left
        } else if data[i] == '1' {
            current = current.Right
        }
    }
    return result.String()
}
 
func main() {
    // 示例:文本"aaabbbbccccddddeeeee"的哈夫曼编码和解码
    text := "aaabbbbccccddddeeeee"
    weights := make([]int, 27) // 字母从'a'到'z'的权重
 
    // 统计每个字符的权重
    for _, char := range text {
        weights[char-'a']++
    }
 
    // 构建哈夫曼树
    root := buildHuffmanTree(weights)
 
    // 生成哈夫曼编码
    encoding := make(map[byte]string)
    huffmanEncoding(root, encoding)
 
    // 示例:打印每个字符的哈夫曼编码
    for char, code := range encoding {
        fmt.Printf("%c: %s\n", char, code)
    }
 
    // 使用哈夫曼编码对文本进行编码
    var encoded bytes.Buffer
    for _, char := range text {
        encoded.WriteString(encoding[byte(char)])
    }
    encodedText := encoded.String()
    fmt.Printf("Encoded text: %s\n", encodedText)
 
    // 使用哈夫曼树对编码文本进行解码
    decodedText := huffmanDecoding

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1033795.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

C++项目——集群聊天服务器项目(九)客户端异常退出业务

服务器端应检测到客户端是否异常退出&#xff0c;因此本节来实现客户端异常退出&#xff0c;项目流程见后文 一、客户端异常退出业务流程 &#xff08;1&#xff09;在业务模块定义处理客户端异常退出的函数 &#xff08;2&#xff09;集群聊天服务器项目(八&#xff09;提到…

Linux(CentOS7)安装 MongoDB

目录 下载 上传 解压 创建mongodb.conf 创建数据文件夹和日志文件夹 启动服务 创建软链接 安装客户端 下载 上传 安装 下载 官方地址&#xff1a; Download MongoDB Community Server | MongoDBhttps://www.mongodb.com/try/download/community 上传 将下载好的 …

跨境运营必看:TikTok账号防封指南

多人在使用TikTok的过程中都会遇到一些问题&#xff0c;比如为什么TikTok没有浏览量&#xff1f;事实上&#xff0c;这很可能是因为你的账号已被禁止。但为什么它会被封呢&#xff1f;你怎样才能解决它&#xff1f; 一、TikTok账号为什么被封&#xff1f; 1、什么是 TikTok 影…

输油管道变电所运维系统发展趋势

摘要&#xff1a;随着现代化技术以及信息化手段的飞速发展&#xff0c;社会已经进入到了全新的发展阶段&#xff0c;这也为自动化技术的发展起到了良好的促进作用&#xff0c;特别是在目前输油管道电网快速发展的背景下&#xff0c;传统的输油管道变电站管理模式与管理系统&…

Scrapy爬虫的打包Auto-py-to-exe/Pyinstall

Scrapy爬虫打包成可执行文件 前言步骤Scrapy代码部分auto-py-to-exe部分1. 安装2. 配置 前言 朋友托了我写了个小爬虫&#xff0c;然后写成之后老是要在我这儿跑&#xff0c;交付不了给朋友。项目太小&#xff0c;也不好用scrapyd托管在服务器。找了找有pyinstall和Auto-py-to…

C++语言学习(二)——⭐缺省参数、函数重载、引用

1.⭐缺省参数 &#xff08;1&#xff09;缺省参数概念 缺省参数是声明或定义函数时为函数的参数指定一个缺省值。在调用该函数时&#xff0c;如果没有指定实参则采用该形参的缺省值&#xff0c;否则使用指定的实参。 void Func(int a 0) {cout<<a<<endl; } int…

keepalived+LVS高可用部署

目录 一.两台设备&#xff08;2.130和2.133&#xff09;作为调度器&#xff0c;前主后备 1.部署keepalived 2.修改配置文件准备启动 3.配置keepalived的系统日志并启动 二.模拟调度器掉点和web服务进程丢失 1.调度器掉点 2.当类似于httpd这种网站服务掉点 三.以三种健康…

简单了解观察者模式(发布 - 订阅模式)

什么是观察者模式&#xff1f; 观察者根据主题类的内部状态变化来改变自身状态&#xff0c;简单来说就是观察者订阅了主题类&#xff0c;当主题类发布一些消息&#xff0c;观察者就会收到消息&#xff0c;然后做出反应。 Spring的观察者模式 Spring用了监听器&#xff08;观察…

时序数据库IoTDB:功能详解与行业应用

一文读懂时序数据库 IoTDB。 01 为什么需要时序数据库 解释时序数据库前&#xff0c;先了解一下何谓时序数据。 时序数据&#xff0c;也称为时间序列数据&#xff0c;是指按时间顺序记录的同一统计指标的数据集合。这类数据的来源主要是能源、工程、交通等工业物联网强关联行业…

数据可视化高级技术(Echarts)

目录 &#xff08;一&#xff09;数据可视化概念及Echarts基础知识 数据可视化的好处&#xff1a; 数据可视化的目标 数据可视化的基本流程 &#xff08;二&#xff09;数据图表 类别比较图表&#xff1a; 数据关系图表&#xff1a; 数据分布图表&#xff1a; 时间序列…

ETL中如何自定义规则

一、ETL中的规则 在使用规则之前我们先来了解一下什么是规则&#xff0c;ETL中规则在很多组件中都能看见&#xff0c;可以理解为按照事前约定好的逻辑去执行&#xff0c;规则可以使得数据更加的规范统一&#xff0c;同时也不需要去纵向的修改底层代码&#xff0c;只需要动态编…

机器学习模型及其使用方法——《机器学习图解》

本书教你两件事——机器学习模型及其使用方法 机器学习模型有不同的类型&#xff0c;有些返回确定性的答案&#xff0c;例如是或否&#xff0c;而另一些返回概率性的答案。有些以问题的形式呈现&#xff1b;其他则使用假设性表达。这些类型的一个共同点是它们都返回一个答案或…

成都市酷客焕学新媒体科技有限公司:实现品牌的更大价值!

成都市酷客焕学新媒体科技有限公司专注于短视频营销&#xff0c;深知短视频在社交媒体中的巨大影响力。该公司巧妙地将品牌信息融入富有创意和趣味性的内容中&#xff0c;使观众在轻松愉悦的氛围中接受并传播这些信息。凭借独特的创意和精准的营销策略&#xff0c;成都市酷客焕…

docker 共享网络的方式实现容器互联

docker 共享网络的方式实现容器互联 本文以nacos连接mysql为例 前提已经在mysql容器中初始化好nacos数据库&#xff0c;库名nacos 创建一个共享网络 docker network create --driver bridge \ --subnt 192.168.0.0/24 \ --gateway 192.168.0.1 mynet此处可以不指定网络模式、…

软件接口安全设计规范及审计要点

1.token授权安全设计 2.https传输加密 3.接口调用安全设计 4.日志审计里监控 5.开发测试环境隔离&#xff0c;脱敏处理 6.数据库运维监控审计 项目管理全套资料获取&#xff1a;软件开发全套资料_数字中台建设指南-CSDN博客

未来购物新篇章:臻奶惠无人新零售

未来购物新篇章&#xff1a;臻奶惠无人新零售 随着科技的不断进步和消费者购物习惯的变化&#xff0c;无人新零售已经成为零售行业的一大趋势&#xff0c;它不仅重新定义了购物体验&#xff0c;也为零售行业带来了前所未有的变革。无人新零售&#xff0c;一种融合了AI技术、物…

民航电子数据库:在有分组统计的语句中,输出表达式含有非分组统计项

目录 一、场景二、报错信息三、排查四、原因五、解决 一、场景 1、对接民航电子数据库 2、执行SQL语句报错 二、报错信息 三、排查 查看数据库def_group_by_mode配置 show def_group_by_mode四、原因 def_group_by_mode设置为0导致&#xff0c;相当于mysql的sql_modeonly_…

SAP Fiori开发中的JavaScript基础知识9 - 代码注释,严格模式,JSON

1 背景 本文将介绍JavaScript编程中的三个小知识点&#xff1a;也即代码注释&#xff0c;严格模式&#xff0c;JSON文件。 2 代码注释 JavaScript的代码注释方式如下&#xff1a; // Single line comment/* Multi line comment */3 严格模式 JavaScript的"strict mod…

Go语言爬虫实战(线程池)

Go语言爬虫实战 目标 利用go语言爬取指定网站的图片。实现爬取网站任意页面所有所需的图片。实现使用go语言线程池开启多个线程爬取图片内容。最后实现创建多个文件夹存储图片。 爬取网站图片 步骤 对指定URL发去GET请求&#xff0c;获取对应的响应。 resp, err : http.Get(…

记一道文件上传

林深时遇见鹿&#xff0c;海蓝时遇见鲸。 首先先随便上传一个文件&#xff0c; 经测试php相关后缀都不能上传&#xff0c;且<?被过滤。 而且.user.ini里的file也被过滤了 所以只能使用.htaccess了 但是<?被过滤了&#xff0c;所以我们可以使用php伪协议来用base64加…