哈夫曼树原理
秉着能不写就不写的理念,关于哈夫曼树的原理及其构建,还是贴一篇博客吧。
https://www.jb51.net/article/97396.htm
其大概流程
哈夫曼编码代码
# 树节点类构建 class TreeNode(object): def __init__(self, data): self.val = data[0] self.priority = data[1] self.leftChild = None self.rightChild = None self.code = "" # 创建树节点队列函数 def creatnodeQ(codes): q = [] for code in codes: q.append(TreeNode(code)) return q # 为队列添加节点元素,并保证优先度从大到小排列 def addQ(queue, nodeNew): if len(queue) == 0: return [nodeNew] for i in range(len(queue)): if queue[i].priority >= nodeNew.priority: return queue[:i] + [nodeNew] + queue[i:] return queue + [nodeNew] # 节点队列类定义 class nodeQeuen(object): def __init__(self, code): self.que = creatnodeQ(code) self.size = len(self.que) def addNode(self,node): self.que = addQ(self.que, node) self.size += 1 def popNode(self): self.size -= 1 return self.que.pop(0) # 各个字符在字符串中出现的次数,即计算优先度 def freChar(string): d ={} for c in string: if not c in d: d[c] = 1 else: d[c] += 1 return sorted(d.items(),key=lambda x:x[1]) # 创建哈夫曼树 def creatHuffmanTree(nodeQ): while nodeQ.size != 1: node1 = nodeQ.popNode() node2 = nodeQ.popNode() r = TreeNode([None, node1.priority+node2.priority]) r.leftChild = node1 r.rightChild = node2 nodeQ.addNode(r) return nodeQ.popNode() codeDic1 = {} codeDic2 = {} # 由哈夫曼树得到哈夫曼编码表 def HuffmanCodeDic(head, x): global codeDic, codeList if head: HuffmanCodeDic(head.leftChild, x+'0') head.code += x if head.val: codeDic2[head.code] = head.val codeDic1[head.val] = head.code HuffmanCodeDic(head.rightChild, x+'1') # 字符串编码 def TransEncode(string): global codeDic1 transcode = "" for c in string: transcode += codeDic1[c] return transcode # 字符串解码 def TransDecode(StringCode): global codeDic2 code = "" ans = "" for ch in StringCode: code += ch if code in codeDic2: ans += codeDic2[code] code = "" return ans # 举例 string = "AAGGDCCCDDDGFBBBFFGGDDDDGGGEFFDDCCCCDDFGAAA" t = nodeQeuen(freChar(string)) tree = creatHuffmanTree(t) HuffmanCodeDic(tree, '') print(codeDic1,codeDic2) a = TransEncode(string) print(a) aa = TransDecode(a) print(aa) print(string == aa)
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
分享文章:Python完成哈夫曼树编码过程及原理详解-创新互联
标题网址:https://www.cdcxhl.com/article14/discge.html
成都网站建设公司_创新互联,为您提供定制开发、软件开发、ChatGPT、响应式网站、做网站、云服务器
声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联