python哈夫曼树解码_Python哈夫曼树HuffmanTree

今天要讲的是天才哈夫曼的哈夫曼编码&＃xff0c;这是树形数据结构的一个典型应用。

&＃xff01;&＃xff01;&＃xff01;敲黑板&＃xff01;&＃xff01;&＃xff01;哈夫曼树的构建以及编码方式将是我们的学习重点。

老方式&＃xff0c;代码&＃43;解释&＃xff0c;手把手教你Python完成哈夫曼编码的全过程。、

首先&＃xff0c;我先假设你已经有了二叉树的相关知识&＃xff0c;主要就是概念和遍历方式这些点。如果没有这些知识储备&＃xff0c;可能理解起来会比较困难。

好了&＃xff0c;废话不多说。

哈夫曼树原理

秉着能不写就不写的理念&＃xff0c;关于哈夫曼树的原理及其构建&＃xff0c;还是贴一篇博客吧。

http://www.cnblogs.com/mcgrady/p/3329825.html。(这篇博客关于哈夫曼树及其编码的原理讲的还行&＃xff0c;简洁易懂&＃xff0c;因为哈夫曼树原理本来就挺简单的)。

其大概流程

哈夫曼编码代码

#树节点类构建

classTreeNode(object):def __init__(self, data):

self.val&＃61;data[0]

self.priority&＃61; data[1]

self.leftChild&＃61;None

self.rightChild&＃61;None

self.code&＃61; ""

#创建树节点队列函数

defcreatnodeQ(codes):

q&＃61;[]for code incodes:

q.append(TreeNode(code))returnq#为队列添加节点元素&＃xff0c;并保证优先度从大到小排列

defaddQ(queue, nodeNew):if len(queue) &＃61;&＃61;0:return[nodeNew]for i inrange(len(queue)):if queue[i].priority >&＃61;nodeNew.priority:return queue[:i] &＃43; [nodeNew] &＃43;queue[i:]return queue &＃43;[nodeNew]#节点队列类定义

classnodeQeuen(object):def __init__(self, code):

self.que&＃61;creatnodeQ(code)

self.size&＃61;len(self.que)defaddNode(self,node):

self.que&＃61;addQ(self.que, node)

self.size&＃43;&＃61; 1

defpopNode(self):

self.size-&＃61; 1

returnself.que.pop(0)#各个字符在字符串中出现的次数&＃xff0c;即计算优先度

deffreChar(string):

d&＃61;{}for c instring:if not c ind:

d[c]&＃61; 1

else:

d[c]&＃43;&＃61; 1

return sorted(d.items(),key&＃61;lambda x:x[1])#创建哈夫曼树

defcreatHuffmanTree(nodeQ):while nodeQ.size !&＃61; 1:

node1&＃61;nodeQ.popNode()

node2&＃61;nodeQ.popNode()

r&＃61; TreeNode([None, node1.priority&＃43;node2.priority])

r.leftChild&＃61;node1

r.rightChild&＃61;node2

nodeQ.addNode(r)returnnodeQ.popNode()

codeDic1&＃61;{}

codeDic2&＃61;{}#由哈夫曼树得到哈夫曼编码表

defHuffmanCodeDic(head, x):globalcodeDic, codeListifhead:

HuffmanCodeDic(head.leftChild, x&＃43;&＃39;0&＃39;)

head.code&＃43;&＃61;xifhead.val:

codeDic2[head.code]&＃61;head.val

codeDic1[head.val]&＃61;head.code

HuffmanCodeDic(head.rightChild, x&＃43;&＃39;1&＃39;)#字符串编码

defTransEncode(string):globalcodeDic1

transcode&＃61; ""

for c instring:

transcode&＃43;&＃61;codeDic1[c]returntranscode#字符串解码

defTransDecode(StringCode):globalcodeDic2

code&＃61; ""ans&＃61; ""

for ch inStringCode:

code&＃43;&＃61;chif code incodeDic2:

ans&＃43;&＃61;codeDic2[code]

