你好,我是四火。
今天,我们来继续学习一些全栈开发中影响深远的算法,我们这次的归类是无损压缩算法。无损压缩,顾名思义就是经过压缩以后,数据的大小降下来了,但是只要经过还原,原始数据是一点都不丢失的。和无损压缩对应的,显然就叫做“有损压缩”了,它们能够做到在牺牲一定程度原数据质量的基础上,比有损压缩获得额外的压缩比。
无损压缩的算法其实有很多,但无论是哪一种,里面都没有多么神奇的把戏,它们的最基本原理都是一致的,就是利用数据的重复性(冗余性)。在经过某种无损压缩以后,由于数据的重复性已经降下来了,因此再压缩就无法获益了。
哈夫曼编码
不管是在哪一本系统介绍压缩算法的书中,那么多的无损压缩算法,哈夫曼编码(Huffman Coding)基本都是需要我们最先接触学习的那一个。哈夫曼编码从原理上看,它会根据字符的出现频率,来决定使用怎样的编码方式,并且是变长编码的一种。相应地,程序员熟悉的 ASCII 码,就是定长编码,因为总共就 128 个字符,不管是哪一个字符,占用的长度都是一样的。
下面我们来看一下哈夫曼编码的大致过程:
首先,统计被加密数据中每个字符出现的频率,把它们从高到低排好。比如下面这个表,就是某一段文字的字母出现的次数统计表格,你可以看到这些字母出现的次数是从左到右依次增加的: