Lecture 5. Greedy algorithm Huffman Codes Huffman codes用于数据压缩一般可以达到 · Huffman code 压缩20%到90%的效果。 Matroid(拟阵) 什么是编码:编码实质上是用给定的一组 符号集的字符串到另外一组符号集的映 射。 例如用{0,1}字符串到所有英文字符{abc…} 的映射的8位码 清华大学們学院宋恒 清华大学软件学院宋 Prefix codes ·我们只考虑任一个编码字不是另一个编码 Fixed-length codeword 000 001 010 011 100 101 的前缀的编码。 ariable-length codeword 0 101 ·这样的编码叫 Prefix Codes Figure 163 A character-coding problem. A data 下页给出几种编码例子 file of 100,000 characters contains only the characters a-f, with the frequencies indicated. If each character is assigned a 3-bit codeword, the file can be encoded in 300.000 bits. Using the variable-length code shown, the file can be 清华大学学院未恒 编码表示方式 Prefix codes are desirabl because they simplify decoding 利用树来表示,下图表示等长编码 示例:在上图非定长编码下 0001110101唯一代表字符串 aaaeab 清华大学轼字院宋恒 消华大学软件学院宋1 清华大学软件学院宋斌恒 1 Lecture 5. Greedy Algorithm •Huffman code •Matroid（拟阵） 清华大学软件学院宋斌恒 2 Huffman Codes •Huffman codes用于数据压缩一般可以达到 压缩20％到90%的效果。 •什么是编码：编码实质上是用给定的一组 符号集的字符串到另外一组符号集的映 射。 •例如用{0,1}字符串到所有英文字符{a,b,c,… } 的映射的8位码 清华大学软件学院宋斌恒 3 Prefix codes •我们只考虑任一个编码字不是另一个编码 字的前缀的编码。 •这样的编码叫Prefix Codes。 •下页给出几种编码例子： a b c d e f Frequency (in thousands) 45 13 12 16 9 5 Fixed-length codeword 000 001 010 011 100 101 Variable-length codeword 0 101 100 111 1101 1100 Figure 16.3 A character-coding problem. A data file of 100,000 characters contains only the characters a-f, with the frequencies indicated. If each character is assigned a 3-bit codeword, the file can be encoded in 300,000 bits. Using the variable-length code shown, the file can be encoded in 224,000 bits. 清华大学软件学院宋斌恒 5 Prefix codes are desirable because they simplify decoding. •示例：在上图非定长编码下，串 0001110101唯一代表字符串aaaeab 清华大学软件学院宋斌恒 6 编码表示方式 •利用树来表示，下图表示等长编码： 100 86 58 28 a:45 b:13 c:12 d:16 e:9 f:5 14 14