PFC解码-sae j1772-2017

第5章 二叉树 §5.5 Huffman编码 139  解码 13 void decode ( PFCTree* tree, Bitmap& code, int n ) { //PFC解码算法 14 BinNodePosi ( char ) x = tree->root(); //根据PFC编码树 15 for ( int i = 0; i < n; i++ ) { //将编码（二迕刢位图） 16 x = code.test ( i ) ? x->rc : x->lc; //转译为明码幵 17 if ( IsLeaf ( *x ) ) { printf ( "%c", x->data ); x = tree->root(); } //打印输出 18 } 19 } 代码5.27 PFC解码  优化 在介绍过PFC及其实现方法后，以下将就其编码效率做一分析，并设计出更佳的编码方法。 同样地，我们依然暂且忽略硬件成本和信道误差等因素，而主要考查如何高效率地完成文本 信息的编码和解码。不难理解，在计算资源固定的条件下，不同编码方法的效率主要体现于所生 成二进制编码串的总长，或者更确切地，体现于二进制码长与原始文本长度的比率。 那么，面对千变万化、长度不一的待编码文本，从总体上我们应该按照何种尺度来衡量这一 因素呢？基于这一尺度，又该应用哪些数据结构来实现相关的算法呢？ 5.5.2 最优编码树 在实际的通讯系统中，信道的使用效率是个很重要的问题，这在很大程度上取决于编码算法 本身的效率。比如，高效的编码算法生成的编码串应该尽可能地短。那么，如何做到这一点呢？ 在什么情况下能够做到这一点呢？以下首先来看如何对编码长度做“度量”。  平均编码长度与叶节点平均深度 由5.2.2节的结论，字符x的编码长度|rps(x)|就是其对应叶节点的深度depth(v(x))。于 是，各字符的平均编码长度就是编码树T中各叶节点的平均深度（average leaf depth）： ald(T) = x |rps(x)| / || = x depth(x) / || 以如图5.9(a)所示编码树为例，字符'A'、'E'和'G'的编码长度为2，'M'和'S'的编码长度为3， 故该编码方案的平均编码长度为： ald(T) = (2 + 2 + 2 + 3 + 3) / 5 = 2.4 既然ald(T)值是反映编码效率的重要指标，我们自然希望这一指标尽可能地小。  最优编码树 同一字符集的所有编码方案中，平均编码长度最小者称作最优方案；对应编码树的ald()值 也达到最小，故称之为最优二叉编码树，简称最优编码树（optimal encoding tree）。 对于任一字符集，深度不超过||的编码树数目有限，故在其中ald()值最小者必然存在。 需注意的是，最优编码树不见得唯一（比如，同层节点互换位置后，并不影响全树的平均深度）， 但从工程的角度看，任取其中一棵即可。 为导出最优编码树的构造算法，以下需从更为深入地了解最优编码树的性质入手。