哈夫曼樹
哈夫曼樹的基本介紹
哈夫曼樹構(gòu)建步驟圖解
創(chuàng)建哈夫曼樹代碼實(shí)現(xiàn)
""" 創(chuàng)建哈夫曼樹 """
class EleNode:
""" 節(jié)點(diǎn)類 """
def __init__(self, value: int):
self.value = value
self.left = None # 指向左子節(jié)點(diǎn)
self.right = None # 指向右子節(jié)點(diǎn)
def __str__(self):
return f"Node [value={self.value}]"
def pre_order(self):
"""前序遍歷二叉樹"""
if self is None:
return
# 先輸出父節(jié)點(diǎn)
print(self, end=' => ')
# 左子樹不為空則遞歸左子樹
if self.left is not None:
self.left.pre_order()
# 右子樹不為空則遞歸右子樹
if self.right is not None:
self.right.pre_order()
class HuffmanTree:
arr: list = None
def __init__(self, arr):
self.arr = arr
def create_huffman_tree(self) -> EleNode:
# 對(duì) arr 列表進(jìn)行升序排序
self.arr.sort()
# 遍歷數(shù)組，將每個(gè)數(shù)組元素構(gòu)建成一個(gè) Node 節(jié)點(diǎn)
# 將 Node 節(jié)點(diǎn)加入到一個(gè)新列表中
node_list = []
for i in self.arr:
node_list.append(EleNode(i))
# 循環(huán)進(jìn)行以下步驟，直到列表中只剩下一棵二叉樹，此時(shí)該二叉樹就是哈夫曼樹
while len(node_list) > 1:
# 取出權(quán)值序列中最小的兩課二叉樹（即列表中的前兩個(gè)元素）構(gòu)建一棵新的二叉樹
left = node_list.pop(0)
right = node_list.pop(0)
# 新二叉樹的根節(jié)點(diǎn)的權(quán)值=兩個(gè)節(jié)點(diǎn)權(quán)值之和
parent = EleNode(left.value + right.value)
# 讓新二叉樹的左右節(jié)點(diǎn)分別指向兩個(gè)最小的節(jié)點(diǎn)
parent.left = left
parent.right = right
# 將新二叉樹根據(jù)根節(jié)點(diǎn)的大小插入到序列中的指定位置
i = 0
n = len(node_list)
while i < n:
if node_list[i].value >= parent.value:
node_list.insert(i, parent) # 找到了根節(jié)點(diǎn)存放的位置
break
i += 1
else:
# 循環(huán)結(jié)束表示新的二叉樹的權(quán)值最大，在node_list列表中沒(méi)有比它大的
# 所以添加到列表最后
node_list.append(parent)
# 此時(shí)列表中只有一棵二叉樹，即所求的哈夫曼樹
# 返回哈夫曼樹的根結(jié)點(diǎn)
return node_list[0]
huffman = HuffmanTree([13, 7, 8, 3, 29, 6, 1])
node = huffman.create_huffman_tree()
node.pre_order()哈夫曼編碼
基本介紹
哈夫曼編碼原理剖析
哈夫曼編碼的實(shí)例
思路分析
代碼實(shí)現(xiàn)文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-720689.html
""" 哈夫曼編碼 """
class CodeNode:
def __init__(self, data: int, weight: int):
self.data = data # 存放字符對(duì)應(yīng)的ASCII碼值
self.weight = weight # 存放字符在字符串中出現(xiàn)的次數(shù)
self.left = None
self.right = None
def __str__(self):
return f"Node[data={chr(self.data) if self.data else None}, weight={self.weight}]"
def pre_order(self):
"""二叉樹的前序遍歷"""
print(self)
if self.left:
self.left.pre_order()
if self.right:
self.right.pre_order()
class HuffmanCode:
# 哈夫曼編碼表
# 存儲(chǔ)每個(gè)字符對(duì)應(yīng)的編碼
# key為對(duì)應(yīng)的字符，val為字符對(duì)應(yīng)的編碼
huffman_code_tab = {}
# 記錄哈夫曼二進(jìn)制編碼字符串最后一個(gè)段的長(zhǎng)度
# 即會(huì)將哈夫曼二進(jìn)制字符串按八位進(jìn)行分割，分割到最后一個(gè)時(shí)長(zhǎng)度可不為8
# 所以用一個(gè)變量存儲(chǔ)最后一段二進(jìn)制字符串的長(zhǎng)度，在解碼的時(shí)候會(huì)用到
last_char_len = 0
def create_huffman_tree(self, s: str) -> CodeNode:
"""
構(gòu)建哈夫曼編碼二叉樹
:param s: 要編碼的字符串
:return:
"""
# 遍歷字符串，統(tǒng)計(jì)每一個(gè)字符出現(xiàn)的次數(shù)，并將結(jié)果放入字典
kw = {}
for ch in s:
ascii_code = ord(ch)
if kw.get(ascii_code): # 如果該字符出現(xiàn)過(guò)，則直接將其次數(shù)加1
kw[ascii_code] += 1
else: # 如果沒(méi)出現(xiàn)過(guò)，則出現(xiàn)次數(shù)為1
kw[ascii_code] = 1
# 按照字符出現(xiàn)的次數(shù)對(duì)字典進(jìn)行排序
kw = sorted(kw.items(), key=lambda kv: (kv[1], kv[0]))
# 遍歷字典，將每個(gè)元素構(gòu)建成一個(gè) Node 節(jié)點(diǎn)
# 將 Node 節(jié)點(diǎn)加入到一個(gè)新列表中
node_list = []
for k, v in kw:
# print(chr(k),'=', v, end=', ')
node_list.append(CodeNode(k, v))
# 循環(huán)進(jìn)行以下步驟，直到列表中只剩下一棵二叉樹，此時(shí)該二叉樹就是哈夫曼樹
while len(node_list) > 1:
# 取出權(quán)值序列中最小的兩課二叉樹（即列表中的前兩個(gè)元素）構(gòu)建一棵新的二叉樹
left = node_list.pop(0)
right = node_list.pop(0)
# 新二叉樹的根節(jié)點(diǎn)的權(quán)值=兩個(gè)節(jié)點(diǎn)權(quán)值之和
parent = CodeNode(None, left.weight + right.weight)
# 讓新二叉樹的左右節(jié)點(diǎn)分別指向兩個(gè)最小的節(jié)點(diǎn)
parent.left = left
parent.right = right
# 將新二叉樹根據(jù)根節(jié)點(diǎn)的大小插入到序列中的指定位置
n = len(node_list)
i = 0
while i < n:
if node_list[i].weight >= parent.weight:
node_list.insert(i, parent) # 找到了根節(jié)點(diǎn)存放的位置
break
i += 1
else:
# 循環(huán)結(jié)束表示新的二叉樹的權(quán)值最大，在node_list列表中沒(méi)有比它大的
# 所以添加到列表最后
node_list.append(parent)
# 此時(shí)列表中只有一棵二叉樹，即所求的哈夫曼樹
# 返回哈夫曼樹的根結(jié)點(diǎn)
return node_list[0]
def get_huffman_code_tab(self, ele_node: CodeNode, code: str, code_str: str):
"""
遍歷所創(chuàng)建的哈夫曼樹，得到所有葉子節(jié)點(diǎn)（葉子結(jié)點(diǎn)即要得到的字符）的編碼
這里規(guī)定左節(jié)點(diǎn)為0，右節(jié)點(diǎn)為1
:param ele_node: 傳入的要遍歷的樹的根節(jié)點(diǎn)，初始為根節(jié)點(diǎn)
:param code: 表示所選擇的路徑是左節(jié)點(diǎn)還是右節(jié)點(diǎn)
:param code_str: 每個(gè)字符對(duì)應(yīng)的編碼
:return:
"""
code_str += code # 拼接編碼
if ele_node.data is None:
# 表示是非葉子節(jié)點(diǎn)，因?yàn)樵趧?chuàng)建哈夫曼樹時(shí)設(shè)置了為葉子結(jié)點(diǎn)的data為空
# code_str += code
if ele_node.left:
self.get_huffman_code_tab(ele_node.left, '0', code_str)
if ele_node.right:
self.get_huffman_code_tab(ele_node.right, '1', code_str)
else: # 是葉子節(jié)點(diǎn)
self.huffman_code_tab[chr(ele_node.data)] = code_str
def huffman_zip(self, s: str) -> list:
"""
利用哈夫曼編碼表把字符串中的每一個(gè)字符轉(zhuǎn)換成對(duì)應(yīng)的編碼
即將一個(gè)字符串根據(jù)哈夫曼編碼進(jìn)行壓縮，得到一個(gè)壓縮后的結(jié)果
:param s: 要轉(zhuǎn)換的字符串
:return: 返回編碼后的列表
"""
res = ''
# 遍歷字符串，將每一個(gè)字符轉(zhuǎn)換成對(duì)應(yīng)的編碼，并將所有編碼拼接起來(lái)
# "i like like like java do you like a java" => 以下形式
# 1100111111101110001011111110111000101111111011100010100001011000101011
# 001100001011001000011001110111111101110001011010100001011000101
for i in s:
res += self.huffman_code_tab[i]
# 將得到的編碼字符串按八位進(jìn)行分割，將每八位轉(zhuǎn)換成一個(gè)int，并將int存放到列表中
code_list = []
i = 0
n = len(res)
while i < n:
num = int(res[i:i + 8], 2) # 將二進(jìn)制字符串轉(zhuǎn)換為整數(shù)
code_list.append(num)
i += 8
if i < n <= i + 8: # 已經(jīng)分割到了最后一部分，記錄該部分的長(zhǎng)度
self.last_char_len = n - i
return code_list
def huffman_decode(self, code_list) -> str:
"""
將哈夫曼編碼進(jìn)行解壓，得到一個(gè)可閱讀的字符串
:param code_list: 要解壓的哈夫曼編碼列表
:return: 解碼后的字符串
"""
# 將哈夫曼編碼列表轉(zhuǎn)換成對(duì)應(yīng)的二進(jìn)制字符串
# [415, 476, 95, 476, 95, 476, 80, 177, 345, 389, 400, 206, 254, 226, 212, 44, 5] =>
# 1100111111101110001011111110111000101111111011100010100001011000101011
# 001100001011001000011001110111111101110001011010100001011000101
code_str = '' # 存儲(chǔ)對(duì)應(yīng)的二進(jìn)制字符串
count = 0
n = len(code_list)
for i in code_list:
t = "{:08b}".format(i) # 將整數(shù)轉(zhuǎn)換為二進(jìn)制字符串
code_str += t
count += 1
if count == n - 1:
break
code_str += "{:0{k}b}".format(code_list[count], k=self.last_char_len)
# 將哈夫曼編碼表的鍵值互換
# 比如原來(lái)的是'a': '001' => 變成 '001': 'a'
code_tab = {}
for k, v in self.huffman_code_tab.items():
code_tab[v] = k
# 遍歷二進(jìn)制字符串
j = 0
i = 1
n = len(code_str)
res_code = '' # 解碼后的字符串
while i <= n:
t = code_str[j:i]
ch = code_tab.get(t)
if ch:
res_code += ch
j = i
i += 1
return res_code
s = "i like like like java do you like a java"
# s = "I love python hahha nihao"
huffman = HuffmanCode()
root_node = huffman.create_huffman_tree(s)
huffman.get_huffman_code_tab(root_node, '', '')
huffman_code_list = huffman.huffman_zip(s)
decode_str = huffman.huffman_decode(huffman_code_list)
print(decode_str)使用哈夫曼編碼壓縮文件的注意事項(xiàng)（代碼勝省略）
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-720689.html
到了這里，關(guān)于哈夫曼樹、哈夫曼編碼/解碼的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
