动态规划之最优二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
# -*- coding: UTF-8 -*- #
'''
@filename: Dynamic_magic_compression.py
@author:JIN
@time:2022-10-31
'''
import math
def Compress(P,n):
    global Lmax,header
    Lmax=256
    header=11
    S = [0 for i in range(n+1)]
    b = [0 for i in range(n+1)]
    L = [0 for i in range(n+1)]
    for i in range(1,n+1):
        b[i]=math.ceil(math.log(P[i-1]+1,2))   #表示第i个像素灰度的二进制位数
        bmax=b[i]                                #每次将当前循环的那个像素设为位数最大值
        S[i]=S[i-1]+bmax                         #S[i] =min{S[i - j] + j * bmax}中第一种情况，
                                                # 前面的像素点为一段，刚刚循环添入耳像素点独自为一组
        L[i]=1                                   #表示当前第i个像素 所在的段  中有只有一个数字 就是他自己

        for j in range(2,min(range(i,256))+1):    #循环其他S[i] =min{S[i - j] + j * bmax}情况
           # print("第",i,"下",i-j,"P[i-j]为",P[i-j])
            if bmax <=math.ceil(math.log(P[i-j]+1,2)):
                #print("bmax", i, "下", i - j, "P[i-j]为", P[i - j])
                bmax=math.ceil(math.log(P[i-j]+1,2))
            #print(bmax,"%%%%", i, "下", i - j)
           # print(S[i])
          #  temp=S[i-j]+j*bmax
            #print(temp)
            if S[i] >= S[i-j]+j*bmax:
                S[i] =S[i - j] + j * bmax     #如果循环下其他情况的S[i]更小那么取那个最小的
                L[i]= j                    #当前第i个数所在段 有几个数字
                b[i]= bmax           #我加，跟新当前组，所需的存储位数
        S[i]=S[i]+header    #每次循环结束 更新S[i]存放前i个数字的最优处理方式
    return L,S
def Traceback(n,L):
    j=1      #j用来追踪段数
    C=[0 for i in range(n)]
    while n!=0:
        C[j]=L[n]   #
        n=n-L[n]
        j=j+1
    return C,j

if __name__ == '__main__':
    numb1 = input('请输入图像灰度序列').split()
    P = list(map(int, numb1))
    n=len(P)#图像灰度序列个数
    #print(P)
    L,S=Compress(P,n)
    #print(L)
    C,j=Traceback(n, L)
    print("图像压缩后最小的空间为",S[-1])
    print("将原灰度分为了",j-1,"段序列")
    for i in range(j-1):
        num=C[j-1-i]
        print("段长为",num)