为什么mian函数的那个文件里引用了头文件“function.h”,还是显示无法解析外来字符呀,我不是在这个function头文件里面声明了这几个函数吗,然后在新建了一个源文件来定义这几个函数
下面我们来介绍另外一种压缩算法,即哈夫曼算法。在了解哈夫曼算法之前,你必须舍弃半角英文数字的1个字符是1个字节(8位)的数据
。下面我们就来认识一下哈夫曼算法的基本思想。
文本文件是由不同类型的字符组合而成的,而且不同字符出现的次数也是不一样的。例如,在某个文本文件中,A 出现了 100次左右,Q仅仅用到了 3 次,类似这样的情况很常见。哈夫曼算法的关键就在于 多次出现的数据用小于 8 位的字节数表示,不常用的数据则可以使用超过 8 位的字节数表示。A 和 Q 都用 8 位来表示时,原文件的大小就是 100次 * 8 位 + 3次 * 8 位 = 824位,假设 A 用 2 位,Q 用 10 位来表示就是 2 * 100 + 3 * 10 = 230 位。
不过要注意一点,最终磁盘的存储都是以8位为一个字节来保存文件的。
哈夫曼算法比较复杂,在深入了解之前我们先吃点甜品
,了解一下 莫尔斯编码
,你一定看过美剧或者战争片的电影,在战争中的通信经常采用莫尔斯编码来传递信息,例如下面
接下来我们来讲解一下莫尔斯编码,下面是莫尔斯编码的示例
,大家把 1 看作是短点(嘀),把 11 看作是长点(嗒)即可。
莫尔斯编码一般把文本中出现最高频率的字符用短编码
来表示。如表所示,假如表示短点的位是 1,表示长点的位是 11 的话,那么 E(嘀)这一数据的字符就可以用 1 来表示,C(滴答滴答)就可以用 9 位的 110101101
来表示。在实际的莫尔斯编码中,如果短点的长度是 1 ,长点的长度就是 3,短点和长点的间隔就是1。这里的长度指的就是声音的长度。比如我们想用上面的 AAAAAABBCDDEEEEEF 例子来用莫尔斯编码重写,在莫尔斯曼编码中,各个字符之间需要加入表示时间间隔的符号。这里我们用 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字节。
所以使用莫尔斯电码的压缩比为 14 / 17 = 82%。效率并不太突出。