精选优质文档-倾情为你奉上题目:将霍夫曼编码推广至三进制编码,并证明它能产生最优编码。将霍夫曼编码推广至三进制编码 设一个数据文件包含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个概率大小,分别赋予与3个字符对应的值:0、1、2,如此得到最后一个排列3个频度的一位编码。5.此时的3个频度中有一个频度是由前一个排列的3个相加而来,这3个频度就取它的一位编码后面再延长一位编码,得到二位编码,其它不变。6.如此一直往前,直到排列1所有的频度值都被编码为止。举例说明如下(假设Q=9):