密码学原理精解【8】

概率分布

• bayes概率
  $$\begin{gathered} Pr(X=x)为明文的先验概率 \\ Pr(Y=y)为密文的先验概率 \\ Pr(K=k)为密钥的先验概率 \\ C(K)=(e_k(x)|k\in P),P为明文，C(K)为密文 \\ \forall y\in C,Pr(Y=y)={\Sigma }_{k:y\in C(K)}Pr(K=k)Pr(x=d_k(y)) \\ Pr(Y=y|X=x)={\Sigma }_{k:x=d_k(y)}Pr(K=k) \\ 所有先验概率准备完毕，下面是bayes概率了 \\ Pr(X=x|Y=y)=\frac{Pr(X=x)\times {\Sigma }_{k:x=d_k(y)}Pr(K=k)}{{\Sigma }_{k:y\in C(k)}Pr(K=k)Pr(x=d_x(y))} \end{gathered}$$

• 例子
  设明文集合 P = { 1 , 2 , 3 , 4 , 5 } ，密文集合 C = { a , b , c , d , e } ∀ i ∈ P , P r ( i ) = 1 2 i , P r ( 1 ) = 1 2 , P r ( 2 ) = 1 4 , P r ( 3 ) = 1 6 , . . . K = { K 1 , K 2 } ， P r ( K i ) = 1 − 1 2 i , P r ( K 1 ) = 1 2 , P r ( K 2 ) = 3 4 0 ≤ j < 5 , j ∈ Z e K i ( P j ) = C ( j + i + 1 ) m o d 5 e K 1 ( 1 ) = c , e K 1 ( 2 ) = d , e K 1 ( 3 ) = e , e K 1 ( 4 ) = a , e K 1 ( 5 ) = b e K 2 ( 1 ) = d , e K 2 ( 2 ) = e , e K 2 ( 3 ) = a , e K 2 ( 4 ) = b , e K 2 ( 5 ) = c 1. C 概率分布 P r ( a ) = ( 1 / 2 ) × ( 1 / 8 ) + ( 3 / 4 ) × ( 1 / 6 ) = 3 / 16 P r ( b ) = ( 1 / 2 ) × ( 1 / 10 ) + ( 3 / 4 ) × ( 1 / 8 ) P r ( c ) = ( 1 / 2 ) × ( 1 / 2 ) + ( 3 / 4 ) × ( 1 / 10 ) P r ( d ) = ( 1 / 2 ) × ( 1 / 4 ) + ( 3 / 4 ) × ( 1 / 2 ) P r ( e ) = ( 1 / 2 ) × ( 1 / 4 ) + ( 3 / 4 ) × ( 1 / 6 ) 2. 给定密文后，明文空间上条件概率分布为 P r ( X = x ∣ Y = y ) P r ( 1 ∣ a ) = 0 P r ( 2 ∣ a ) = 0 . . . . P r ( 4 ∣ a ) = P r ( X = 4 ) × P r ( K = K 1 ) P r ( Y = a ) = 1 / 8 × 1 / 2 3 / 16 = 1 3 . . . . 3. 密码机制具有完善保密性 < = 对于任意 x ∈ P , y ∈ C ， P r ( x ∣ y ) = P r ( x ) 上面例子的密码机制不具有完善保密性 : P r ( 4 ∣ a ) = 1 / 3 , P ( 4 ) = 1 / 8 设明文集合P=\{1,2,3,4,5\}，密文集合C=\{a,b,c,d,e\} \\ \forall i \in P,Pr(i)=\frac 1 {2i},Pr(1)=\frac 1 2,Pr(2)= \frac 1 4,Pr(3)=\frac 1 6,... \\K=\{K_1,K_2\}，Pr(K_i)=1-\frac 1 {2i},Pr(K_1)=\frac 1 2,Pr(K_2) =\frac 3 4 \\0 \le j < 5,j \in Z \\e_{K_i}(P_j)=C_{(j+i+1) mod5} \\e_{K_1}(1)=c,e_{K_1}(2)=d,e_{K_1}(3)=e,e_{K_1}(4)=a,e_{K_1}(5)=b \\e_{K_2}(1)=d,e_{K_2}(2)=e,e_{K_2}(3)=a,e_{K_2}(4)=b,e_{K_2}(5)=c \\1.C概率分布 \\Pr(a)=(1/2) \times (1/8)+(3/4)\times(1/6)=3/16 \\Pr(b)=(1/2)\times(1/10)+(3/4)\times(1/8) \\Pr(c)=(1/2)\times(1/2)+(3/4)\times(1/10) \\Pr(d)=(1/2)\times(1/4)+(3/4)\times(1/2) \\Pr(e)=(1/2)\times(1/4)+(3/4)\times(1/6) \\2.给定密文后，明文空间上条件概率分布为Pr(X=x|Y=y) \\Pr(1|a)=0 \\Pr(2|a)=0 \\.... \\Pr(4|a)=\frac {Pr(X=4)\times Pr(K=K_1)} {Pr(Y=a)}=\frac {1/8 \times1/2}{3/16}=\frac 1 3 \\.... \\3.密码机制具有完善保密性<=对于任意x \in P,y \in C，Pr(x|y)=Pr(x) \\上面例子的密码机制不具有完善保密性:Pr(4|a)=1/3,P(4)=1/8 设明文集合P={1,2,3,4,5}，密文集合C={a,b,c,d,e}∀i∈P,Pr(i)=2i1​,Pr(1)=21​,Pr(2)=41​,Pr(3)=61​,...K={K1​,K2​}，Pr(Ki​)=1−2i1​,Pr(K1​)=21​,Pr(K2​)=43​0≤j<5,j∈ZeKi​​(Pj​)=C(j+i+1)mod5​eK1​​(1)=c,eK1​​(2)=d,eK1​​(3)=e,eK1​​(4)=a,eK1​​(5)=beK2​​(1)=d,eK2​​(2)=e,eK2​​(3)=a,eK2​​(4)=b,eK2​​(5)=c1.C概率分布Pr(a)=(1/2)×(1/8)+(3/4)×(1/6)=3/16Pr(b)=(1/2)×(1/10)+(3/4)×(1/8)Pr(c)=(1/2)×(1/2)+(3/4)×(1/10)Pr(d)=(1/2)×(1/4)+(3/4)×(1/2)Pr(e)=(1/2)×(1/4)+(3/4)×(1/6)2.给定密文后，明文空间上条件概率分布为Pr(X=x∣Y=y)Pr(1∣a)=0Pr(2∣a)=0....Pr(4∣a)=Pr(Y=a)Pr(X=4)×Pr(K=K1​)​=3/161/8×1/2​=31​....3.密码机制具有完善保密性<=对于任意x∈P,y∈C，Pr(x∣y)=Pr(x)上面例子的密码机制不具有完善保密性:Pr(4∣a)=1/3,P(4)=1/8

