哈夫曼树（Huffman Tree）:
给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
哈夫曼编码解码过程：
编码：
1.输入字符串，通过getWeight()获取其权重即每个字符出现的次数并利用权重及字符生成Node结点，组成sourceData列表。
2.调用makeHuffman()方法，通过getmin2()函数可获得最小权重的两个字符，再让其形成父亲结点，并赋予左子结点右子结点，遍历sourceData完生成huffman结点，即哈夫曼树的根结点。
3.调用traverse()方法，将以huffman为根结点的树遍历形成列表。
4.调用strToHuffmanCode()方法，会去调用getCode()方法，会去根据huffman形成路径表route2，再跟原字符串一个一个字符进行比对，找到就添加其路径最终生成huffmancode
5.获取二进制表示的哈夫曼编码后，调用huffmanCodeBytes函数可以将二进制树转为带符号的十进制树，以八位二进制数为一组例如11010110,第一位为符号位，1表示负转为十进制数应将其余位取反并加1，再转为十进制数再*-1，就可以得到最终的十进制数。
解码：
调用decimalToBinary()函数将带符号的十进制数转为二进制数，再调用byteToBitString()比对route路径表 得到字符
代码实现
def getWeight(string):
#功能：文章中部分字母根据出现的概率规定权重，并让其生成Node对象
#1.统计字符串出现字符的次数，并与字符组成字典
sourceData = {x:string.count(x) for x in string }
print(sourceData)
# print("统计字符串出现字符的次数，并与字符组成字典",sourceData)
#2.将字符串转为携带自身字符及次数（权重）组成的元组的列表
#sourceData.items() ： 以列表形式返回可遍历的(键, 值) 元组数组。
#sourceData = sourceData.items() 也可以
sourceData = [(key,val) for key,val in sourceData.items()]
print(sourceData)
# print("以列表形式返回可遍历的(键, 值) 元组数组",sourceData)
#3.将每个元组中的第0个元素与第一个元素作为参数实例化Node对象
sourceData = [Node(x[0], x[1]) for x in sourceData]
print(sourceData)
# print("将每个元组中的第0个元素与第一个元素作为参数实例化Node对象",sourceData)
return sourceData
# 构成赫夫曼树的步骤：
# 1)从小到大进行排序,将每一个数据，每个数据都是一个节点，每个节点可以看成是一颗最简单的二叉树
# 2)取出根节点权值最小的两颗二叉树
# 3)组成一颗新的二叉树,该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
# 4)再将这颗新的二叉树，以根节点的权值大小再次排序，不断重复1-2-3-4的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树
class Node ():
def __init__(self,data,value):
self.value = value
self.data = data
self.left = None
self.right = None
# 定义获取列表中权重最大的两个节点的方法：
#1.定义 result 列表 带有两个value为正无穷的 Node 对象
#2.将权重最小的两个结点放入 result 中
#3.将其他结点扔到list2中，包括从result淘汰的结点
def getmin2(list):
result = [Node (None,float('inf')), Node (None,float('inf'))]
list2 = []
for i in range(len(list)):
if list[i].value < result[0].value:
if result[1].value != float('inf'):
list2.append(result[1])
result[0] , result[1] = list[i] , result[0]
elif list[i].value < result[1].value:
if result[1].value != float('inf'):
list2.append(result[1])
result[1] = list[i]
else:
list2.append(list[i])
# for i in range(len(result)):
# print("result",result[i].value)
# for i in range(len(list2)):
# print("list2",list2[i].value)
return result , list2
#定义生成哈夫曼树的方法：
#1.调用getmin2方法 获得 min2，分别为left、right结点，data 为剩下的结点
#2.创建一个father结点，并将left、right分别赋给 father.left father.right
#3.如果data里空了 说明没有剩余结点了 就可以返回 father了就是哈夫曼树
#4.如果data不是空的，那么就还得继续构造father结点， 并且记得把father结点扔到 data里面
#5.递归调用makeHuffman函数，也就继续调用getmin2函数，继续获得最小权重的两个结点
def makeHuffman(list):
min2, data = getmin2(list)
left = min2[0]
right = min2[1]
value = left.value + right.value
father = Node(None, value)
father.left = left
father.right = right
if data == []:
return father
data.append(father)
return makeHuffman(data)
# 递归方式实现广度优先遍历
#1.先将Node对象的list转为列表,只是把类型改了，list 的属性都还在
#2.将值一个一个扔到result里面，先扔根结点，
# 3.然后判断当前跟结点有没有左右子结点，有的话将根结点的左子结点，右子结点分别扔到nextlist里去
#4.没有的话判断当前根结点是是其父结点的右子结点吗，若是则判断nextlist是否为空，
# 4.1 若为空说明以当前结点为根结点的树遍历完了（没有叶子结点），可以返回了
# 4.2 若不为空，说明还没有遍历完，调整下参数以便继续遍历
#5.若不是右子结点，则将index + 1 使当前指向右子结点继续遍历
#6 全遍历完，返回result
#结果：
#[(None, 25), (None, 9), (None, 16), (None, 4), (None, 5), (None, 8), (None, 8), (None, 2), (None, 2), (None, 2),
# (' ', 3), ('o', 4), ('l', 4), (None, 4), (None, 4), ('v', 1), ('p', 1), ('y', 1), ('t', 1), ('h', 1), ('n', 1),
# ('e', 2), (None, 2), (None, 2), (None, 2), ('H', 1), ('W', 1), ('r', 1), ('d', 1), (',', 1), ('I', 1)]
def traverse(list,index= 0 ,nextlist = [] ,result = []):
if type(list) == Node:
list = [list]
result.append((list[index].data,list[index].value))
if list[index].left != None:
nextlist.append((list[index].left))
if list[index].right != None:
nextlist.append((list[index].right))
if index == len(list)-1:
#这里可输出哈夫曼树每一行的情况
# print( result)
if nextlist == []:
return
else:
list = nextlist
nextlist = []
index = 0
else:
index +=1
traverse(list,index,nextlist,result)
return result
# 直接用前序遍历将其输出
# def traverse(list):
# # if type(list) == Node:
# # list = [list]
# print(list.data,list.value)
# if list.left != None:
# traverse(list.left)
# if list.right != None:
# traverse(list.right)
#构建霍夫曼编码
#结果：
# [('v', '0000'), ('p', '0001'), ('y', '0010'), ('t', '0011'), ('h', '0100'), ('n', '0101'), (' ', '011'), ('o', '100'),
# ('l', '101'), ('e', '1100'), ('H', '11010'), ('W', '11011'), ('r', '11100'), ('d', '11101'), (',', '11110'), ('I', '11111')]
def getCode(node,code,route,route2):
#注意先后顺序。。。。。
route = route + code
#若该结点有数据，则必是叶子结点，因此只要没有数据就可以进行递归
if node.data == None:
getCode(node.left,'0',route,route2)
getCode(node.right,'1',route,route2)
#没数据就把当前数据及路径添加到route列表里
else:
# print(node.data,route,route2)
route2.append((node.data,route))
return route2
#字符串转哈夫曼编码：按照str的顺序
#结果：
# 11010110010110110001111011100111001011110111110111110111011000000110001100010010001101001000101
def strToHuffmanCode(huffman,string):
route = ''#临时存放路径
route2 = []#存放数据的路径
route = getCode(huffman,'',route,route2)
huffmancode =''
for j in range(len(string)):
for i in range(len(route)):
if route[i][0] == string[j]:
huffmancode += route[i][1]
return route,huffmancode
#二进制转带符号的十进制函数
def binaryToDecimal(string):
length = len(string)
#若传进来的二进制首位为1，要进行其余位数（取反，并+1，转为十进制数）并取相反数
if int(string)//pow(10,length-1) == 1:
binary_input = list(string)
binary_output = ''
#其余位数取反
for i in range(1,len(binary_input)):
if binary_input[i] == '0':
binary_input[i] = '1'
else:
binary_input[i] = '0'
#将其组合成字符串
for i in range(len(binary_input)):
binary_output += binary_input[i]
#对除首字符外的字符串转int型并+1 并转位十进制数 最后取相反数
length = len(binary_output)
if int(binary_output)//pow(10,length-1) == 1:
binary_output = binary_output[1:]
_,byte = bin((int(binary_output,2))+1).split('b')
byte = -1 * int(byte,2)
return (byte)
#若首位位0则找到第一个不位0的开始 计算其十进制数值
else:
for i in range(length):
if int(string[i]) != 0:
return (int((string[i:]),2))
#解决了如果有一个二进制数全为0 那就返回0
elif i==length-1:
return 0
#将霍夫曼编发二进制压缩成十进制
#结果：
#[-42, 91, 30, -25, 47, 125, -9, 96, 99, 18, 52, -59]
def huffmanCodeBytes(huffmancode):
huffmancodebytes = []
# print(len(huffmancode))
# huffmancodelist = [huffmancode]
for i in range(0,len(huffmancode),8):
if i != len(huffmancode)//8*8:
byte = binaryToDecimal(huffmancode[i:i+8])
huffmancodebytes.append(byte)
# 解决了 哈夫曼编码长度为8的倍数，编码表会多一个数字的问题
if len(huffmancode)%8 != 0:
byte = binaryToDecimal(huffmancode[i:])
# print(huffmancode[i:])
huffmancodebytes.append(byte)
return huffmancodebytes
# string = "Hello World,I love python"
string = input("请输入字符串（至少两个字符）:")
# print("原字符串：",string)
sourceData = getWeight(string)
huffman = makeHuffman(sourceData)
huffmantree = traverse(huffman)
print("哈夫曼树：",huffmantree)
route,huffmancode = strToHuffmanCode(huffman,string)
print("路径表：",route)
print("哈夫曼编码",huffmancode)
huffmancodebytes = huffmanCodeBytes(huffmancode)
print("编码表：",huffmancodebytes)
#解码
#将带符号十进制的数转为二进制的数再根据路径表（route）还原字符
#结果：
# 11010110
# 01011011
# 00011110
# 11100111...
def decimalToBinary(decimal,flag,bit= 8):
#flag == 1 说明不是最后一个数需要补码到8位
if flag == 1:
if decimal<0:
decimal = abs(decimal)
# 将十进制的a 转为2进制并-1，并切片，获取其二进制数
_,byte = (bin(int(bin(decimal),2)-1)).split('b')
# 补码，因为之前编码的时候1变成了0 这里0就丢了 ，因此得补码
byte2 = '1'
for i in range(len(byte),7):
byte2 += '1'
byte = list(byte)
# 取反码
for i in range(len(byte)):
if byte[i] == '1':
byte2 += '0'
else:
byte2 += '1'
else :
decimal = abs(decimal)
byte2 = '0'
_,byte = (bin(int(bin(decimal),2))).split('b')
for i in range(len(byte),7):
byte2 += '0'
byte2 += byte
#是最后一位数，如果需要补码就看还剩几位
else:
if decimal<0:
# 将十进制的a 转为2进制并-1，并切片，获取其二进制数
# print(bin(int(bin(decimal),2)))
_,byte = (bin(int(bin(decimal),2)+1)).split('b')
length = len(str(byte))
byte2 = '1'
for i in range(length,bit-1):
byte2 += '1'
byte = list(byte)
# 取反码
for i in range(len(byte)):
if byte[i] == '1':
byte2 += '0'
else:
byte2 += '1'
else :
decimal = abs(decimal)
byte2 = '0'
_,byte = (bin(int(bin(decimal),2))).split('b')
byte2 += byte
return byte2
# 将字节转为bit字符串再比对 route路径表 得到字符
#Hello World,I love python
def byteToBitString(huffmancodebytes,route,huffmancodelength):
bitstring = ''
character = ''
string = ''
#将字节转为bit字符串
# 结果：
#11010110010110110001111011100111001011110111110111110111011000000110001100010010001101001000101
for i in range(len(huffmancodebytes)):
#解决了 当哈夫曼编码长度为8的倍数的时候，最后一个数也当成之前的数去处理就可以了
if i != len(huffmancodebytes)-1 or huffmancodelength%8 == 0:
bitstring += decimalToBinary(int(huffmancodebytes[i]),1)
else:
bitstring += decimalToBinary(int(huffmancodebytes[i]),0,huffmancodelength%8)
#比对 route路径表 得到字符
print("哈夫曼解码",bitstring)
for i in range(len(bitstring)):
character += bitstring[i]
for j in range(len(route)):
if character == route[j][1]:
string += route[j][0]
character = ''
return string
string = byteToBitString(huffmancodebytes,route,len(huffmancode))
print("解码后字符串",string)
