霍夫曼编码和贪婪算法 _霍夫曼编码

本文概述

前缀代码
构造霍夫曼码的贪婪算法

（i）可以使用霍夫曼码对数据进行有效编码。
（ii）它是一种广泛使用的有益数据压缩技术。
（iii）霍夫曼的贪婪算法使用每个字符出现频率的表来建立将每个字符表示为二进制字符串的最佳方式。

假设我们在一个数据文件中有105个字符。普通存储：每个字符8位（ASCII）-文件中8 x 105位。但是我们要压缩文件并紧凑地保存它。假设文件中仅出现六个字符：

文章图片
我们如何以紧凑的方式表示数据？
（i）固定长度代码：每个字母由相等位数表示。使用固定长度的代码, 每个字符至少3位：
例如：

a000b001c010d011e100f101

对于具有105个字符的文件, 我们需要3 x 105位。
（ii）可变长度代码：通过给许多字符提供短代码字而很少给字符提供长代码字, 它可以比定长代码做得更好。
例如：

a0b101c100d111e1101f1100 Number of bits = (45 x 1 + 13 x 3 + 12 x 3 + 16 x 3 + 9 x 4 + 5 x 4) x 1000 = 2.24 x 105bits

因此, 用224, 000位表示该文件, 节省了大约25％。这是此文件的最佳字符代码。
前缀代码一个字符编码的前缀不能等于另一字符的完整编码, 例如1100和11001是无效代码, 因为1100是某些其他代码字的前缀, 称为前缀代码。
前缀代码是可取的, 因为它们阐明了编码和解码。对于任何二进制字符代码, 编码总是很简单；我们将描述文件每个字符的代码字连接起来。使用前缀代码也很容易解码。由于没有代码字是任何其他字词的前缀, 因此以编码数据开头的代码字是明确的。
构造霍夫曼码的贪婪算法霍夫曼（Huffman）发明了一种贪心算法, 该算法可创建称为霍夫曼码（Huffman Code）的最佳前缀代码。