(1)首先统计出每个符号出现的频率,上例S0到S7的出现频率分别为414,314,2/14, 1/14,1/14,1/14,1/14,1/14 (2)从左到右把上述频率按从小到大的顺序排列 (3)每一次选出最小的两个值,作为二叉树的两个叶子节点,将和作为它们的根节点, 这两个叶子节点不再参与比较,新的根节点参与比较。 (4)重复(3),直到最后得到和为1的根节点 5)将形成的二叉树的左节点标0,右节点标1。把从最上面的根节点到最下面的叶子 节点途中遇到的0,1序列串起来,就得到了各个符号的编码 上面的例子用 Huffman编码的过程如图91所示,其中圆圈中的数字是新节点产生的顺序 可见,我们上面给出的编码就是这么得到的。 0 8/1406 6/14 4/141 2/14① 2/4②2 3/4③ 1140114011401141020403/14044 0000 00100011100101 图9.1 Huffman编码的示意图 产生 Huffman编码需要对原始数据扫描两遍。第一遍扫描要精确地统计岀原始数据中,每 个值出现的频率,第二遍是建立 Huffman树并进行编码。由于需要建立二叉树并遍历二叉 树生成编码,因此数据压缩和还原速度都较慢,但简单有效,因而得到广泛的应用 源程序就不给出了,有兴趣的读者可以自己实现 92行程编码 行程编码( Run Length Coding)的原理也很简单:将一行中颜色值相同的相邻象素用一个计数 值和该颜色值来代替。例如 aaabccccccddeee可以表示为3ab6c2d3e。如果一幅图象是由很 多块颜色相同的大面积区域组成,那么采用行程编码的压缩效率是惊人的。然而,该算法也 导致了一个致命弱点,如果图象中每两个相邻点的颜色都不同,用这种算法不但不能压缩 反而数据量增加一倍。所以现在单纯采用行程编码的压缩算法用得并不多,PCX文件算是 其中的一种(1) 首先统计出每个符号出现的频率，上例 S0 到 S7 的出现频率分别为 4/14，3/14，2/14， 1/14，1/14，1/14，1/14，1/14。 (2) 从左到右把上述频率按从小到大的顺序排列。 (3) 每一次选出最小的两个值，作为二叉树的两个叶子节点，将和作为它们的根节点， 这两个叶子节点不再参与比较，新的根节点参与比较。 (4) 重复(3)，直到最后得到和为 1 的根节点。 (5) 将形成的二叉树的左节点标 0，右节点标 1。把从最上面的根节点到最下面的叶子 节点途中遇到的 0,1 序列串起来，就得到了各个符号的编码。 上面的例子用 Huffman 编码的过程如图 9.1 所示，其中圆圈中的数字是新节点产生的顺序。 可见，我们上面给出的编码就是这么得到的。 图 9.1 Huffman 编码的示意图 产生 Huffman 编码需要对原始数据扫描两遍。第一遍扫描要精确地统计出原始数据中，每 个值出现的频率，第二遍是建立 Huffman 树并进行编码。由于需要建立二叉树并遍历二叉 树生成编码，因此数据压缩和还原速度都较慢，但简单有效，因而得到广泛的应用。 源程序就不给出了，有兴趣的读者可以自己实现。 9.2 行程编码 行程编码(Run Length Coding)的原理也很简单：将一行中颜色值相同的相邻象素用一个计数 值和该颜色值来代替。例如 aaabccccccddeee 可以表示为 3a1b6c2d3e。如果一幅图象是由很 多块颜色相同的大面积区域组成，那么采用行程编码的压缩效率是惊人的。然而，该算法也 导致了一个致命弱点，如果图象中每两个相邻点的颜色都不同，用这种算法不但不能压缩， 反而数据量增加一倍。所以现在单纯采用行程编码的压缩算法用得并不多，PCX 文件算是 其中的一种