酷客网通过莫尔斯编码来看哈夫曼算法，压缩技巧实际上有很多种。接下来，我们就来看一下本章要介绍的第二个压缩技巧，即哈夫曼算法。哈夫曼算法是哈夫曼（D. A. Huffman）于1952年提出来的压缩算法。日本人比较常用的压缩软件LHA，使用的就是哈夫曼算法。
为了更好地理解哈夫曼算法，首先大家要抛弃掉“半角英文数字的1个字符是1个字节（8位）的数据”这一概念。文本文件是由不同类型的字符组合而成的，而且不同的字符出现的次数也是不同的。例如，在某一个文本文件中，A出现了100次左右，Q仅用到了3次，类似这样的情况是很常见的。而哈夫曼算法的关键就在于“多次出现的数据用小于8位的字节数来表示，不常用的数据则可以用超过8位的字节数来表示”。A和Q都用8位来表示时，原文件的大小就是100次× 8位 + 3次× 8位=824位，而假设A用2位、Q用10位来表示，压缩后的大小就是100次×2位+3次×10位=230位。
不过有一点需要注意，不管是不满8位的数据，还是超过8位的数据，最终都要以8位为单位保存到文件中。这是因为磁盘是以字节（8位）为单位来保存数据的（图6-3）。为了实现这一处理，压缩程序的内容会复杂很多，不过作为回报，最终得到的压缩率也是相当高的。
图6-3 非8位数据的读写
下面让我们把当前的话题暂时放下，为了更好地理解哈夫曼算法，先来看一下莫尔斯编码。莫尔斯编码是1837年莫尔斯（Samuel F. B. Morse）提出的。莫尔斯编码不是通过语言，而是通过“嗒嘀嗒嘀”这些长点和短点的组合来传递文本信息的。想必大家在电影中也都看到过发送莫尔斯电码的设备。
接下来我们就来仔细讲解一下莫尔斯编码。对数字领域比较熟悉的读者可能会认为“莫尔斯编码的短点是0，长点是1，其中1个字符用8位来表示”，但实际上，根据字符种类的不同，莫尔斯电码符号的长度也是不同的。表6-2是莫尔斯编码的示例。大家把1看作是短点（嘀），把11看作是长点（嗒）即可。
表6-2 莫尔斯编码和位长
1：短点、11：长点、0：短点和长点的分隔符
莫尔斯编码把一般文本中出现频率高的字符用短编码来表示。这里所说的出现频率，不是通过对出版物等文章进行统计调查得来的，而是根据印刷行业的印刷活字数目而确定的。如表6-2所示，假设表示短点的位是1，表示长点的位是11的话，那么E（嘀）这一字符的数据就可以用1位的1来表示，C（嗒嘀嗒嘀）这一字符的数据就可以用9位的110101101来表示。在实际的莫尔斯编码中，如果短点的长度是1，长点的长度就是3，短点和长点的间隔就是1。这里的长度指的是声音的长度。接下来，就让我们尝试一下用莫尔斯编码来表示前面提到的AAAAAABBCDDEEEEEF这个17个字符的文本。在莫尔斯编码中，各个字符之间需要加入表示间隔的符号。这里我们用00来进行区分。因此，AAAAAABBCDDEEEEEF这个文本，就变成了A× 6次+ B× 2次+C× 1次+D× 2次+ E × 5次+F × 1次 +字符间隔× 16=4位× 6次+ 8位× 2次+9位× 1次+6位× 2次+1位× 5次+8位× 1次+ 2位× 16次=106位 ≒ 14字节。因为文件只能以字节为单位来存储数据，因此不满1字节的部分就要圆整成1个字节。如果所有字符占用的空间都是1个字节（8位），这样文本中列出来的17个字符=17字节，那么摩尔斯电码的压缩比率就是14÷17≒82％，并不太突出。
酷客网相关文章：
评论前必须登录！
注册