Python完成哈夫曼树编码过程及原理详解
作者:TomHawk 发布时间:2023-10-16 03:09:39
哈夫曼树原理
秉着能不写就不写的理念,关于哈夫曼树的原理及其构建,还是贴一篇博客吧。
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)
接下来就是一段一段分析代码
1.树结点类的构建:
共有5个属性:结点的值,结点的优先度,结点的左子结点,结点的右子结点,结点值的编码(这个没有什么好说的,这些属性都是被需要的)
2.创建树结点队列函数:
对于所有的字母结点,我们将其组成一个队列,这里使用list列表来完成队列的功能。将所有树节点够放进列表中,当然传进来的是按优先度从小到大已排序的元素列表
3.为队列添加节点元素,并保证优先度从大到小排列:
当有新生成的结点时,需将其插入列表,并放在合适位置,使队列依然时按优先度从小打到排列的。
4.结点队列类定义:
创建类初始化时需要传进去的是一个列表,列表中的每个元素是由字母与优先度组成的元组。元组第一个元素是字母,第二个元素是优先度(即在文本中出现的次数)
类初始化化时,调用“创建树结点队列函数”,队列中的每个元素都是一个树结点。
类中还包含一个队列规模属性以及另外两个操作函数:添加结点函数和弹出结点函数。
添加结点函数直接调用之前定义的函数即可,输入的参数为队列和新结点,并且队列规模加一
弹出第一个元素则直接调用列表的pop(0)函数,同时队列规模减一
5.计算文本中个字母的优先度,即出现的次数:
定义一个字典,遍历文本中的每一个字母,若字母不在字典里说明是第一次出现,则定义该字母为键,另键值为1,若在字典里有,则只需将相应的键值加一。 遍历后就得到了每个字母出现的次数。
6.由哈夫曼树得到编码表:
这里定义了两个全局字典,用于存放字母编码,一个字典用于编码,另一个字典用于解码,这样程序操作起来比较方便。
这里主要就是遍历,运用的是二叉树的中序遍历。如果明白中序遍历的化,就能看懂这里的代码,每递归到深一层的时候,就在后面多加一个‘0'(左子树)或‘1'(右子树)。
中序遍历我在上一篇博客中讲的还算可以吧,不懂的可以参考一下,否则就可以略过这一段。
这一段是哈夫曼编码的关键,也是难点,希望能够好好理解一下,也是对递归的一个理解。这一点没问题的话,我觉得哈夫曼树真的挺简单的!!!
7.字符串编码,字符串解码:
这两段我就不详细说了,应为已经有编码与解码的字典了,所以对应每一个字母直接在字典里找就好了,而且字典的寻找速度还是相当快的。
差不多了,例子就不举了,确实哈夫曼树比之前的什么八皇后问题还有KMP问题简单多了。
最后向Huffman大神致敬,祝各位学有所成。
来源:https://www.cnblogs.com/tomhawk/p/7471133.html
猜你喜欢
- reflect反射首先,我们要区分两个概念——“标识名”和&
- MapReduce是一种编程模型,用于大规模数据集(大于1TB)的并行运算。概念"Map(映射)"和"Redu
- <style> body {margin:10px;background-color:#ffffff;margin-t
- 超文本传输协议http构成了万维网的基础,它利用URI(统一资源标识符)来识别Internet上的数据,而指定文档地址的URI被称为URL(
- 取行和列的几种常用方式:data[ 列名 ]: 取单列或多列,不能用连续方式取,也不能用于取行。data.列名: 只用于取单列,不能用于行。
- 此次遇到的是一个函数使用不熟练造成的问题,但有了分析工具后可以很快定位到问题(此处推荐一个非常棒的抓包工具fiddler) 正文如
- 本案例使用 Jupyter Notebook进行案例演示,数据集为NBA球员信息数据集。本项目将进行完整的数据分析演示。1. 数据介绍数据集
- SQL Server 的扩展存储过程,其实就是一个普通的 Windows DLL,只不过按照某种规则实现了某些函数而已。近日在写一个扩展存储
- /* JS代码部分 */ 3 const date = new Date()const years = []const months = [
- 这篇文章主要介绍了Python input函数使用实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋
- 安装:pip install wave在wav 模块中 ,主要介绍一种方法:getparams(),该方法返回的结果如下:_wave_par
- 在Python多线程中如何创建一个线程对象如果你要创建一个线程对象,很简单,只要你的类继承threading.Thread,然后在__ini
- 程序能实现什么a.完成gap值的自定义输入以及两条需比对序列的输入b.完成得分矩阵的计算及输出c.输出序列比对结果d.使用matplotli
- 对于请求一些网站,我们需要加上请求头才可以完成网页的抓取,不然会得到一些错误,无法返回抓取的网页。下面,介绍两种添加请求头的方法。方法一:借
- asp无组件上传VBS编写的大家见的多了,这个是纯javascript实现的上传,原来unicode可以解决读取位置的问题,这次真的是纯JS
- 在 IT 开发中,有时我们需要对结构体数组进行排序。Go 语言提供了 sort 包,其中最常用的一种是 sort.Slice() 函数。但是
- 本文实例为大家分享了python类支持比较运算的具体代码,供大家参考,具体内容如下案例:有时我们希望自定义的类,实例间可以使用比较运算符进行
- 一、激活函数1.Sigmoid函数函数图像以及表达式如下:通过该函数,可以将输入的负无穷到正无穷的输入压缩到0-1之间。在x=0的时候,输出
- 版本 0.9来自 http://onewww.net说明:当焦点不在表格内的input时,回车键复制最后一行,delete删除键最后一行选择
- 在神经网络训练中,好的权重 初始化会加速训练过程。下面说一下kernel_initializer 权重初始化的方法。不同的层可能使用不同的关