哈夫曼樹（Huffman Tree）:

給定n個權(quán)值作為n個葉子結(jié)點，構(gòu)造一棵二叉樹，若該樹的帶權(quán)路徑長度達(dá)到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffman Tree)。哈夫曼樹是帶權(quán)路徑長度最短的樹，權(quán)值較大的結(jié)點離根較近。

哈夫曼編碼解碼過程：

編碼：
1.輸入字符串，通過getWeight()獲取其權(quán)重即每個字符出現(xiàn)的次數(shù)并利用權(quán)重及字符生成Node結(jié)點，組成sourceData列表。
2.調(diào)用makeHuffman()方法，通過getmin2()函數(shù)可獲得最小權(quán)重的兩個字符，再讓其形成父親結(jié)點，并賦予左子結(jié)點右子結(jié)點，遍歷sourceData完生成huffman結(jié)點，即哈夫曼樹的根結(jié)點。
3.調(diào)用traverse()方法，將以huffman為根結(jié)點的樹遍歷形成列表。
4.調(diào)用strToHuffmanCode()方法，會去調(diào)用getCode()方法，會去根據(jù)huffman形成路徑表route2，再跟原字符串一個一個字符進(jìn)行比對，找到就添加其路徑最終生成huffmancode
5.獲取二進(jìn)制表示的哈夫曼編碼后，調(diào)用huffmanCodeBytes函數(shù)可以將二進(jìn)制樹轉(zhuǎn)為帶符號的十進(jìn)制樹，以八位二進(jìn)制數(shù)為一組例如11010110,第一位為符號位，1表示負(fù)轉(zhuǎn)為十進(jìn)制數(shù)應(yīng)將其余位取反并加1，再轉(zhuǎn)為十進(jìn)制數(shù)再*-1，就可以得到最終的十進(jìn)制數(shù)。
解碼：
調(diào)用decimalToBinary()函數(shù)將帶符號的十進(jìn)制數(shù)轉(zhuǎn)為二進(jìn)制數(shù)，再調(diào)用byteToBitString()比對route路徑表 得到字符

代碼實現(xiàn)

def getWeight(string):
    #功能：文章中部分字母根據(jù)出現(xiàn)的概率規(guī)定權(quán)重，并讓其生成Node對象
    #1.統(tǒng)計字符串出現(xiàn)字符的次數(shù)，并與字符組成字典
    sourceData = {x:string.count(x) for x in string }
    print(sourceData)
    # print("統(tǒng)計字符串出現(xiàn)字符的次數(shù)，并與字符組成字典",sourceData)
    #2.將字符串轉(zhuǎn)為攜帶自身字符及次數(shù)（權(quán)重）組成的元組的列表
    #sourceData.items() ： 以列表形式返回可遍歷的(鍵, 值) 元組數(shù)組。
    #sourceData = sourceData.items() 也可以
    sourceData = [(key,val) for key,val in sourceData.items()]
    print(sourceData)
    # print("以列表形式返回可遍歷的(鍵, 值) 元組數(shù)組",sourceData)
    #3.將每個元組中的第0個元素與第一個元素作為參數(shù)實例化Node對象
    sourceData = [Node(x[0], x[1]) for x in sourceData]
    print(sourceData)
    # print("將每個元組中的第0個元素與第一個元素作為參數(shù)實例化Node對象",sourceData)
    return sourceData

# 構(gòu)成赫夫曼樹的步驟：
# 1)從小到大進(jìn)行排序,將每一個數(shù)據(jù)，每個數(shù)據(jù)都是一個節(jié)點，每個節(jié)點可以看成是一顆最簡單的二叉樹
# 2)取出根節(jié)點權(quán)值最小的兩顆二叉樹
# 3)組成一顆新的二叉樹,該新的二叉樹的根節(jié)點的權(quán)值是前面兩顆二叉樹根節(jié)點權(quán)值的和
# 4)再將這顆新的二叉樹，以根節(jié)點的權(quán)值大小再次排序，不斷重復(fù)1-2-3-4的步驟，直到數(shù)列中，所有的數(shù)據(jù)都被處理，就得到一顆赫夫曼樹
class Node ():
    def __init__(self,data,value):
        self.value = value
        self.data = data
        self.left = None
        self.right = None

# 定義獲取列表中權(quán)重最大的兩個節(jié)點的方法：
#1.定義 result 列表 帶有兩個value為正無窮的 Node 對象
#2.將權(quán)重最小的兩個結(jié)點放入 result 中
#3.將其他結(jié)點扔到list2中，包括從result淘汰的結(jié)點

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.調(diào)用getmin2方法 獲得 min2，分別為left、right結(jié)點，data 為剩下的結(jié)點
#2.創(chuàng)建一個father結(jié)點，并將left、right分別賦給 father.left father.right
#3.如果data里空了 說明沒有剩余結(jié)點了 就可以返回 father了就是哈夫曼樹
#4.如果data不是空的，那么就還得繼續(xù)構(gòu)造father結(jié)點， 并且記得把father結(jié)點扔到 data里面
#5.遞歸調(diào)用makeHuffman函數(shù)，也就繼續(xù)調(diào)用getmin2函數(shù)，繼續(xù)獲得最小權(quán)重的兩個結(jié)點
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)

