三进制霍夫曼编码.doc

题目:将霍夫曼编码推广至三进制编码,并证明它能产生最优编码。※将霍夫曼编码推广至三进制编码设一个数据文件包含Q个字符:A1,A2,……,Aq,每个字符出现的频度对应为P:P1,P2,……,Pq。,记此时的排列为排列1。(设为S1)代替排列1中频度值最小的Q-2k(k为(Q-1)/2取整)个字符,并记其频度值为排列1中最小的Q-2k个频度值相加,再重新按频度从大到小顺序排列字符,记为排列2。(注:若Q-2k=0,则取其值为2,若Q-2k=1,则取其值为3.),直至最后剩下3个概率值。,根据3个概率大小,分别赋予与3个字符对应的值:0、1、2,如此得到最后一个排列3个频度的一位编码。,这3个频度就取它的一位编码后面再延长一位编码,得到二位编码,其它不变。,直到排列1所有的频度值都被编码为止。举例说明如下(假设Q=9):。编码后字符A1~A9的码字依次为:2,00,02,10,11,12,010,011,012。构造三进制霍夫曼编码伪码程序如下:HUFFMAN(C)1n←∣C∣2Q←C3fori←1ton-14doallocateanewnodes5left[s]←x←EXTRACT-MIN(Q)6middle[s]←y←EXTRACT-MIN(Q)7right[s]←z←EXTRACT-MIN(Q)8f[s]←f[x]+f[y]+f[z]9INSERT(Q,z)10returnEXTRACT-MIN(Q)※霍夫曼编码(三进制)最优性证明在二进制霍夫曼编码中,文件的最优编码由一棵满二叉树表示,树中每个非叶子结点都有两个子结点。在此与之相对应,构造一棵满三叉树来表示三进制的霍夫曼编码,树中每个非叶子结点都有三个子结点。对文件中A中的每个字符a,设f(a)表示a在文件中出现的频度,dT(a)表示字符a的编码长度,亦即a的叶子在树中的深度。这样,编码一个文件所需的位数就是B(T)=∑f(a)dT(a)设A为一给定文件,其中每个字符都定义有频度f[a]。设x,y和z是A中具有最低频度的两个字符。并设A'为文件A中移去x,y和z,再加上新的字符s后的文件,亦即A'=A-{x,y,z}∪{s};如A一样为A'定义f,其中f[s]=f[x]+f[y]+f[z]。设T'为文件A'上最优前缀编码的任意一棵树,那么,将T'中叶子节点s换成具有x,y和z孩子的内部节点所得到的树T,表示文件A上的一个最优前缀编码。证明:对每一个a∈A-{x,y,z},有dT(a)=dT'(a),故f[a]dT(a)=f[