code&＃61; ""

returnans

# 举例

string&＃61; "AAGGDCCCDDDGFBBBFFGGDDDDGGGEFFDDCCCCDDFGAAA"t&＃61;nodeQeuen(freChar(string))

tree&＃61;creatHuffmanTree(t)

HuffmanCodeDic(tree,&＃39;&＃39;)print(codeDic1,codeDic2)

a&＃61;TransEncode(string)print(a)

aa&＃61;TransDecode(a)print(aa)print(string &＃61;&＃61; aa)

接下来就是一段一段分析代码

1.树结点类的构建&＃xff1a;

共有5个属性&＃xff1a;结点的值&＃xff0c;结点的优先度&＃xff0c;结点的左子结点&＃xff0c;结点的右子结点&＃xff0c;结点值的编码(这个没有什么好说的&＃xff0c;这些属性都是被需要的)

2.创建树结点队列函数&＃xff1a;

对于所有的字母结点&＃xff0c;我们将其组成一个队列&＃xff0c;这里使用list列表来完成队列的功能。将所有树节点够放进列表中&＃xff0c;当然传进来的是按优先度从小到大已排序的元素列表

3.为队列添加节点元素&＃xff0c;并保证优先度从大到小排列&＃xff1a;

当有新生成的结点时&＃xff0c;需将其插入列表&＃xff0c;并放在合适位置&＃xff0c;使队列依然时按优先度从小打到排列的。

4.结点队列类定义&＃xff1a;

创建类初始化时需要传进去的是一个列表&＃xff0c;列表中的每个元素是由字母与优先度组成的元组。元组第一个元素是字母&＃xff0c;第二个元素是优先度(即在文本中出现的次数)

类初始化化时&＃xff0c;调用“创建树结点队列函数”&＃xff0c;队列中的每个元素都是一个树结点。

类中还包含一个队列规模属性以及另外两个操作函数&＃xff1a;添加结点函数和弹出结点函数。

添加结点函数直接调用之前定义的函数即可&＃xff0c;输入的参数为队列和新结点&＃xff0c;并且队列规模加一

弹出第一个元素则直接调用列表的pop(0)函数&＃xff0c;同时队列规模减一

5.计算文本中个字母的优先度&＃xff0c;即出现的次数&＃xff1a;

定义一个字典&＃xff0c;遍历文本中的每一个字母&＃xff0c;若字母不在字典里说明是第一次出现&＃xff0c;则定义该字母为键&＃xff0c;另键值为1&＃xff0c;若在字典里有&＃xff0c;则只需将相应的键值加一。 遍历后就得到了每个字母出现的次数。

6.由哈夫曼树得到编码表&＃xff1a;

这里定义了两个全局字典&＃xff0c;用于存放字母编码&＃xff0c;一个字典用于编码&＃xff0c;另一个字典用于解码&＃xff0c;这样程序操作起来比较方便。

这里主要就是遍历&＃xff0c;运用的是二叉树的中序遍历。如果明白中序遍历的化&＃xff0c;就能看懂这里的代码&＃xff0c;每递归到深一层的时候&＃xff0c;就在后面多加一个‘0’(左子树)或‘1’(右子树)。

中序遍历我在

这一段是哈夫曼编码的关键&＃xff0c;也是难点&＃xff0c;希望能够好好理解一下&＃xff0c;也是对递归的一个理解。这一点没问题的话&＃xff0c;我觉得哈夫曼树真的挺简单的&＃xff01;&＃xff01;&＃xff01;

7.字符串编码&＃xff0c;字符串解码&＃xff1a;

这两段我就不详细说了&＃xff0c;应为已经有编码与解码的字典了&＃xff0c;所以对应每一个字母直接在字典里找就好了&＃xff0c;而且字典的寻找速度还是相当快的。

差不多了&＃xff0c;例子就不举了&＃xff0c;确实哈夫曼树比之前的什么八皇后问题还有KMP问题简单多了。

最后向Huffman大神致敬&＃xff0c;祝各位学有所成。