哈夫曼编码实现

julia官方文档建议的变量命名规范：

• 变量名用小写。 单词用下划线"_"分隔，建议只对复杂的名称使用。
• 类型、模块的名称以大写字母开头，单词以驼峰方式间隔。
• 函数名和宏名用不带下划线的小写字母。
• 改变输入参数值的函数，函数名以’!'为结尾

julia源码

mutable struct NodeData
    data::String
    data_pr::Real
    bm::Union{String,Nothing}
end

mutable struct TreeNode
    data::NodeData
    left::Union{TreeNode, Nothing}
    right::Union{TreeNode, Nothing}
end

 

# 插入节点的函数
function newnode(data::String,data_pr::Real,bm=nothing)
    ndata=NodeData(data,data_pr,bm)
    tnode=TreeNode(ndata,nothing,nothing)
    return tnode
end
function insertleft(node::TreeNode, leftsubnode::TreeNode)
        node.left=leftsubnode
end
function insertright(node::TreeNode, rightsubnode::TreeNode)
        node.right=rightsubnode
end


function printPaths(node::TreeNode, nodetype::String="L",path = [])  

    if node == nothing  

        return  

    end  
    if nodetype=="L"
       node.data.bm="0"
    else
       node.data.bm="1"
    end

      

    # 将当前节点的值添加到路径中  

    push!(path, node.data)  

      

    # 如果是叶节点，则打印路径  

    if node.left == nothing && node.right == nothing  

        println("===",path,"===")  

    else  

        # 递归遍历左子树和右子树  

        printPaths(node.left,"L",path)  

        printPaths(node.right,"R",path)  

    end  

      

    # 回溯，移除当前节点值  

    pop!(path)  

end


# 使用
strtxt="

Fedora Workstation is Fedora’s official desktop edition. It provides a powerful, easy to use desktop experience. Workstation is intended to be a great general purpose desktop. It also aims to be a fantastic platform for software developers.

Workstation is part of the Fedora project. As such, it shares components, tools, and processes with other Fedora Editions and Spins. However, Workstation is also an independent project, which is able to make its own design and technical decisions, and is a distinct product of its own.

The Workstation Working Group is the team that has responsibility for Fedora Workstation. However, Workstation wouldn’t be possible without the hard work of teams and individuals across the entire Fedora community.
"
#计算概率
word_pr=Dict{String,Real}()
for i in eachindex(strtxt)
     global word_pr
     if haskey(word_pr,string(strtxt[i]))
         word_pr[string(strtxt[i])]+=1
     else
         word_pr[string(strtxt[i])]=1
     end
end
allwordcount=sum(values(word_pr))
map!(x->x/allwordcount, values(word_pr))

nodelist=Dict{String,TreeNode}()
#构建优先队列
wordslist=collect(word_pr)

sort!(wordslist,by=x->x[2])


