廊坊哪里做网站,重庆网站网页设计培训机构,免费不良正能量网站链接,网页一般用什么语言编写文章目录 概率分布哈夫曼编码实现julia官方文档建议的变量命名规范#xff1a;julia源码 熵一、信息熵的定义二、信息量的概念三、信息熵的计算步骤四、信息熵的性质五、应用举例 哈夫曼编码#xff08;Huffman Coding#xff09;基本原理编码过程特点应用具体过程1. 排序概… 文章目录 概率分布哈夫曼编码实现julia官方文档建议的变量命名规范julia源码 熵一、信息熵的定义二、信息量的概念三、信息熵的计算步骤四、信息熵的性质五、应用举例 哈夫曼编码Huffman Coding基本原理编码过程特点应用具体过程1. 排序概率2. 合并最小概率3. 更新概率序列4. 重复合并5. 生成码表6. 编码数据示例 哈夫曼编码的具体算法一、算法步骤二、算法特点三、应用实例四、算法实现五、注意事项 乘积密码乘积密码的基本概念和原理乘积密码的应用场景与优势乘积密码的算法设计与实现乘积密码的实例乘积密码的发展趋势与挑战 参考文献 概率分布 bayes概率 P r ( X x ) 为明文的先验概率 P r ( Y y ) 为密文的先验概率 P r ( K k ) 为密钥的先验概率 C ( K ) ( e k ( x ) ∣ k ∈ P ) , P 为明文 C ( K ) 为密文 ∀ y ∈ C , P r ( Y y ) Σ k : y ∈ C ( K ) P r ( K k ) P r ( x d k ( y ) ) P r ( Y y ∣ X x ) Σ k : x d k ( y ) P r ( K k ) 所有先验概率准备完毕下面是 b a y e s 概率了 P r ( X x ∣ Y y ) P r ( X x ) × Σ k : x d k ( y ) P r ( K k ) Σ k : y ∈ C ( k ) P r ( K k ) P r ( x d x ( y ) ) Pr(Xx)为明文的先验概率 \\Pr(Yy)为密文的先验概率 \\Pr(Kk)为密钥的先验概率 \\C(K)(e_k(x)|k \in P),P为明文C(K)为密文 \\\forall y \in C,Pr(Yy)\Sigma_{k:y \in C(K)} Pr(Kk)Pr(xd_k(y)) \\Pr(Yy|Xx)\Sigma_{k:xd_k(y)}Pr(Kk) \\所有先验概率准备完毕下面是bayes概率了 \\Pr(Xx|Yy)\frac {Pr(Xx)\times \Sigma_{k:xd_k(y)}Pr(Kk)}{\Sigma_{k:y \in C(k)}Pr(Kk)Pr(xd_x(y))} Pr(Xx)为明文的先验概率Pr(Yy)为密文的先验概率Pr(Kk)为密钥的先验概率C(K)(ek(x)∣k∈P),P为明文C(K)为密文∀y∈C,Pr(Yy)Σk:y∈C(K)Pr(Kk)Pr(xdk(y))Pr(Yy∣Xx)Σk:xdk(y)Pr(Kk)所有先验概率准备完毕下面是bayes概率了Pr(Xx∣Yy)Σk:y∈C(k)Pr(Kk)Pr(xdx(y))Pr(Xx)×Σk:xdk(y)Pr(Kk) 例子 设明文集合 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_{(ji1) 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(Xx|Yy) \\Pr(1|a)0 \\Pr(2|a)0 \\.... \\Pr(4|a)\frac {Pr(X4)\times Pr(KK_1)} {Pr(Ya)}\frac {1/8 \times1/2}{3/16}\frac 1 3 \\.... \\3.密码机制具有完善保密性对于任意x \in P,y \in CPr(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)430≤j5,j∈ZeKi(Pj)C(ji1)mod5eK1(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(Xx∣Yy)Pr(1∣a)0Pr(2∣a)0....Pr(4∣a)Pr(Ya)Pr(X4)×Pr(KK1)3/161/8×1/231....3.密码机制具有完善保密性对于任意x∈P,y∈CPr(x∣y)Pr(x)上面例子的密码机制不具有完善保密性:Pr(4∣a)1/3,P(4)1/8
哈夫曼编码实现
julia官方文档建议的变量命名规范
变量名用小写。 单词用下划线_分隔建议只对复杂的名称使用。类型、模块的名称以大写字母开头单词以驼峰方式间隔。函数名和宏名用不带下划线的小写字母。改变输入参数值的函数函数名以’!为结尾
julia源码
mutable struct NodeDatadata::Stringdata_pr::Realbm::Union{String,Nothing}
endmutable struct TreeNodedata::NodeDataleft::Union{TreeNode, Nothing}right::Union{TreeNode, Nothing}
end# 插入节点的函数
function newnode(data::String,data_pr::Real,bmnothing)ndataNodeData(data,data_pr,bm)tnodeTreeNode(ndata,nothing,nothing)return tnode
end
function insertleft(node::TreeNode, leftsubnode::TreeNode)node.leftleftsubnode
end
function insertright(node::TreeNode, rightsubnode::TreeNode)node.rightrightsubnode
endfunction printPaths(node::TreeNode, nodetype::StringL,path []) if node nothing return end if nodetypeLnode.data.bm0elsenode.data.bm1end# 将当前节点的值添加到路径中 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# 使用
strtxtFedora 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_prDict{String,Real}()
for i in eachindex(strtxt)global word_prif haskey(word_pr,string(strtxt[i]))word_pr[string(strtxt[i])]1elseword_pr[string(strtxt[i])]1end
end
allwordcountsum(values(word_pr))
map!(x-x/allwordcount, values(word_pr))nodelistDict{String,TreeNode}()
#构建优先队列
wordslistcollect(word_pr)sort!(wordslist,byx-x[2])while length(wordslist)1global nodelistglobal wordslist#从优先队列中取出两个频率最小的节点,创建一个新的父节点其频率为这两个子节点频率之和。c1popfirst!(wordslist)c2popfirst!(wordslist)if !haskey(nodelist,c1[1])nodelist[c1[1]]newnode(c1[1],c1[2])endif !haskey(nodelist,c2[1])nodelist[c2[1]]newnode(c2[1],c2[2])end#将新节点作为这两个子节点的父节点并将新节点插入回优先队列。if !haskey(nodelist,c1[1]*c2[1])parentnodenewnode(c1[1]*c2[1],c1[2]c2[2])nodelist[c1[1]*c2[1]]parentnodeinsertleft(parentnode,nodelist[c1[1]])insertright(parentnode,nodelist[c2[1]])endpush!(wordslist,c1[1]*c2[1]c1[2]c2[2])sort!(wordslist,byx-x[2])
end printPaths(nodelist[wordslist[1][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(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上述程序构造了从根结点到叶子结点的所有路径。
熵
以下内容取自文心一言自动生成。
一、信息熵的定义
信息学中的熵特别是在信息论中用于量化信息的不确定性或随机性。熵的计算是基于随机变量的概率分布来进行的。具体来说信息熵的计算公式为 [ H ( X ) − ∑ i 1 n P ( x i ) log 2 ( P ( x i ) ) ] [ H(X) -\sum_{i1}^{n} P(x_i) \log_2(P(x_i)) ] [H(X)−i1∑nP(xi)log2(P(xi))]
其中X 表示随机变量n 是 X可能取值的总数 P ( x i ) P(x_i) P(xi)是 X取值为 x i x_i xi的概率 log 2 \log_2 log2 表示以2为底的对数。
这个公式表示了随机变量 X 的信息熵 H(X)它是 X 所有可能取值的信息量的加权平均权重是各个取值的概率。信息量 I ( x i ) I(x_i) I(xi)被定义为 − log 2 ( P ( x i ) ) -\log_2(P(x_i)) −log2(P(xi))它表示了当随机变量 X取值为 x i x_i xi时我们所获得的信息量。
在信息论中熵Entropy是一个用来量化信息不确定性或随机性的重要概念。信息学熵的计算主要基于概率分布其计算公式和信息量的概念紧密相关。 以下是对信息学熵的详细阐述
信息熵是随机变量不确定性的度量它表示了随机变量所有可能取值的信息量的期望。对于离散随机变量X其信息熵H(X)的定义如下 [ H ( X ) − ∑ i 1 n P ( x i ) log b P ( x i ) ] [ H(X) -\sum_{i1}^{n} P(x_i) \log_b P(x_i) ] [H(X)−∑i1nP(xi)logbP(xi)]
其中 P ( x i ) P(x_i) P(xi)是随机变量X取值为 x i x_i xi的概率n是X所有可能取值的数量b是对数的底数在信息论中常用2作为底数此时单位称为比特也有用自然对数作为底数的此时单位称为奈特。
二、信息量的概念
信息量与信息熵紧密相关它度量的是一个具体事件发生了所带来的信息。对于某一事件X其信息量I(X)的计算公式为 [ I ( X ) − log b P ( X ) ] [ I(X) -\log_b P(X) ] [I(X)−logbP(X)]
其中P(X)是事件X发生的概率。这个公式表明一个事件发生的概率越小它所包含的信息量就越大反之概率越大信息量就越小。
三、信息熵的计算步骤 确定随机变量的所有可能取值及其概率首先需要明确随机变量X的所有可能取值并计算出每个取值对应的概率 P ( x i ) P(x_i) P(xi)。 计算每个取值的信息量根据信息量的计算公式计算随机变量X每个取值的信息量 I ( x i ) − log b P ( x i ) I(x_i) -\log_b P(x_i) I(xi)−logbP(xi)。 计算信息熵最后将每个取值的信息量乘以其对应的概率并求和即可得到随机变量X的信息熵 H ( X ) − ∑ i 1 n P ( x i ) log b P ( x i ) H(X) -\sum_{i1}^{n} P(x_i) \log_b P(x_i) H(X)−∑i1nP(xi)logbP(xi)。
四、信息熵的性质 非负性信息熵总是非负的即 H ( X ) ≥ 0 H(X) \geq 0 H(X)≥0。这是因为概率P的取值范围是[0,1]而对数函数在(0,1]区间内是负的所以加上负号后变为正数或0。 极值性当随机变量X的所有取值概率相等时即均匀分布信息熵取得最大值。这是因为此时不确定性最大。 可加性对于多个相互独立的随机变量它们联合分布的信息熵等于各随机变量信息熵之和。
五、应用举例
以世界杯冠军预测为例如果假设有32支球队参赛且每支球队夺冠的概率相等即1/32则“谁是世界杯冠军”这一信息的信息熵为 [ H ( X ) − ∑ i 1 32 1 32 log 2 1 32 − log 2 1 32 5 比特 ] [H(X) -\sum_{i1}^{32} \frac{1}{32} \log_2 \frac{1}{32} -\log_2 \frac{1}{32} 5 \text{比特} ] [H(X)−∑i132321log2321−log23215比特]
这表示为了确定世界杯冠军平均需要5比特的信息量。然而在实际情况下由于各支球队的夺冠概率并不相等因此所需的信息量通常会小于5比特。
假设有一个随机变量 (X)它只有两个可能的取值0和1且 P ( X 0 ) 0.5 P(X0) 0.5 P(X0)0.5 P ( X 1 ) 0.5 P(X1) 0.5 P(X1)0.5。则 X X X 的信息熵为 [ H ( X ) − ( 0.5 log 2 ( 0.5 ) 0.5 log 2 ( 0.5 ) ) − ( 0.5 × ( − 1 ) 0.5 × ( − 1 ) ) 1 bit ] [ 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} ] [H(X)−(0.5log2(0.5)0.5log2(0.5))−(0.5×(−1)0.5×(−1))1 bit]
这表示在平均意义上我们需要1比特的信息来完全确定 (X) 的取值。
哈夫曼编码Huffman Coding
又称霍夫曼编码是一种可变字长编码VLC, Variable Length Coding方式由David A. Huffman在1952年提出。它是一种用于无损数据压缩的熵编码算法通常用于压缩重复率比较高的字符数据。哈夫曼编码完全依据字符出现概率来构造异字头的平均长度最短的码字因此有时也称之为最佳编码。
基本原理
哈夫曼编码的基本方法是先对图像数据或文本数据扫描一遍计算出各种字符或像素出现的概率然后按概率的大小指定不同长度的唯一码字由此得到一张该数据的哈夫曼码表。编码后的数据记录的是每个字符或像素的码字而码字与实际字符或像素值的对应关系则记录在码表中。
编码过程
统计频率计算字符串或数据集中每个字符或像素出现的频率。排序将字符或像素按照出现频率由低到高进行排序。构建哈夫曼树 创建一个空节点将最小频率的两个字符或像素作为该节点的左右子节点并将它们的频率相加作为父节点的频率。将这两个子节点从队列中删除并将父节点添加到队列中。重复上述步骤直到队列中只剩下一个节点即根节点此时哈夫曼树构建完成。 生成编码从根节点开始为每个字符或像素生成一个唯一的编码。对于每个非叶子节点将0分配给连接线的左侧1分配给连接线的右侧。从根节点到叶子节点的路径上的0和1序列即为该叶子节点代表的字符或像素的编码。
特点
编码效率高由于哈夫曼编码根据字符或像素的出现频率分配码长因此出现频率高的字符或像素使用较短的编码而出现频率低的则使用较长的编码从而实现了数据的有效压缩。编码不唯一由于构建哈夫曼树时可以为左右子节点任意分配0和1以及当两个字符或像素的频率相等时排序的随机性因此生成的哈夫曼编码并不唯一。但所有有效的哈夫曼编码都具有相同的平均码长。前缀码哈夫曼编码的一个重要特性是任何一个编码都不是其他编码的前缀这保证了在解码时能够准确地分离出每个字符或像素的编码。
应用
哈夫曼编码已被广泛应用于数据压缩领域如文件压缩、图像压缩、视频压缩等。此外在通信和网络传输中哈夫曼编码也常被用于减少数据传输量提高传输效率。
综上所述哈夫曼编码是一种基于字符或像素出现频率的无损数据压缩算法通过构建哈夫曼树并为每个字符或像素生成唯一的编码来实现数据的压缩。由于其高效的压缩性能和广泛的应用场景哈夫曼编码在数据压缩领域具有重要的地位。
哈夫曼编码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, bc, de合并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”
这样就得到了每个符号的哈夫曼码字并可以据此对包含这些符号的数据进行编码。
哈夫曼编码由于其编码长度与符号出现概率的逆序关系使得编码后的数据平均长度最短因此在实际应用中常用于数据压缩领域。
哈夫曼编码的具体算法
哈夫曼编码是一种广泛用于数据文件压缩的非常有效的编码方法其核心思想是利用字符频率信息通过贪心策略构建一棵最优二叉树哈夫曼树使得高频字符使用较短的编码低频字符使用较长的编码从而实现数据压缩。以下是哈夫曼编码的具体算法步骤
一、算法步骤 统计频率 遍历数据统计每个字符在数据中出现的频率。 构建优先队列 将每个字符及其频率作为一个节点并按照频率从小到大的顺序放入优先队列最小堆。如果两个字符频率相同则它们的顺序可以任意因为哈夫曼编码不唯一但都能正常工作。 构建哈夫曼树 重复执行以下步骤直到优先队列中只剩下一个节点即哈夫曼树的根节点 从优先队列中取出两个频率最小的节点。创建一个新的父节点其频率为这两个子节点频率之和。将新节点作为这两个子节点的父节点并将新节点插入回优先队列。 生成编码 从根节点开始为哈夫曼树的每个节点规定编码 左子树路径编码为“0”右子树路径编码为“1”。从根节点到每个叶子节点的路径包括经过的“0”和“1”构成了该叶子节点所代表字符的哈夫曼编码。
二、算法特点
前缀码哈夫曼编码是一种前缀码即任何一个字符的编码都不是另一个字符编码的前缀这使得解码过程变得非常简单和高效。变长编码高频字符使用较短的编码低频字符使用较长的编码从而减少了整体编码的长度提高了压缩效率。最优性在给定字符频率分布的情况下哈夫曼编码生成的编码方案是平均码长最短的编码方案。
三、应用实例
假设有一个字符串“aaaaabbcdddeee”我们可以按照以下步骤进行哈夫曼编码 统计频率 a: 5b: 2c: 1d: 3e: 3 构建优先队列和哈夫曼树这里省略详细构建过程仅给出结果 最终构建的哈夫曼树将包含这些字符作为叶子节点并根据它们的频率进行合并。 生成编码 假设生成的哈夫曼编码为注意实际编码可能因构建过程的具体实现而异 a: 0b: 101c: 100d: 111e: 110
四、算法实现
哈夫曼编码的算法实现相对简单主要涉及到频率统计、优先队列操作以及树的构建。在实际应用中可以使用各种编程语言中的数据结构如优先队列、二叉树等来实现该算法。
五、注意事项
在实际应用中需要注意哈夫曼编码的解码过程由于它是前缀码所以解码时无需回溯。哈夫曼编码是一种无损压缩算法可以保证压缩后的数据可以完全还原成原始数据。哈夫曼编码的压缩效率取决于字符频率的分布情况对于频率分布差异较大的数据哈夫曼编码的压缩效果更为显著。乘积密码是一种密码学中的概念它指的是通过连续执行两个或多个密码系统或加密算法以使得所得到的最后结果或乘积从密码编码的角度比其任意一个组成密码都更强。这种密码体制的主要作用是提高加密的安全性通过多次加密增加攻击者破解密文的难度从而保护数据的机密性和完整性。
乘积密码
以下内容取自文心一言自动生成。
乘积密码的基本概念和原理
定义乘积密码以某种方式连续执行两个或多个密码使得最终结果的密码强度高于每个单独密码的强度。这是公钥密码学中的一个重要概念尤其在实现复杂的安全需求时非常有用。原理乘积密码基于扩散和混乱两种基本密码操作的组合变换。通过多次加密变换可以产生比单独使用任何一个密码时更强大的密码系统。
乘积密码的应用场景与优势
保密性乘积密码通过对数据进行多次加密确保在传输过程中数据不被未经授权的第三方窃取或窥探。完整性通过使用哈希函数等密码学工具乘积密码能够检测数据在传输过程中是否被篡改保证数据的完整性。不可否认性结合数字签名技术乘积密码可以确保发送方和接收方都无法否认已发送或接收的数据提供不可否认的证据。身份认证和访问控制乘积密码支持用户身份认证确保只有授权用户能够访问特定资源或服务。同时结合身份认证乘积密码可实现细粒度的访问控制根据用户角色和权限限制对资源的访问。
乘积密码的算法设计与实现
选择加密算法根据安全需求和性能要求选择合适的加密算法如AES、DES、RSA等。确定加密模式根据加密算法的特性选择合适的加密模式如ECB、CBC、CFB等。设置加密参数设置加密算法所需的密钥、初始化向量等参数。执行加密操作将明文输入到加密算法中经过多次加密变换最终得到密文输出。
乘积密码的实例
古典密码学中的乘积密码如转子机Rotor Machines它是非常复杂的多轮替代技术广泛应用于第二次世界大战中。现代密码学中的乘积密码在现代密码学中乘积密码的概念被广泛应用于各种加密协议和系统中以提高数据的安全性和保护用户的隐私。
乘积密码的发展趋势与挑战
随着计算机技术和密码学的发展乘积密码也在不断演进。一方面新的加密算法和技术的出现为乘积密码提供了更多的选择和可能性另一方面随着计算能力的提升和攻击技术的发展乘积密码也面临着更大的挑战。因此在设计和实现乘积密码时需要充分考虑其安全性和效率之间的平衡以确保其在实际应用中的有效性和可靠性。
参考文献
1.《密码学原理与实践第三版》 2. 文心一言
