《三进制霍夫曼编码》由会员分享，可在线阅读，更多相关《三进制霍夫曼编码(9页珍藏版)》请在人人文库网上搜索。
1、精品好资料学习推荐题目：将霍夫曼编码推广至三进制编码，并证明它能产生最优编码。将霍夫曼编码推广至三进制编码设一个数据文件包含Q个字符：A1，A2，Aq，每个字符出现的频度对应为P：P1，P2，Pq。1.将字符按频度从大到小顺序排列，记此时的排列为排列1。2.用一个新的符号(设为S1)代替排列1中频度值最小的Q-2k(k为(Q-1)/2取整)个字符，并记其频度值为排列1中最小的Q-2k个频度值相加，再重新按频度从大到小顺序排列字符，记为排列2。(注：若Q-2k=0，则取其值为2，若Q-2k=1，则取其值为3.)3.对排列2重复上述步骤2，直至最后剩下3个概率值。4.从最后一个排列开始编码，根据3。
2、个概率大小，分别赋予与3个字符对应的值：0、1、2，如此得到最后一个排列3个频度的一位编码。5.此时的3个频度中有一个频度是由前一个排列的3个相加而来，这3个频度就取它的一位编码后面再延长一位编码，得到二位编码，其它不变。6.如此一直往前，直到排列1所有的频度值都被编码为止。举例说明如下(假设Q=9)：字符A1A2A3A4A5A6A7A8A9频度0.220.180.150.130.100.070.070.050.03字符频度编码频度编码频度编码频度编码A10.2220.2220.3010.480A20.18000.18000.2220.301A30.15020.15010.18000.222A。
3、40.13100.15020.1501A50.10110.13100.1502A60.07120.1011A70.070100.0712A80.05011A90.03012频度中的黑体为前一频度列表中斜体频度相加而得。编码后字符A1A9的码字依次为：2,00,02,10,11,12,010,011,012。构造三进制霍夫曼编码伪码程序如下：HUFFMAN(C)1 n C2 Q C3 fori 1 to n-14 do allocate a new node s5 lefts x EXTRACT-MIN(Q)6 middles y EXTRACT-MIN(Q)7 rights z EXTRACT。
4、-MIN(Q)8 fs fx+fy+fz9 INSERT(Q，z)10 return EXTRACT-MIN(Q)霍夫曼编码(三进制)最优性证明在二进制霍夫曼编码中，文件的最优编码由一棵满二叉树表示，树中每个非叶子结点都有两个子结点。在此与之相对应，构造一棵满三叉树来表示三进制的霍夫曼编码，树中每个非叶子结点都有三个子结点。对文件中A中的每个字符a，设f(a)表示a在文件中出现的频度，dT(a)表示字符a的编码长度，亦即a的叶子在树中的深度。这样，编码一个文件所需的位数就是B(T)=f(a)dT(a)设A为一给定文件，其中每个字符都定义有频度fa。设x，y和z是A中具有最低频度的两个字符。并设。
5、A为文件A中移去x，y和z，再加上新的字符s后的文件，亦即A=A-x,y,zs；如A一样为A定义f，其中fs=fx+fy+fz。设T为文件A上最优前缀编码的任意一棵树，那么，将T中叶子节点s换成具有x，y和z孩子的内部节点所得到的树T，表示文件A上的一个最优前缀编码。证明：对每一个aA-x,y,z，有dT(a)=dT(a)，故fadT(a)=fadT(a)。又dT(x)=dT(y)=dT(z)=dT(s)+1，从而有：fxdT(x)+fydT(y)+fzdT(z)=(fx+fy+fz)(dT(s)+1)=fsdT(s)+(fx+fy+fz)由此可得：B(T)=B(T)+fx+fy+fz假设T不。
6、表示A的最优前缀编码，那么存在一棵树T，有B(T)#include #include int Sorting(int *x,int n)/排序int *a,b,i,j,r=0;a=x;for(j=0;j0;i-)temp=codepi0-1;for(j=count-2*i-1;j=0;j-)if(jpi0-1)codej+2=codej;elseif(j%sn,characteri,codei);printf(n);/for test/*for(i=0;i0;i-)temp=codepi0-1;for(j=count-i-1;j=0;j-)if(jpi0-1)codej+1=codej;elseif(j%sn,characteri,codei);printf(n);/for test/*for(i=0;itc;i+)for(j=0;jcount+1;j+)printf(%d ,pij);printf(n);*/9 / 9。
