《程序是怎么跑起来的》读书笔记(6) -- 为什么文件可以压缩

文件以字节为单位保存

文件是将数据存储在磁盘等存储媒介中的一种形式
程序文件中存储数据的单位是字节,1字节=8位=256种字节数据

从物理上看,对磁盘进行读写的是扇区为单位,而程序在逻辑上以字节为单位

如果文件里存储的数据是文字,就是文本文件;如果是图形,就是图像文件;文件就是字节数据的集合体

RLE算法(Run Length Encoding 行程长度编码):

AAAAAAABBBBCCC=A7B4C3 成功压缩6/14 适合压缩图像,常用语传真,比如照片打印,各种颜色重复几次
这种算法对于图像等文件十分有效,但对于文字来说:
this is a pen=t1h1i1.....,不但没有压缩,压缩比率大于1接近于2

哈夫曼算法(huffman)

对于一个文件A出现100次,Q只出现了3次,对于这样的情况,原来100 * 8+3 * 8=824,而如果A是2位,Q是10位,也就是230 230/824

哈夫曼算法的关键是多次出现的数据用小于8位的字节数来表示
实现就是谍战剧里面经常演的那种摩尔斯编码,长点和短点交替组合实现
用二叉树实现Huffman算法,目的是尽量让最经常出现的字符用最少位数的编码实现
对于AAAAAABBCDDEEEEEF,按照出现频率进行降序排列:
A6E5B2D2C1F1
找出最小频率的两个数去连,然后逐渐连成一棵树,保证出现频率较低先被连进树里面,枝条数对应着就多,编码就多,反之频率较高的编码就少

可逆压缩和非可逆压缩

windows标准是bmp(bitmap)格式,完全未压缩的
JPEG(Joint Photographic Experts Group)数码相机常用格式 非可逆
TIFF(TAG image File Format)
GIF(Graphics InterChange Format) 可逆,但是GIF的颜色只有256位,所以也会变小
对于图像来说,很多时候不要求必须还原到压缩前同等的质量
因此我们把完全能还原的叫做可逆压缩,不能完全被还原的叫做非可逆压缩

至今,学界和工业界都没有一个万能的压缩算法,大有可为,提示:
文本文件不能进行非可逆的

发表评论

电子邮件地址不会被公开。