# 遞歸方式實現(xiàn)廣度優(yōu)先遍歷
#1.先將Node對象的list轉(zhuǎn)為列表,只是把類型改了，list 的屬性都還在
#2.將值一個一個扔到result里面，先扔根結(jié)點，
# 3.然后判斷當(dāng)前跟結(jié)點有沒有左右子結(jié)點，有的話將根結(jié)點的左子結(jié)點，右子結(jié)點分別扔到nextlist里去
#4.沒有的話判斷當(dāng)前根結(jié)點是是其父結(jié)點的右子結(jié)點嗎，若是則判斷nextlist是否為空，
# 4.1 若為空說明以當(dāng)前結(jié)點為根結(jié)點的樹遍歷完了（沒有葉子結(jié)點），可以返回了
# 4.2 若不為空，說明還沒有遍歷完，調(diào)整下參數(shù)以便繼續(xù)遍歷
#5.若不是右子結(jié)點，則將index + 1 使當(dāng)前指向右子結(jié)點繼續(xù)遍歷
#6 全遍歷完，返回result
#結(jié)果：
#[(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)

#構(gòu)建霍夫曼編碼   
#結(jié)果：
# [('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
    #若該結(jié)點有數(shù)據(jù)，則必是葉子結(jié)點，因此只要沒有數(shù)據(jù)就可以進(jìn)行遞歸
    if node.data == None:
        getCode(node.left,'0',route,route2)
        getCode(node.right,'1',route,route2)
    #沒數(shù)據(jù)就把當(dāng)前數(shù)據(jù)及路徑添加到route列表里
    else:
        # print(node.data,route,route2)
        route2.append((node.data,route))
    return route2

#字符串轉(zhuǎn)哈夫曼編碼：按照str的順序
#結(jié)果：
# 11010110010110110001111011100111001011110111110111110111011000000110001100010010001101001000101
def strToHuffmanCode(huffman,string):
    route = ''#臨時存放路徑
    route2 = []#存放數(shù)據(jù)的路徑
    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

#二進(jìn)制轉(zhuǎn)帶符號的十進(jìn)制函數(shù)
def binaryToDecimal(string):
    length = len(string)
    #若傳進(jìn)來的二進(jìn)制首位為1，要進(jìn)行其余位數(shù)（取反，并+1，轉(zhuǎn)為十進(jìn)制數(shù)）并取相反數(shù)
    if int(string)//pow(10,length-1) == 1:
        binary_input = list(string)
        binary_output = ''
        #其余位數(shù)取反
        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]
        #對除首字符外的字符串轉(zhuǎn)int型并+1 并轉(zhuǎn)位十進(jìn)制數(shù) 最后取相反數(shù)
        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的開始 計算其十進(jìn)制數(shù)值
    else:
        for i in range(length):
            if int(string[i]) != 0:
                return (int((string[i:]),2))
            #解決了如果有一個二進(jìn)制數(shù)全為0  那就返回0 
            elif i==length-1:
                return 0
#將霍夫曼編發(fā)二進(jìn)制壓縮成十進(jìn)制
#結(jié)果：
#[-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的倍數(shù)，編碼表會多一個數(shù)字的問題
    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)

#解碼
#將帶符號十進(jìn)制的數(shù)轉(zhuǎn)為二進(jìn)制的數(shù)再根據(jù)路徑表（route）還原字符
#結(jié)果：
# 11010110
# 01011011
# 00011110
# 11100111...
def decimalToBinary(decimal,flag,bit= 8):
    #flag == 1 說明不是最后一個數(shù)需要補(bǔ)碼到8位
    if flag == 1:
        if decimal<0:
            decimal = abs(decimal)
            # 將十進(jìn)制的a 轉(zhuǎn)為2進(jìn)制并-1，并切片，獲取其二進(jìn)制數(shù)
            _,byte = (bin(int(bin(decimal),2)-1)).split('b')
            # 補(bǔ)碼，因為之前編碼的時候1變成了0  這里0就丟了 ，因此得補(bǔ)碼
            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
    #是最后一位數(shù)，如果需要補(bǔ)碼就看還剩幾位
    else:
        if decimal<0:
            # 將十進(jìn)制的a 轉(zhuǎn)為2進(jìn)制并-1，并切片，獲取其二進(jìn)制數(shù)
            # 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
# 將字節(jié)轉(zhuǎn)為bit字符串再比對 route路徑表 得到字符
#Hello World,I love python
def byteToBitString(huffmancodebytes,route,huffmancodelength):
    bitstring = ''
    character = ''
    string = ''
    #將字節(jié)轉(zhuǎn)為bit字符串
    # 結(jié)果：
    #11010110010110110001111011100111001011110111110111110111011000000110001100010010001101001000101
    for i in range(len(huffmancodebytes)):
        #解決了  當(dāng)哈夫曼編碼長度為8的倍數(shù)的時候，最后一個數(shù)也當(dāng)成之前的數(shù)去處理就可以了
        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)