while length(wordslist)>1
    global nodelist
    global wordslist
    #从优先队列中取出两个频率最小的节点,创建一个新的父节点，其频率为这两个子节点频率之和。
    c1=popfirst!(wordslist)
    c2=popfirst!(wordslist)
    
    if !haskey(nodelist,c1[1])
        nodelist[c1[1]]=newnode(c1[1],c1[2])
    end
    if !haskey(nodelist,c2[1])
        nodelist[c2[1]]=newnode(c2[1],c2[2])
    end
    #将新节点作为这两个子节点的父节点，并将新节点插入回优先队列。
    if !haskey(nodelist,c1[1]*c2[1])
        parentnode=newnode(c1[1]*c2[1],c1[2]+c2[2])
        nodelist[c1[1]*c2[1]]=parentnode
        insertleft(parentnode,nodelist[c1[1]])
        insertright(parentnode,nodelist[c2[1]])
    end
    push!(wordslist,c1[1]*c2[1]=>c1[2]+c2[2])

    sort!(wordslist,by=x->x[2])
end 


printPaths(nodelist[wordslist[1][1]])




















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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150

===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("oh,mg’jHITxAE.unrvGSyfpa", 0.4008042895442359, "0"), NodeData("oh,mg’jHITxAE.u", 0.17828418230563003, "0"), NodeData("o", 0.08847184986595175, "0")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("oh,mg’jHITxAE.unrvGSyfpa", 0.4008042895442359, "0"), NodeData("oh,mg’jHITxAE.u", 0.17828418230563003, "0"), NodeData("h,mg’jHITxAE.u", 0.08981233243967829, "1"), NodeData("h,m", 0.04289544235924933, "0"), NodeData("h", 0.021447721179624665, "0")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("oh,mg’jHITxAE.unrvGSyfpa", 0.4008042895442359, "0"), NodeData("oh,mg’jHITxAE.u", 0.17828418230563003, "0"), NodeData("h,mg’jHITxAE.u", 0.08981233243967829, "1"), NodeData("h,m", 0.04289544235924933, "0"), NodeData(",m", 0.021447721179624665, "1"), NodeData(",", 0.010723860589812333, "0")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("oh,mg’jHITxAE.unrvGSyfpa", 0.4008042895442359, "0"), NodeData("oh,mg’jHITxAE.u", 0.17828418230563003, "0"), NodeData("h,mg’jHITxAE.u", 0.08981233243967829, "1"), NodeData("h,m", 0.04289544235924933, "0"), NodeData(",m", 0.021447721179624665, "1"), NodeData("m", 0.010723860589812333, "1")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("oh,mg’jHITxAE.unrvGSyfpa", 0.4008042895442359, "0"), NodeData("oh,mg’jHITxAE.u", 0.17828418230563003, "0"), NodeData("h,mg’jHITxAE.u", 0.08981233243967829, "1"), NodeData("g’jHITxAE.u", 0.04691689008042896, "1"), NodeData("g’jHITxAE", 0.021447721179624665, "0"), NodeData("g’j", 0.010723860589812333, "0"), NodeData("g", 0.005361930294906166, "0")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("oh,mg’jHITxAE.unrvGSyfpa", 0.4008042895442359, "0"), NodeData("oh,mg’jHITxAE.u", 0.17828418230563003, "0"), NodeData("h,mg’jHITxAE.u", 0.08981233243967829, "1"), NodeData("g’jHITxAE.u", 0.04691689008042896, "1"), NodeData("g’jHITxAE", 0.021447721179624665, "0"), NodeData("g’j", 0.010723860589812333, "0"), NodeData("’j", 0.005361930294906166, "1"), NodeData("’", 0.002680965147453083, "0")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("oh,mg’jHITxAE.unrvGSyfpa", 0.4008042895442359, "0"), NodeData("oh,mg’jHITxAE.u", 0.17828418230563003, "0"), NodeData("h,mg’jHITxAE.u", 0.08981233243967829, "1"), NodeData("g’jHITxAE.u", 0.04691689008042896, "1"), NodeData("g’jHITxAE", 0.021447721179624665, "0"), NodeData("g’j", 0.010723860589812333, "0"), NodeData("’j", 0.005361930294906166, "1"), NodeData("j", 0.002680965147453083, "1")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("oh,mg’jHITxAE.unrvGSyfpa", 0.4008042895442359, "0"), NodeData("oh,mg’jHITxAE.u", 0.17828418230563003, "0"), NodeData("h,mg’jHITxAE.u", 0.08981233243967829, "1"), NodeData("g’jHITxAE.u", 0.04691689008042896, "1"), NodeData("g’jHITxAE", 0.021447721179624665, "0"), NodeData("HITxAE", 0.010723860589812333, "1"), NodeData("HI", 0.005361930294906166, "0"), NodeData("H", 0.002680965147453083, "0")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("oh,mg’jHITxAE.unrvGSyfpa", 0.4008042895442359, "0"), NodeData("oh,mg’jHITxAE.u", 0.17828418230563003, "0"), NodeData("h,mg’jHITxAE.u", 0.08981233243967829, "1"), NodeData("g’jHITxAE.u", 0.04691689008042896, "1"), NodeData("g’jHITxAE", 0.021447721179624665, "0"), NodeData("HITxAE", 0.010723860589812333, "1"), NodeData("HI", 0.005361930294906166, "0"), NodeData("I", 0.002680965147453083, "1")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("oh,mg’jHITxAE.unrvGSyfpa", 0.4008042895442359, "0"), NodeData("oh,mg’jHITxAE.u", 0.17828418230563003, "0"), NodeData("h,mg’jHITxAE.u", 0.08981233243967829, "1"), NodeData("g’jHITxAE.u", 0.04691689008042896, "1"), NodeData("g’jHITxAE", 0.021447721179624665, "0"), NodeData("HITxAE", 0.010723860589812333, "1"), NodeData("TxAE", 0.005361930294906166, "1"), NodeData("Tx", 0.002680965147453083, "0"), NodeData("T", 0.0013404825737265416, "0")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("oh,mg’jHITxAE.unrvGSyfpa", 0.4008042895442359, "0"), NodeData("oh,mg’jHITxAE.u", 0.17828418230563003, "0"), NodeData("h,mg’jHITxAE.u", 0.08981233243967829, "1"), NodeData("g’jHITxAE.u", 0.04691689008042896, "1"), NodeData("g’jHITxAE", 0.021447721179624665, "0"), NodeData("HITxAE", 0.010723860589812333, "1"), NodeData("TxAE", 0.005361930294906166, "1"), NodeData("Tx", 0.002680965147453083, "0"), NodeData("x", 0.0013404825737265416, "1")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("oh,mg’jHITxAE.unrvGSyfpa", 0.4008042895442359, "0"), NodeData("oh,mg’jHITxAE.u", 0.17828418230563003, "0"), NodeData("h,mg’jHITxAE.u", 0.08981233243967829, "1"), NodeData("g’jHITxAE.u", 0.04691689008042896, "1"), NodeData("g’jHITxAE", 0.021447721179624665, "0"), NodeData("HITxAE", 0.010723860589812333, "1"), NodeData("TxAE", 0.005361930294906166, "1"), NodeData("AE", 0.002680965147453083, "1"), NodeData("A", 0.0013404825737265416, "0")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("oh,mg’jHITxAE.unrvGSyfpa", 0.4008042895442359, "0"), NodeData("oh,mg’jHITxAE.u", 0.17828418230563003, "0"), NodeData("h,mg’jHITxAE.u", 0.08981233243967829, "1"), NodeData("g’jHITxAE.u", 0.04691689008042896, "1"), NodeData("g’jHITxAE", 0.021447721179624665, "0"), NodeData("HITxAE", 0.010723860589812333, "1"), NodeData("TxAE", 0.005361930294906166, "1"), NodeData("AE", 0.002680965147453083, "1"), NodeData("E", 0.0013404825737265416, "1")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("oh,mg’jHITxAE.unrvGSyfpa", 0.4008042895442359, "0"), NodeData("oh,mg’jHITxAE.u", 0.17828418230563003, "0"), NodeData("h,mg’jHITxAE.u", 0.08981233243967829, "1"), NodeData("g’jHITxAE.u", 0.04691689008042896, "1"), NodeData(".u", 0.02546916890080429, "1"), NodeData(".", 0.012064343163538873, "0")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("oh,mg’jHITxAE.unrvGSyfpa", 0.4008042895442359, "0"), NodeData("oh,mg’jHITxAE.u", 0.17828418230563003, "0"), NodeData("h,mg’jHITxAE.u", 0.08981233243967829, "1"), NodeData("g’jHITxAE.u", 0.04691689008042896, "1"), NodeData(".u", 0.02546916890080429, "1"), NodeData("u", 0.013404825737265416, "1")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("oh,mg’jHITxAE.unrvGSyfpa", 0.4008042895442359, "0"), NodeData("nrvGSyfpa", 0.22252010723860588, "1"), NodeData("nr", 0.10455764075067024, "0"), NodeData("n", 0.05093833780160858, "0")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("oh,mg’jHITxAE.unrvGSyfpa", 0.4008042895442359, "0"), NodeData("nrvGSyfpa", 0.22252010723860588, "1"), NodeData("nr", 0.10455764075067024, "0"), NodeData("r", 0.05361930294906166, "1")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("oh,mg’jHITxAE.unrvGSyfpa", 0.4008042895442359, "0"), NodeData("nrvGSyfpa", 0.22252010723860588, "1"), NodeData("vGSyfpa", 0.11796246648793565, "1"), NodeData("vGSyfp", 0.05630026809651474, "0"), NodeData("vGSyf", 0.02815013404825737, "0"), NodeData("vGSy", 0.013404825737265416, "0"), NodeData("v", 0.006702412868632708, "0")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("oh,mg’jHITxAE.unrvGSyfpa", 0.4008042895442359, "0"), NodeData("nrvGSyfpa", 0.22252010723860588, "1"), NodeData("vGSyfpa", 0.11796246648793565, "1"), NodeData("vGSyfp", 0.05630026809651474, "0"), NodeData("vGSyf", 0.02815013404825737, "0"), NodeData("vGSy", 0.013404825737265416, "0"), NodeData("GSy", 0.006702412868632708, "1"), NodeData("GS", 0.002680965147453083, "0"), NodeData("G", 0.0013404825737265416, "0")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("oh,mg’jHITxAE.unrvGSyfpa", 0.4008042895442359, "0"), NodeData("nrvGSyfpa", 0.22252010723860588, "1"), NodeData("vGSyfpa", 0.11796246648793565, "1"), NodeData("vGSyfp", 0.05630026809651474, "0"), NodeData("vGSyf", 0.02815013404825737, "0"), NodeData("vGSy", 0.013404825737265416, "0"), NodeData("GSy", 0.006702412868632708, "1"), NodeData("GS", 0.002680965147453083, "0"), NodeData("S", 0.0013404825737265416, "1")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("oh,mg’jHITxAE.unrvGSyfpa", 0.4008042895442359, "0"), NodeData("nrvGSyfpa", 0.22252010723860588, "1"), NodeData("vGSyfpa", 0.11796246648793565, "1"), NodeData("vGSyfp", 0.05630026809651474, "0"), NodeData("vGSyf", 0.02815013404825737, "0"), NodeData("vGSy", 0.013404825737265416, "0"), NodeData("GSy", 0.006702412868632708, "1"), NodeData("y", 0.004021447721179625, "1")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("oh,mg’jHITxAE.unrvGSyfpa", 0.4008042895442359, "0"), NodeData("nrvGSyfpa", 0.22252010723860588, "1"), NodeData("vGSyfpa", 0.11796246648793565, "1"), NodeData("vGSyfp", 0.05630026809651474, "0"), NodeData("vGSyf", 0.02815013404825737, "0"), NodeData("f", 0.014745308310991957, "1")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("oh,mg’jHITxAE.unrvGSyfpa", 0.4008042895442359, "0"), NodeData("nrvGSyfpa", 0.22252010723860588, "1"), NodeData("vGSyfpa", 0.11796246648793565, "1"), NodeData("vGSyfp", 0.05630026809651474, "0"), NodeData("p", 0.028150134048257374, "1")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("oh,mg’jHITxAE.unrvGSyfpa", 0.4008042895442359, "0"), NodeData("nrvGSyfpa", 0.22252010723860588, "1"), NodeData("vGSyfpa", 0.11796246648793565, "1"), NodeData("a", 0.06166219839142091, "1")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("iwbFkl sted\nWc", 0.599195710455764, "1"), NodeData("iwbFkl ", 0.28284182305630023, "0"), NodeData("iwbFkl", 0.1327077747989276, "0"), NodeData("i", 0.06568364611260054, "0")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("iwbFkl sted\nWc", 0.599195710455764, "1"), NodeData("iwbFkl ", 0.28284182305630023, "0"), NodeData("iwbFkl", 0.1327077747989276, "0"), NodeData("wbFkl", 0.06702412868632707, "1"), NodeData("wbF", 0.030831099195710455, "0"), NodeData("w", 0.014745308310991957, "0")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("iwbFkl sted\nWc", 0.599195710455764, "1"), NodeData("iwbFkl ", 0.28284182305630023, "0"), NodeData("iwbFkl", 0.1327077747989276, "0"), NodeData("wbFkl", 0.06702412868632707, "1"), NodeData("wbF", 0.030831099195710455, "0"), NodeData("bF", 0.0160857908847185, "1"), NodeData("b", 0.00804289544235925, "0")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("iwbFkl sted\nWc", 0.599195710455764, "1"), NodeData("iwbFkl ", 0.28284182305630023, "0"), NodeData("iwbFkl", 0.1327077747989276, "0"), NodeData("wbFkl", 0.06702412868632707, "1"), NodeData("wbF", 0.030831099195710455, "0"), NodeData("bF", 0.0160857908847185, "1"), NodeData("F", 0.00804289544235925, "1")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("iwbFkl sted\nWc", 0.599195710455764, "1"), NodeData("iwbFkl ", 0.28284182305630023, "0"), NodeData("iwbFkl", 0.1327077747989276, "0"), NodeData("wbFkl", 0.06702412868632707, "1"), NodeData("kl", 0.03619302949061662, "1"), NodeData("k", 0.01742627345844504, "0")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("iwbFkl sted\nWc", 0.599195710455764, "1"), NodeData("iwbFkl ", 0.28284182305630023, "0"), NodeData("iwbFkl", 0.1327077747989276, "0"), NodeData("wbFkl", 0.06702412868632707, "1"), NodeData("kl", 0.03619302949061662, "1"), NodeData("l", 0.01876675603217158, "1")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("iwbFkl sted\nWc", 0.599195710455764, "1"), NodeData("iwbFkl ", 0.28284182305630023, "0"), NodeData(" ", 0.15013404825737264, "1")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("iwbFkl sted\nWc", 0.599195710455764, "1"), NodeData("sted\nWc", 0.3163538873994638, "1"), NodeData("st", 0.15281501340482573, "0"), NodeData("s", 0.07238605898123325, "0")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("iwbFkl sted\nWc", 0.599195710455764, "1"), NodeData("sted\nWc", 0.3163538873994638, "1"), NodeData("st", 0.15281501340482573, "0"), NodeData("t", 0.08042895442359249, "1")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("iwbFkl sted\nWc", 0.599195710455764, "1"), NodeData("sted\nWc", 0.3163538873994638, "1"), NodeData("ed\nWc", 0.16353887399463807, "1"), NodeData("e", 0.08176943699731903, "0")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("iwbFkl sted\nWc", 0.599195710455764, "1"), NodeData("sted\nWc", 0.3163538873994638, "1"), NodeData("ed\nWc", 0.16353887399463807, "1"), NodeData("d\nWc", 0.08176943699731903, "1"), NodeData("d", 0.040214477211796246, "0")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("iwbFkl sted\nWc", 0.599195710455764, "1"), NodeData("sted\nWc", 0.3163538873994638, "1"), NodeData("ed\nWc", 0.16353887399463807, "1"), NodeData("d\nWc", 0.08176943699731903, "1"), NodeData("\nWc", 0.04155495978552279, "1"), NodeData("\nW", 0.020107238605898123, "0"), NodeData("\n", 0.00938337801608579, "0")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("iwbFkl sted\nWc", 0.599195710455764, "1"), NodeData("sted\nWc", 0.3163538873994638, "1"), NodeData("ed\nWc", 0.16353887399463807, "1"), NodeData("d\nWc", 0.08176943699731903, "1"), NodeData("\nWc", 0.04155495978552279, "1"), NodeData("\nW", 0.020107238605898123, "0"), NodeData("W", 0.010723860589812333, "1")]===
===Any[NodeData("oh,mg’jHITxAE.unrvGSyfpaiwbFkl sted\nWc", 1.0, "0"), NodeData("iwbFkl sted\nWc", 0.599195710455764, "1"), NodeData("sted\nWc", 0.3163538873994638, "1"), NodeData("ed\nWc", 0.163538873994638
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

上述程序构造了从根结点到叶子结点的所有路径。

熵

以下内容取自文心一言自动生成。

一、信息熵的定义

• 信息学中的熵，特别是在信息论中，用于量化信息的不确定性或随机性。熵的计算是基于随机变量的概率分布来进行的。具体来说，信息熵的计算公式为：
  $$[H(X)=-\sum _{i=1}^{n}P(x_i){\log }_2(P(x_i))]$$

其中，X 表示随机变量，n 是 X可能取值的总数，$P(x_i)$是 X取值为$x_i$的概率，${\log }_2$ 表示以2为底的对数。

这个公式表示了随机变量 X 的信息熵 H(X)，它是 X 所有可能取值的信息量的加权平均，权重是各个取值的概率。信息量$I(x_i)$被定义为 $-{\log }_2(P(x_i))$，它表示了当随机变量 X取值为$x_i$时，我们所获得的信息量。

在信息论中，熵（Entropy）是一个用来量化信息不确定性或随机性的重要概念。信息学熵的计算主要基于概率分布，其计算公式和信息量的概念紧密相关。
以下是对信息学熵的详细阐述：

• 信息熵是随机变量不确定性的度量，它表示了随机变量所有可能取值的信息量的期望。对于离散随机变量X，其信息熵H(X)的定义如下：

$[H(X)=-{\sum }_{i=1}^{n}P(x_i){\log }_{b}P(x_i)]$

其中，$P(x_i)$是随机变量X取值为$x_i$的概率，n是X所有可能取值的数量，b是对数的底数（在信息论中，常用2作为底数，此时单位称为比特；也有用自然对数作为底数的，此时单位称为奈特）。

二、信息量的概念

信息量与信息熵紧密相关，它度量的是一个具体事件发生了所带来的信息。对于某一事件X，其信息量I(X)的计算公式为：

$[I(X)=-{\log }_{b}P(X)]$

其中，P(X)是事件X发生的概率。这个公式表明，一个事件发生的概率越小，它所包含的信息量就越大；反之，概率越大，信息量就越小。

三、信息熵的计算步骤

1. 确定随机变量的所有可能取值及其概率：首先，需要明确随机变量X的所有可能取值，并计算出每个取值对应的概率$P(x_i)$。

2. 计算每个取值的信息量：根据信息量的计算公式，计算随机变量X每个取值的信息量$I(x_i)=-{\log }_{b}P(x_i)$。

3. 计算信息熵：最后，将每个取值的信息量乘以其对应的概率，并求和，即可得到随机变量X的信息熵$H(X)=-{\sum }_{i=1}^{n}P(x_i){\log }_{b}P(x_i)$。

四、信息熵的性质

1. 非负性：信息熵总是非负的，即$H(X)\ge 0$。这是因为概率P的取值范围是[0,1]，而对数函数在(0,1]区间内是负的，所以加上负号后变为正数或0。

2. 极值性：当随机变量X的所有取值概率相等时（即均匀分布），信息熵取得最大值。这是因为此时不确定性最大。

3. 可加性：对于多个相互独立的随机变量，它们联合分布的信息熵等于各随机变量信息熵之和。

五、应用举例

• 以世界杯冠军预测为例，如果假设有32支球队参赛，且每支球队夺冠的概率相等（即1/32），则“谁是世界杯冠军”这一信息的信息熵为：

$[H(X)=-{\sum }_{i=1}^{32}\frac{1}{32}{\log }_2\frac{1}{32}=-{\log }_2\frac{1}{32}=5\text{比特}]$

这表示，为了确定世界杯冠军，平均需要5比特的信息量。然而，在实际情况下，由于各支球队的夺冠概率并不相等，因此所需的信息量通常会小于5比特。

• 假设有一个随机变量 (X)，它只有两个可能的取值：0和1，且 $P(X=0)=0.5$，$P(X=1)=0.5$。则 $X$ 的信息熵为：

$[H(X)=-(0.5{\log }_2(0.5)+0.5{\log }_2(0.5))=-(0.5\times (-1)+0.5\times (-1))=1\text{ bit}]$

这表示在平均意义上，我们需要1比特的信息来完全确定 (X) 的取值。

哈夫曼编码（Huffman Coding）

又称霍夫曼编码，是一种可变字长编码（VLC, Variable Length Coding）方式，由David A. Huffman在1952年提出。它是一种用于无损数据压缩的熵编码算法，通常用于压缩重复率比较高的字符数据。哈夫曼编码完全依据字符出现概率来构造异字头的平均长度最短的码字，因此有时也称之为最佳编码。

基本原理

哈夫曼编码的基本方法是先对图像数据或文本数据扫描一遍，计算出各种字符或像素出现的概率，然后按概率的大小指定不同长度的唯一码字，由此得到一张该数据的哈夫曼码表。编码后的数据记录的是每个字符或像素的码字，而码字与实际字符或像素值的对应关系则记录在码表中。

编码过程

1. 统计频率：计算字符串或数据集中每个字符或像素出现的频率。
2. 排序：将字符或像素按照出现频率由低到高进行排序。
3. 构建哈夫曼树：
   • 创建一个空节点，将最小频率的两个字符或像素作为该节点的左右子节点，并将它们的频率相加作为父节点的频率。
   • 将这两个子节点从队列中删除，并将父节点添加到队列中。
   • 重复上述步骤，直到队列中只剩下一个节点，即根节点，此时哈夫曼树构建完成。
4. 生成编码：从根节点开始，为每个字符或像素生成一个唯一的编码。对于每个非叶子节点，将0分配给连接线的左侧，1分配给连接线的右侧。从根节点到叶子节点的路径上的0和1序列即为该叶子节点代表的字符或像素的编码。

特点

1. 编码效率高：由于哈夫曼编码根据字符或像素的出现频率分配码长，因此出现频率高的字符或像素使用较短的编码，而出现频率低的则使用较长的编码，从而实现了数据的有效压缩。
2. 编码不唯一：由于构建哈夫曼树时可以为左右子节点任意分配0和1，以及当两个字符或像素的频率相等时排序的随机性，因此生成的哈夫曼编码并不唯一。但所有有效的哈夫曼编码都具有相同的平均码长。
3. 前缀码：哈夫曼编码的一个重要特性是任何一个编码都不是其他编码的前缀，这保证了在解码时能够准确地分离出每个字符或像素的编码。

应用

哈夫曼编码已被广泛应用于数据压缩领域，如文件压缩、图像压缩、视频压缩等。此外，在通信和网络传输中，哈夫曼编码也常被用于减少数据传输量，提高传输效率。

综上所述，哈夫曼编码是一种基于字符或像素出现频率的无损数据压缩算法，通过构建哈夫曼树并为每个字符或像素生成唯一的编码来实现数据的压缩。由于其高效的压缩性能和广泛的应用场景，哈夫曼编码在数据压缩领域具有重要的地位。

哈夫曼编码（Huffman Coding），又称霍夫曼编码，是由David A. Huffman在1952年提出的一种编码方法，它完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码。哈夫曼编码是可变字长编码（VLC）的一种，其基本原理是表示符号的码字长度随符号的出现概率而变化，对出现概率大的符号赋予短码字，出现概率小的符号赋予长码字，并且码字长度严格按照所对应符号出现概率大小逆序排列。以下是哈夫曼编码的具体过程：

具体过程

1. 排序概率

• 将信源符号的概率按从大到小的顺序排队，即P(1) > P(2) > … > P(Sm-1) > P(Sm)。

2. 合并最小概率

• 从概率最小的两个符号开始，将它们合并为一个新的符号，合并后的新符号概率为这两个符号概率之和。
• 在合并时，可以给这两个符号分别赋予“0”和“1”（或相反）作为它们的编码，这取决于合并时的具体实现。

3. 更新概率序列

• 将合并后的新符号的概率与未处理的其余符号的概率重新按从大到小的顺序排列，形成一个新的概率序列。

4. 重复合并

• 重复步骤2和步骤3，直到所有的符号都被合并为一个概率为1的符号为止。在这个过程中，每次合并都会生成一个新的符号，并给这个新符号赋予一个编码（由前面合并时赋予的“0”和“1”组成）。

5. 生成码表

• 最后，从合并得到的概率总和为1的符号开始，逆向追踪每个符号的编码路径，从而得到每个原始符号的哈夫曼码字。
• 这些码字和它们对应的原始符号一起构成了哈夫曼码表。

6. 编码数据

• 使用生成的哈夫曼码表对原始数据进行编码，即用每个符号的哈夫曼码字替换原始数据中的符号。

示例

假设有以下符号及其概率：a(0.4), b(0.2), c(0.2), d(0.1), e(0.1)。

• 排序：a, b=c, d=e
• 合并b和c，得到新符号bc(0.4)，赋予编码“0”（或“1”），假设为“0”
• 合并d和e，得到新符号de(0.2)，赋予编码“1”（或“0”），假设为“1”
• 排序：a, bc, de
• 合并a和bc，得到新符号abc(0.8)，赋予编码“0”（或“1”），假设为“0”
• 现在只剩下一个符号de，其编码为“1”
• 逆向追踪：a的编码为“00”，bc的编码为“01”（假设b为“0”，c为“1”），de的编码为“1”

这样，就得到了每个符号的哈夫曼码字，并可以据此对包含这些符号的数据进行编码。

哈夫曼编码由于其编码长度与符号出现概率的逆序关系，使得编码后的数据平均长度最短，因此在实际应用中常用于数据压缩领域。

哈夫曼编码的具体算法

哈夫曼编码是一种广泛用于数据文件压缩的非常有效的编码方法，其核心思想是利用字符频率信息，通过贪心策略构建一棵最优二叉树（哈夫曼树），使得高频字符使用较短的编码，低频字符使用较长的编码，从而实现数据压缩。以下是哈夫曼编码的具体算法步骤：

一、算法步骤

1. 统计频率：

   • 遍历数据，统计每个字符在数据中出现的频率。

2. 构建优先队列：

   • 将每个字符及其频率作为一个节点，并按照频率从小到大的顺序放入优先队列（最小堆）。
   • 如果两个字符频率相同，则它们的顺序可以任意，因为哈夫曼编码不唯一，但都能正常工作。

3. 构建哈夫曼树：

   • 重复执行以下步骤，直到优先队列中只剩下一个节点（即哈夫曼树的根节点）：
     • 从优先队列中取出两个频率最小的节点。
     • 创建一个新的父节点，其频率为这两个子节点频率之和。
     • 将新节点作为这两个子节点的父节点，并将新节点插入回优先队列。

4. 生成编码：

   • 从根节点开始，为哈夫曼树的每个节点规定编码：
     • 左子树路径编码为“0”，右子树路径编码为“1”。
     • 从根节点到每个叶子节点的路径（包括经过的“0”和“1”）构成了该叶子节点所代表字符的哈夫曼编码。

二、算法特点

• 前缀码：哈夫曼编码是一种前缀码，即任何一个字符的编码都不是另一个字符编码的前缀，这使得解码过程变得非常简单和高效。
• 变长编码：高频字符使用较短的编码，低频字符使用较长的编码，从而减少了整体编码的长度，提高了压缩效率。
• 最优性：在给定字符频率分布的情况下，哈夫曼编码生成的编码方案是平均码长最短的编码方案。

三、应用实例

假设有一个字符串“aaaaabbcdddeee”，我们可以按照以下步骤进行哈夫曼编码：

1. 统计频率：

   • a: 5
   • b: 2
   • c: 1
   • d: 3
   • e: 3

2. 构建优先队列和哈夫曼树（这里省略详细构建过程，仅给出结果）：

   • 最终构建的哈夫曼树将包含这些字符作为叶子节点，并根据它们的频率进行合并。

3. 生成编码：

   • 假设生成的哈夫曼编码为（注意：实际编码可能因构建过程的具体实现而异）：
     • a: 0
     • b: 101
     • c: 100
     • d: 111
     • e: 110

四、算法实现

哈夫曼编码的算法实现相对简单，主要涉及到频率统计、优先队列操作以及树的构建。在实际应用中，可以使用各种编程语言中的数据结构（如优先队列、二叉树等）来实现该算法。

五、注意事项

• 在实际应用中，需要注意哈夫曼编码的解码过程，由于它是前缀码，所以解码时无需回溯。
• 哈夫曼编码是一种无损压缩算法，可以保证压缩后的数据可以完全还原成原始数据。
• 哈夫曼编码的压缩效率取决于字符频率的分布情况，对于频率分布差异较大的数据，哈夫曼编码的压缩效果更为显著。

参考文献

1.《密码学原理与实践（第三版）》
2. 文心一言