费诺编码 / Ferno Encoding

此程序为费诺编码的Python实现,但此版本存在缺陷：每个编码符号出现的概率不能相同。该问题在第二个程序得到改进。

第一个程序

'''
All rights reserved by Liu Junhong
Reference books: 《信息论基础》
Completion time：2020-11-24
'''
#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/%E8%B4%B9%E8%AF%BA%E7%BC%96%E7%A0%81)")
print("Completion time：2020-11-24")
print("Last modification time ：2020-11-24")
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)

#编码算法
name = []
value = []
#code = []

#truncation = 0 #保存截断位置
for i in Dict_order:
    name.append(i[0])
    value.append(i[1])
    
Fano_dict_value = {}.fromkeys(value,'')
#print(name)
#print(value)

value_copy = [value]
value_copy_copy = []

while(len(value_copy)>0):
    for k in value_copy:
        if len(k) == 2:
            Fano_dict_value[k[0]] = Fano_dict_value[k[0]] + '0'
            Fano_dict_value[k[1]] = Fano_dict_value[k[1]] + '1'
        else:
            for i in range(len(k)):
                a = sum(k[:i])
                b = sum(k[i:])
                c = sum(k[:(i+1)])
                d = sum(k[(i+1):])
                if abs(a-b)<abs(c-d):
                    if i == 1:
                        Fano_dict_value[k[0]] = Fano_dict_value[k[0]] + '0'
                        value_copy_copy.append(k[1:])
                        for h in k[1:]:
                            Fano_dict_value[h] = Fano_dict_value[h] + '1'
                    else:
                        value_copy_copy.append(k[:i])
                        value_copy_copy.append(k[i:])
                        for j in k[:i]:
                            Fano_dict_value[j] = Fano_dict_value[j] + '0'
                        for h in k[i:]:
                            Fano_dict_value[h] = Fano_dict_value[h] + '1'
                    break
    value_copy = value_copy_copy
    value_copy_copy = []

#输出结果
Fano_dict = dict(zip(name,Fano_dict_value.values()))
print(Fano_dict)

第二个程序

'''
All rights reserved by Liu Junhong
Reference books: 《信息论基础》
Completion time：2020-11-24
'''
import math

#程序说明
print("-------------------<费诺编码>程序说明-------------------")
print("Designed by 刘俊宏：All rights reserved")
print("Reference books: 《信息论基础》、百度百科-费诺编码 (https://baike.baidu.com/item/%E8%B4%B9%E8%AF%BA%E7%BC%96%E7%A0%81)")
print("Completion time：2020-11-24")
print("Last modification time ：2020-11-25")
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


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

#编码算法
name = []
value = []
for i in Dict_order:
    name.append(i[0])
    value.append(i[1])
    
Fano_dict = {}.fromkeys(name,'')

value_copy = [value]
value_copy_copy = []
name_copy = [name]
name_copy_copy = []
while(len(value_copy)>0):
    for k in range(len(value_copy)):
        if len(value_copy[k]) == 2:
            Fano_dict[name_copy[k][0]] = Fano_dict[name_copy[k][0]] + '0'
            Fano_dict[name_copy[k][1]] = Fano_dict[name_copy[k][1]] + '1'
        else:
            for i in range(len(value_copy[k])):
                a = sum(value_copy[k][:i])
                b = sum(value_copy[k][i:])
                c = sum(value_copy[k][:(i+1)])
                d = sum(value_copy[k][(i+1):])
                if abs(a-b)<abs(c-d):
                    if i == 1:
                        Fano_dict[name_copy[k][0]] = Fano_dict[name_copy[k][0]] + '0'
                        value_copy_copy.append(value_copy[k][1:])
                        name_copy_copy.append(name_copy[k][1:])
                        for h in name_copy[k][1:]:
                            Fano_dict[h] = Fano_dict[h] + '1'
                    else:
                        value_copy_copy.append(value_copy[k][:i])
                        value_copy_copy.append(value_copy[k][i:])
                        name_copy_copy.append(name_copy[k][:i])
                        name_copy_copy.append(name_copy[k][i:])
                        for j in name_copy[k][:i]:
                            Fano_dict[j] = Fano_dict[j] + '0'
                        for h in name_copy[k][i:]:
                            Fano_dict[h] = Fano_dict[h] + '1'
                    break
    value_copy = value_copy_copy
    name_copy = name_copy_copy
    value_copy_copy = []
    name_copy_copy = []

#输出结果
print(Fano_dict)