哈夫曼编码go语言实现
2021/11/6 23:40:38
本文主要是介绍哈夫曼编码go语言实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
//哈夫曼编码的实现,还未经过测试,只写了实现思路,后续还会改进优化 // Package huffman 构造哈夫曼树和哈夫曼编码 package huffman // HuffmanTreeNode 哈夫曼树结点 type HuffmanTreeNode struct { Data rune //结点数据域 Weight int //结点权重 Parent int //父结点索引 LeftChild int //左子树根节点索引 RightChild int //右子树根结点索引 } // HuffmanCodes 用来存储哈夫曼编码表 var HuffmanCodes map[rune]int // HuffmanTreeCoding 进行哈夫曼编码 func HuffmanTreeCoding( huffmanTree []HuffmanTreeNode, //哈夫曼树 huffmanCodes map[rune][]byte, //用于存放哈夫曼编码表 //用于存储n个结点的权重 weight []int){ if len(weight)<=1{ return } huffmanTreeLength:=2*(len(weight))-1 huffmanTree=make([]HuffmanTreeNode,huffmanTreeLength) for i := 0; i < len(weight); i++ { huffmanTree[i].Weight=weight[i] } for i := len(weight); i < huffmanTreeLength; i++ { huffmanTree[i].Weight=weight[i] } //构建哈夫曼树 for i := len(weight); i < huffmanTreeLength; i++ { min,secondaryMin:=Select(huffmanTree,i-1) huffmanTree[min].Parent=i huffmanTree[secondaryMin].Parent=i huffmanTree[i].LeftChild=min huffmanTree[i].RightChild=secondaryMin huffmanTree[i].Weight=huffmanTree[min].Weight+huffmanTree[secondaryMin].Weight } for i := 0; i < len(weight); i++ { j:=i parent:=huffmanTree[j].Parent for { //这里每个字符串对应的哈夫曼编码存储在一个切片中,且为倒序存储,取用编码的时候需要倒着取 if parent==0{ break } if huffmanTree[parent].LeftChild==i { huffmanCodes[huffmanTree[i].Data] = append(huffmanCodes[huffmanTree[i].Data], '0') }else { huffmanCodes[huffmanTree[i].Data] = append(huffmanCodes[huffmanTree[i].Data], '1') } j=parent parent=huffmanTree[parent].Parent } } } // Select 从切片组成的哈夫曼树中,从huffmanTree[0...bound]中选出权重最小的两个结点,返回对应的结点 func Select(huffmanTree []HuffmanTreeNode,bound int) (min int,secondaryMin int) { min=0 for i := 0; i < bound; i++ { if huffmanTree[i].Weight<huffmanTree[min].Weight{ min=i } } secondaryMin=1 for i := 0; i < bound; i++ { if huffmanTree[i].Weight<huffmanTree[secondaryMin].Weight &&i!=min{ secondaryMin=i } } return min,secondaryMin }
``
这篇关于哈夫曼编码go语言实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-24MongoDB资料:新手入门完全指南
- 2024-12-20go-zero 框架的 RPC 服务 启动start和停止 底层是怎么实现的?-icode9专业技术文章分享
- 2024-12-19Go-Zero 框架的 RPC 服务启动和停止的基本机制和过程是怎么实现的?-icode9专业技术文章分享
- 2024-12-18怎么在golang中使用gRPC测试mock数据?-icode9专业技术文章分享
- 2024-12-15掌握PageRank算法核心!你离Google优化高手只差一步!
- 2024-12-15GORM 中的标签 gorm:"index"是什么?-icode9专业技术文章分享
- 2024-12-11怎么在 Go 语言中获取 Open vSwitch (OVS) 的桥接信息(Bridge)?-icode9专业技术文章分享
- 2024-12-11怎么用Go 语言的库来与 Open vSwitch 进行交互?-icode9专业技术文章分享
- 2024-12-11怎么在 go-zero 项目中发送阿里云短信?-icode9专业技术文章分享
- 2024-12-11怎么使用阿里云 Go SDK (alibaba-cloud-sdk-go) 发送短信?-icode9专业技术文章分享