精选优质文档-倾情为你奉上题目：将霍夫曼编码推广至三进制编码，并证明它能产生最优编码。将霍夫曼编码推广至三进制编码 设一个数据文件包含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）：
