JX算法分析与设计贪心算法.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 活动安排问题 贪心算法的基本要素 最优装载 哈夫曼编码 单源最短路径 主要内容 * 哈夫曼编码(1) 哈夫曼编码( Huffman Codes，P109 )：广泛用于数据文件(如传真、图像)的无损压缩，压缩率常在20%~90%之间。 文件编码问题描述： 给定一个文件，该文件长度为 100,000 个字符，其中包含a, b, c, d, e和f 六种字符，各字符出现频率如下表，试对该文件进行编码存储。 a b c d e f 频率(千次) 45 13 12 16 9 5 * 哈夫曼编码(2) 定长码(Fixed-length Codeword)存储： a b c d e f 频率(千次) 45 13 12 16 9 5 编码 000 001 010 011 100 101 定长码文件长度为：3*100,0000=300,000 位(bits) 变长码(Variable-length Codeword)存储(Huffman编码)： a b c d e f 频率(千次) 45 13 12 16 9 5 编码 0 101 100 111 1101 1100 变长码文件长度为：45*1+13*3+12*3+16*3+9*4+5*4=224,000 位(bits) * 哈夫曼编码(3) 变长编码的贪心策略2：频率越高，使用越少编码位。 a b c d e f 频率(千次) 45 13 12 16 9 5 编码 0 1 10 11 100 101 变长码文件长度为：45*1+13*1+12*2+16*2+9*3+5*3=156,000 位(bits)，这样得到了最大压缩率，但是这样存在解码问题。示例如下： abcdef 011011100101 贪心策略2： (解码歧义) abcdef 010110011111011100 Huffman编码： (解码无歧义) * 哈夫曼编码(4) 前缀码 (Prefix Codes)的概念： 对每个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀。这种编码称为前缀码。 前缀码的性质使译码方法非常简单，例如：001011101，根据上述编码可直接译出：aabe。 Huffman提出了最优前缀码的贪心算法。 David A. Huffman ( 1925.08 - 1999.10 ) 1944年在俄亥俄州立大学(Ohio State University)获学士学位。 1945-1946年在美国海军服役，工作内容是在驱逐舰上维护雷达。 1949年在俄亥俄州立大学获硕士学位。1953年在MIT获博士学位，在攻读博士学位期间提出了Huffman编码( “A Method for the Construction of Minimum-Redundancy Codes”，1952年)。 1953-1967年工作于MIT，之后作为主创人之一去了加州大学圣克鲁斯分校(University of California, Santa Cruz)创建了信息科学系，并一直工作到1994年退休。 1955年，因在时序继电电路(Sequential Switching Circuits)方面的贡献获富兰克林科学博物馆(Franklin Institute)的Louis E. Levy奖章。 1999年，因在信息科学方面的贡献获 IEEE Richard W. Hamming奖。 * 哈夫曼编码(5) 使用前缀码 (Prefix Codes)的译码示例(序列：001011101)： 001011101 00=a，循环查找出只有a的前缀为0 1) 001011101 0 1011101 0=a，循环查找出只有a的前缀为0 2) 001011101 1 011101 循环查找出b~e的前缀为1，继续扫描 3) 001011101 4) 10 11101 循环查找出b, c的前缀为10，继续扫描 001011101 5) 101 1101 101=b，循环查找出只有b的前缀为101 同理解出 1101=e，从而得到字符序列为aabe，但可发现循环查找匹配前缀的速度慢。 * 哈夫曼编码(6) 提高前缀匹配速度：前缀码的二叉树(Binary Tree)表示。 字符 a b c d e f 编码 0 101 100 111 1101 1100 说明： 1) 该二叉树是一颗满二叉树。 2) 使用该满二叉树在匹配前缀时，只会是查找左边或右边，不会出现需要同时查找两边的情况。 3) 每个字