Python描述數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)之哈夫曼樹篇
前言
本篇章主要介紹哈夫曼樹及哈夫曼編碼,包括哈夫曼樹的一些基本概念、構(gòu)造、代碼實現(xiàn)以及哈夫曼編碼,并用Python實現(xiàn)。
1. 基本概念
哈夫曼樹
其中,
帶權(quán)路徑長度是帶權(quán)結(jié)點和根結(jié)點之間的路徑長度與該結(jié)點的權(quán)值的乘積。有關(guān)帶權(quán)結(jié)點、路徑長度的概念請參閱這篇博客。
對于含有
2. 構(gòu)造過程及實現(xiàn)
給定
比如
代碼實現(xiàn):
class HuffmanTreeNode(object): def __init__(self): self.data = '#' self.weight = -1 self.parent = None self.lchild = None self.rchild = None class HuffmanTree(object): def __init__(self, data_list): self.nodes = [] # 按權(quán)重從大到小進行排列 for val in data_list: newnode = HuffmanTreeNode() newnode.data = val[0] newnode.weight = val[1] self.nodes.append(newnode) self.nodes = sorted(self.nodes, key=lambda node: node.weight, reverse=True) print([(node.data, node.weight) for node in self.nodes]) def CreateHuffmanTree(self): # 這里注意區(qū)分 # TreeNode = self.nodes[:] 變量TreeNode, 這個相當(dāng)于深拷貝, TreeNode變化不影響nodes # TreeNode = self.nodes 指針TreeNode與nodes共享一個地址, 相當(dāng)于淺拷貝, TreeNode變化會影響nodes TreeNode = self.nodes[:] if len(TreeNode) > 0: while len(TreeNode) > 1: letfTreeNode = TreeNode.pop() rightTreeNode = TreeNode.pop() newNode = HuffmanTreeNode() newNode.lchild = letfTreeNode newNode.rchild = rightTreeNode newNode.weight = letfTreeNode.weight + rightTreeNode.weight letfTreeNode.parent = newNode rightTreeNode.parent = newNode self.InsertTreeNode(TreeNode, newNode) return TreeNode[0] def InsertTreeNode(self, TreeNode, newNode): length = len(TreeNode) if length > 0: temp = length - 1 while temp >= 0: if newNode.weight < TreeNode[temp].weight: TreeNode.insert(temp+1, newNode) return True temp -= 1 TreeNode.insert(0, newNode)
3. 哈夫曼編碼
在數(shù)據(jù)通信時,假如我們要發(fā)送
A | B | C | D | E | F | G | |
---|---|---|---|---|---|---|---|
固定長度編碼 | 000 | 001 | 010 | 011 | 100 | 101 | 110 |
可變長度編碼 | 0 | 1 | 01 | 10 | 11 | 101 | 110 |
報文最短可以引申到二叉樹路徑最短,即構(gòu)造前綴編碼的實質(zhì)就是構(gòu)造一棵哈夫曼樹,通過這種形式獲得的二進制編碼稱為哈夫曼編碼。這里的權(quán)值就是報文中字符出現(xiàn)的概率,出現(xiàn)概率越高的字符我們用越短的字符表示。
以下表中的字符及其出現(xiàn)的概率為例來實現(xiàn)哈夫曼編碼:
字符 | A | B | C | D | E | F | G | H |
---|---|---|---|---|---|---|---|---|
出現(xiàn)概率 | 0.01 | 0.43 | 0.15 | 0.02 | 0.03 | 0.21 | 0.07 | 0.08 |
哈夫曼編碼 | 101010 | 0 | 110 | 101011 | 10100 | 111 | 1011 | 100 |
代碼實現(xiàn)就是在哈夫曼樹的基礎(chǔ)上加一個編碼的函數(shù):
def HuffmanEncode(self, Root): TreeNode = self.nodes[:] code_result = [] for index in range(len(TreeNode)): temp = TreeNode[index] code_leaf = [temp.data] code = '' while temp is not Root: if temp.parent.lchild is temp: # 左分支 code = '0' + code else: # 右分支 code = '1' + code temp = temp.parent code_leaf.append(code) code_result.append(code_leaf) return code_result
測試結(jié)果如下:
if __name__ == '__main__': tree_obj = HuffmanTree([('A', 0.01), ('B', 0.43), ('C', 0.15), ('D', 0.02), ('E', 0.03), ('F', 0.21), ('G', 0.07), ('H', 0.08)]) huf_tree = tree_obj.CreateHuffmanTree() huf_code = tree_obj.HuffmanEncode(huf_tree) for index in range(len(huf_code)): print('{0}: {1}'.format(huf_code[index][0], huf_code[index][1]))
總結(jié)
到此這篇關(guān)于Python描述數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)之哈夫曼樹篇的文章就介紹到這了,更多相關(guān)Python數(shù)據(jù)結(jié)構(gòu)之哈夫曼樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
- Python 數(shù)據(jù)結(jié)構(gòu)之樹的概念詳解
- Python數(shù)據(jù)結(jié)構(gòu)之二叉排序樹的定義、查找、插入、構(gòu)造、刪除
- Python數(shù)據(jù)結(jié)構(gòu)之棧、隊列及二叉樹定義與用法淺析
- Python數(shù)據(jù)結(jié)構(gòu)之哈夫曼樹定義與使用方法示例
- Python數(shù)據(jù)結(jié)構(gòu)與算法之字典樹實現(xiàn)方法示例
- Python數(shù)據(jù)結(jié)構(gòu)與算法之完全樹與最小堆實例
- Python數(shù)據(jù)結(jié)構(gòu)與算法之二叉樹結(jié)構(gòu)定義與遍歷方法詳解
- Python數(shù)據(jù)結(jié)構(gòu)之樹的全面解讀
相關(guān)文章
python模塊詳解之pywin32使用文檔(python操作windowsAPI)
pywin32是一個第三方模塊庫,主要的作用是方便python開發(fā)者快速調(diào)用windows API的一個模塊庫,這篇文章主要給大家介紹了關(guān)于python模塊詳解之pywin32使用文檔的相關(guān)資料,文中將python操作windowsAPI介紹的非常詳細,需要的朋友可以參考下2024-01-01將圖片文件嵌入到wxpython代碼中的實現(xiàn)方法
前面一篇文章中提到的那個程序,GUI中包含了一張圖片。在編譯成exe文件發(fā)布時,無法直接生成一個單獨的exe文件。因此需要直接把圖片寫入到代碼中2014-08-08淺談Pytorch 定義的網(wǎng)絡(luò)結(jié)構(gòu)層能否重復(fù)使用
這篇文章主要介紹了Pytorch定義的網(wǎng)絡(luò)結(jié)構(gòu)層能否重復(fù)使用的操作,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2021-06-06基于matplotlib中ion()和ioff()的使用詳解
這篇文章主要介紹了基于matplotlib中ion()和ioff()的使用詳解,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2020-06-06pytest使用parametrize將參數(shù)化變量傳遞到fixture
這篇文章主要為大家介紹了pytest使用parametrize將參數(shù)化變量傳遞到fixture的使用詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2022-05-05Python導(dǎo)入或執(zhí)行python源文件的3種方法
這篇文章主要給大家介紹了關(guān)于Python導(dǎo)入或執(zhí)行python源文件的3種方法,python源代碼的文件以"py"為擴展名,由python.exe解釋,可以在控制臺下運行,需要的朋友可以參考下2023-08-08Python NumPy創(chuàng)建數(shù)組方法
這篇文章主要介紹了Python NumPy創(chuàng)建數(shù)組方法,文章圍繞主題展開詳細的內(nèi)容介紹,具有一定的參考價值,需要的朋友可以參考一下2022-09-09Python中的JSON?Pickle?Shelve模塊特性與區(qū)別實例探究
在Python中,處理數(shù)據(jù)序列化和持久化是極其重要的,JSON、Pickle和Shelve是三種常用的模塊,它們提供了不同的方法來處理數(shù)據(jù)的序列化和持久化,本文將深入研究這三個模塊,探討它們的特性、用法以及各自的優(yōu)缺點2024-01-01