香农编码 / Shannon Encoding

'''
All rights reserved by Junhong Liu
Reference books: 《信息论基础》
Completion time：2020-11-23
'''
#import numpy as np
#import pandas
#import time
import math
#import sys

#程序说明
print("-------------------<香农编码>程序说明-------------------")
print("Designed by Junhong Liu：All rights reserved")
print("Reference books: 《信息论基础》、百度百科-香农编码 (https://baike.baidu.com/item/%E9%A6%99%E5%86%9C%E7%BC%96%E7%A0%81/22353186?fr=aladdin)")
print("Completion time：2020-11-23")
print("Last modification time ：2020-11-23")
print("--------------------------------------------------------")
print("\n")

#*******录入数据
N_num = float(input("请输入需要编码字符个数："))
while(N_num <= 0 or (N_num % 1)):
    N_num = float(input("请输入正整数："))
N_num = int(N_num)

Dict = {}
probability = 1

while(N_num > 0):
    N_num = N_num-1
    print("\n","------还需输入",N_num,"编码字符信息------")
    print("\n","请输入一个编码字符名：")
    name = str(input())
    Dict.setdefault(name)
    print("请输入小于",probability,"的对应编码字符概率：")
    value = float(input())
    probability = probability - value
    Dict[name] = value

#print(Dict)
    
#按概率排序
Dict_order=sorted(Dict.items(),key=lambda x:x[1],reverse=True)

#print(Dict_order)
#sys.exit(0)

#编码算法
Q = 0  #累加概率
Shannon_dict = {}
for i in Dict_order:
    P = i[1]    #字符概率
    L = math.ceil(-math.log(P,2)) #码长
    Autoregressive_variable = 0
    num = Q
    word = ""   #码字
    while(Autoregressive_variable < L):
        if int(num) < int(2*num):
            word = word + '1'
            num = 2*num - int(2*num)
        else:
            word = word + '0'
            num = 2*num
        Autoregressive_variable = Autoregressive_variable+1
    Shannon_dict.setdefault(i[0])
    Shannon_dict[i[0]] = word
    Q = Q + P
    
print("Shannon_dict编码结果：",Shannon_dict)
#sys.exit(0)