Python實作哈夫曼編碼，包含畫出二叉樹，可視化操作界面以及編碼的傳輸與接收
- 包含功能：
- 部分功能展示：
- PS:
- 原始碼：
包含功能：
1.哈夫曼編碼文本
2.matplotlib包畫出哈弗曼樹
3.tkinter實作可視化操作頁面
4.簡單的socket實作編碼傳輸功能
部分功能展示：
用matplotlib可以進行區域放大，右下角節點的顯示效果同樣很好！
PS:
1. 此專案使用的模板只包含大寫字母與空格，如需要解碼其他內容，
請自行添加模板串列，
2. py版本為3.7，matplotlib為3.3.3
3. 監聽代碼按鈕按下去之后點別的地方代碼會直接去世，
應該加一個執行緒或者用別的方法可以解決，
4. 個人覺得用matplotlib畫二叉樹影像的演算法挺值得看的，網上有關內容并不多，
(通過調整演算法中的引數理論上可以避免二叉樹隨深度增加而造成間距太小而重合）
5. 本人為初學者，代碼寫的有很多不規范的地方，敬請指正！
6.轉載請標明出處，
原始碼：
1.編碼功能實作及畫圖功能實作
import matplotlib.pyplot as plt
from matplotlib.patches import Circle
class HTcoder():
def __init__(self):
# 最終模板
self.CharList = [' ', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O',
'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']
self.list0 = [186, 64, 13, 22, 32, 103, 21, 15, 47, 57, 1, 5, 32, 20, 57, 63,
15, 2, 48, 51, 80, 23, 8, 18, 1, 16, 1]
self.length = len(self.list0) # 獲得初始陣列長度
# 初始化陣列
self.list = self.initData(self.length)
# 進行計算,獲得哈夫曼表
self.list = self.HToperate(self.list, self.length)
# 獲得編碼陣列
self.CodeList = self.CalCode(self.list, self.length)
# 獲得編碼表
self.CODELIST = self.GetEncodeList(self.CharList, self.CodeList)
self.deepth = self.findTreedeepth(self.CodeList)
def findMin(self,list):
min = []
temp = 0
tempindex = 0
flag = 0
# 從未使用過的元素中找出第一個元素的位置，以便下一個找最小值回圈的初始比較
for index, i in enumerate(list):
# 跳過第一次回圈.之后的同理
if flag == 0:
flag = flag + 1
continue
if i[4] == 0:
temp = i[0]
tempindex = index
break
# 重置跳過第一次回圈的標志
flag = 0
#找到最小值，記錄位置和值
for index, i in enumerate(list):
if flag == 0:
flag = flag + 1
continue
if i[4] == 0 and i[0] != 0:
if temp > i[0]: #可能會出現權值一樣找不到最小值的問題
temp = i[0]
tempindex = index
min.append(temp)
min.append(tempindex)
list[tempindex][4] = 1
return min, list
def findIndex(self,list,element):
for index, item in enumerate(list):
if item == element:
return index
def CalCode (self,list,length):
res = []
for i in range(length):
#每一次for回圈 計算一個元素的編碼（從該元素所在的葉子結點往上，直到根節點）
code = []
p = list[i+1]
while p[1]!=0:
if (list[p[1]][2] == self.findIndex(list,p)):
#表示左子樹，回傳值：0
code.append(0)
elif (list[p[1]][3] == self.findIndex(list,p)):
#表示右子樹，回傳值：1
code.append(1)
p = list[p[1]]
code.reverse()
res.append(code)
return res
def initData(self,length1):
list = []
# 創建的二維陣列分別表示 權重 父母節點index 左節點index 右節點index 是否被使用過的標識（1表示已被使用）
for i in range(length1 + 1):
list.append([])
for j in range(5):
list[i].append(0)
# 初始化資料
for i in range(length1):
list[i + 1][0] = round(self.list0[i] * 100)
return list
def delSame(self,list):
for i in range(len(list)):
for j in range(i+1,len(list)):
if list[j] == list[i]:
list[j][4] = list[j][4] + 1
return list
def HToperate(self,list,length1):
# 回圈次數 ：7次
# n-1
cout = length1 - 1
while cout > 0:
# 回傳串列中目前未被使用過的資料的最小值的 值 和 下標
min1, list = self.findMin(list)
min2, list = self.findMin(list)
list.append([(min1[0] + min2[0]), 0, min1[1], min2[1], 0])
list[min1[1]][1] = length1 + 1
list[min2[1]][1] = length1 + 1
length1 = length1 + 1
cout = cout - 1
list = self.delSame(list)
return list
def GetEncodeList(self,Char,Code):
res = []
for i in range(len(Code)):
res.append([])
res[i].append(Char[i])
res[i].append(Code[i])
return res
def EnCode(self,content,code):
CODERES = ''
for i in range(len(content)):
for j in range(len(code)):
temp = ''
if content[i] == code[j][0]:
for k in code[j][1]:
temp = temp + str(k)
CODERES = CODERES + temp
break
return CODERES
def DeCode(self,content,code):
res = ''
i = 0
while i < (len(content)):
for j in code:
flag = 0
for kindex,k in enumerate(j[1]):
#該步驟判斷十分重要，當解碼到最后一個字符時，該字符編碼長度可能比編碼表里用來對比的短，
#就會造成超出content長度的情況，系統直接報錯
if (i+kindex) > (len(content)-1):
break
if content[i+kindex] == str(k):
flag = flag + 1
if flag == kindex+1:
res = res + j[0]
i = i+kindex
break
i = i + 1
return res
#該函式是為了查找二叉樹深度，方便畫圖
def findTreedeepth(self,codelist):
deepth = len(codelist[0])
for i in codelist:
if len(i)>deepth:
deepth = len(i)
return deepth
def drawTree(self,data,deepth):
fig, axes = plt.subplots(nrows=1, ncols=1, figsize=(8, 10))
axes.set(xlim=[0, 2000], ylim=[0, 500], title='HT-BinTree')
tree_deepth = deepth + 1 # 深度等于最大編碼長度+1
height = round(500 / (1 + tree_deepth))
Radius = 5
#因為該函式用到了函式外的變數，所以要定義在該函式里
def findXloc(node, x_loc, y_loc, isleft):
if node[0] == 0:
return
# 求當前節點所在深度
deeptemp = round((500 - y_loc) / height)
# 求出按照深度計算得來的每一行的元素之間的寬度的 1/2
width = round(2000 / (1 + 2 ** (deeptemp - 1)) / 2 + deeptemp*0.5)
# 求父母節點連線坐標
line_loc0x = x_loc
line_loc0y = y_loc + height - Radius
# 求該節點與父母節點連線點的坐標
line_loc1y = y_loc + Radius
# 判斷是左子樹還是右子樹
if isleft == 1:
x_loc = round(x_loc - width * 1.3)
elif isleft == -1:
pass
else:
x_loc = round(x_loc + width * 1.3)
# 求該節點與父母節點連線點的坐標
line_loc1x = x_loc
list_tree.append([x_loc, y_loc, round(node[0] / 100), line_loc0x, line_loc0y, line_loc1x, line_loc1y])
findXloc(data[node[2]], x_loc, y_loc - height, 1)
findXloc(data[node[3]], x_loc, y_loc - height, 0)
list_tree = [] # 每一個串列元素中所含元素代表含義分別為
# 節點x坐標， 節點y坐標， 節點值， 該節點連線點坐標x,y，該節點連到父母節點的點坐標x,y
len1 = len(data)
findXloc(data[len1-1], 1000, 500 - height, -1) # -1表示根節點
for i in range(len(list_tree)):
circle = Circle(xy=(list_tree[i][0], list_tree[i][1]), radius=Radius, alpha=0.2, color='b')
axes.add_patch(circle)
plt.text(list_tree[i][0] - 2, list_tree[i][1] - 5, list_tree[i][2], weight="bold", color="0")
if i != 0:
plt.plot([list_tree[i][3], list_tree[i][5]], [list_tree[i][4], list_tree[i][6]], linewidth=0.5)
# 計算線上中點坐標
x1 = (list_tree[i][3] + list_tree[i][5]) / 2
y1 = (list_tree[i][4] + list_tree[i][6]) / 2
if list_tree[i][3] < list_tree[i][5]:
plt.text(x1, y1, 1, weight="bold", color="r")
else:
plt.text(x1, y1, 0, weight="bold", color="r")
plt.show()
def Doencode(self,CODELIST):
# 哈夫曼編譯
file = open('./text.txt', "r")
TEXT = file.read()
CODERES = self.EnCode(TEXT, CODELIST)
file.close()
file1 = open('./output.txt', 'w')
file1.write(CODERES)
print("編碼成功，結果保存在output.txt中！")
file1.close()
def Dodecode(self,CODELIST):
# 哈夫曼解碼
file = open('./output.txt', "r")
CODE = file.read()
TEXTRES = self.DeCode(CODE, CODELIST)
file.close()
file1 = open('./text.txt', 'w')
file1.write(TEXTRES)
print("解碼成功，結果保存在text.txt中！")
file1.close()
#操作界面呼叫的介面
def useEncode(self):
self.Doencode(self.CODELIST)
def useDecode(self):
self.Dodecode(self.CODELIST)
def useDrawTree(self):
self.drawTree(self.list, self.deepth)
# 該部分代碼做了分裝，若想要單獨呼叫，請自行修改部分函式
2.UI實作及通信功能實作：
from tkinter import *
import socket
from function_body import HTcoder
from tkinter import messagebox
root = Tk() # 創建視窗物件的背景色
root.title('哈夫曼編/解碼器v1.0---by HuDX')
root.geometry('800x600+350+150')
# root.minsize(800,600)
root["bg"] = "gray"
root.attributes("-alpha",1)
#實體功能類
a = HTcoder()
def ClickEncodeBTN():
text = ety1.get('0.0','end')
file1 = open('./text.txt', 'w')
file1.write(text)
file1.close()
a.useEncode()
file = open('./output.txt', "r")
codes = file.read()
file.close()
ety2.delete('1.0', 'end')
ety2.insert('end', codes)
messagebox.showinfo('提示', '解碼成功！\n輸入文本和輸出編碼會同步保存至該專案根目錄的text.txt和output.txt中！')
def ClickDecodeBTN():
codes = ety2.get('0.0','end')
file1 = open('./output.txt', 'w')
file1.write(codes)
file1.close()
a.useDecode()
file = open('./text.txt', "r")
text = file.read()
file.close()
ety1.delete('1.0', 'end')
ety1.insert('end', text)
messagebox.showinfo('提示', '解碼成功！\n輸入編碼和輸出文本會同步保存至該專案根目錄的output.txt和text.txt中！')
def ClickDrawBTN():
a.useDrawTree()
def ClickSendBTN():
flag = messagebox.askquestion(title='警告',message='發送編碼須確保接收方打開監聽按鈕,\n'
'是否繼續發送？')
if flag == 'yes':
codes = ety2.get('0.0','end')
IP = ety3.get('0.0','end')
IP = IP[:(len(IP)-1)] #去掉IP后面的一個回車符號
udp_socket = socket.socket(socket.AF_INET, socket.SOCK_DGRAM)
udp_socket.sendto(codes.encode(), (IP, 6666))
udp_socket.close()
messagebox.showinfo('提示', '發送成功！')
else:
pass
def ClickRecvBTN():
udp_socket = socket.socket(socket.AF_INET, socket.SOCK_DGRAM)
udp_socket.bind(('', 6666))
recv_data, ip_port = udp_socket.recvfrom(1024)
codes = recv_data.decode()
ety2.delete('1.0', 'end')
ety2.insert('end', codes)
messagebox.showinfo('提示', '來自ip：', ip_port, '的編碼接收成功！')
udp_socket.close()
bt1 = Button(root, text='編碼', activebackground='red',command=ClickEncodeBTN)
bt1.place(x=675,y=285)
bt2 = Button(root, text='解碼', activebackground='red',command=ClickDecodeBTN)
bt2.place(x=725,y=285)
bt3 = Button(root, text='顯示哈夫曼二叉樹',activebackground='red',command=ClickDrawBTN)
bt3.place(x=550,y=285)
bt4 = Button(root, text='發送編碼',activebackground='red',command=ClickSendBTN)
bt4.place(x=420,y=285)
bt5 = Button(root, text='開啟監聽',activebackground='red',command=ClickRecvBTN)
bt5.place(x=480,y=285)
ety1 = Text(root, bg='white',width=107,height=19)
ety1.place(x=25,y=25)
ety2 = Text(root, bg='white',width=107,height=19)
ety2.place(x=25,y=325)
ety3 = Text(root, bg='white',width=15,height=1)
ety3.place(x=265,y=292)
ety4 = Text(root, bg='white',width=5,height=1)
ety4.insert('end', 6666)
ety4.place(x=380,y=292)
title3 = Label(root, text="輸入需要發送的ip和埠號：")
title3.place(x=100,y=290)
title1 = Label(root, text="文本：")
title1.place(x=26,y=2)
title2 = Label(root, text="編碼：")
title2.place(x=26,y=300)
root.mainloop() # 進入訊息回圈
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/236601.html
標籤：python
上一篇：基于 Google Colab 的 mask rcnn 訓練自己的資料集（以實體分割為例）
下一篇：連夜優化的一段代碼，請求指教