数据压缩

字数统计: 1.6k字 | 阅读时长: 5分

2020-08-13

摘要: 本文总结了 leetcode 上的数据压缩相关的题目

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

数据压缩的背景
相似的概念：序列化，序列化/反序列化，编码/解码(加密/解密)，压缩/解压缩
数据压缩算法
- 游程编码
- 莫尔斯编码
- 哈夫曼编码
题目列表
- 数据压缩
- 编码/解码
- 序列化/反序列化

$1 数据压缩

不管是做算法还是做工程的同事应该都用过下面这组 linux 命令

1 2	tar zcvf a.tar a tar zxvf a.tar

尤其是经常做数据搬运的算法同事，数据量很大但是传输资源有限的时候总是先要这么压缩一下。

此外，做计算机视觉这样的工作需要大量接触图片数据，在业务侧图片是用户上传的，上传的时候或者保存在计算机上的时候，也会使用压缩算法进行文件压缩，常见的压缩格式是 JPEG

数据存储

文件 : 在磁盘等媒介存储的数据的集合和抽象(类似与函数是程序的集合和抽象)

文件以字节为单位存储 1字节=1Byte=1B=8bit，1字节表示的字节数据有 $2^{8}=256$ 种(00000000~11111111)。

字节数据可能是文本文件，图片文件等等。

文件是字节数据的集合，其字节数据是连续存储的

数据压缩就是通过一些有别于原始编码的特殊编码方式来保存数据，使数据占用的存储空间比较小。压缩可以减少网络传输时间，但是压缩和解压缩需要时间。

压缩算法

不改变原有文件属性的前提下(文本还是文本，图片还是图片)，降低文件的空间的算方法。包含两步：压缩和解压缩

压缩算法的评价

时间：压缩速度、解压速度
空间：压缩比 = 压缩后所占空间/压缩前所占空间

有损和无损

无损：从压缩后的数据可以重构，准确地还原数据。例如差分编码，游程编码，哈夫曼编码，算术编码。

有损：从压缩后的数据可以重构，但不能准确地还原数据，重构出的数据只是原始数据的近似。好处是压缩比大。例如分形压缩，小波压缩，JPEG/MPEG

对称性

对称编码：编码解码的复杂性差不多
编码比解码难：哈夫曼编码，分形编码
解码比编码难：数据加密

帧内和帧间

帧内：JPEG

帧间：MPEG

$2 相近的概念 — 持久化，序列化/反序列化

以 Python 对象为例，有一个 Python 程序，如果希望在多次执行这个程序之间可以保存程序对象。即望将对象存储在磁盘上，便于以后检索，这就是持久化。

持久化的手段是序列化。它是一个将任意复杂的对象转成对象的文本或二进制表示的过程。同时必须能够将对象经过序列化后的形式恢复到原有的对象。

序列化有三种主要途径，其中前两种序列化是分布式数据处理的基础：

作为一种持久化格式：一个对象序列化以后，他的编码可以存储在磁盘上，供以以后反序列化使用；
作为一种通信数据格式：序列化结果可以从一个正在运行的虚拟机通过网络被传递到另一个虚拟机上；
作为一种克隆机制：将对象序列化到内存的缓冲区中；然后通过反序列化可以得到一个深拷贝的对象；

序列化的常见协议：JSON、XML、Thrift、Protobuf…

在 Python 中，这种序列化过程为 pickle，可以将对象 pickle 成字符串、磁盘上的文件或者任何类似于文件的对象，也可以将这些字符串、文件或任何类似于文件的对象 unpickle 成原来的对象。

$3 题目汇总

3.1 数据压缩

游程编码(RLE)

把文件内容用 数据 * 重复次数 的形式表示

RLE 的缺点：只对特定序列有效，例如图像文件和可执行文件。文本文件无效，因为文本中的连续字符不常见。

莫尔斯编码

把短点视为 1，长点视为 11，短点和长点的分隔符视为 0，字符间隔视为 00，即可将莫尔斯编码转化成字节数据。莫尔斯编码一般把文本中出现最高频率的字符用短编码表示。

804. 唯一摩尔斯密码词

哈夫曼编码

莫尔斯编码是根据日常文本中各个字符出现频率来决定个字符编码长度的，哈夫曼编码在决定字符长度时，是视数据而定的。压缩后的文件存储哈夫曼编码的信息和压缩过的数据。

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

数信息论