数据压缩算法 _算法

概述之前在听到数据压缩的时候, 想着肯定是某些高深莫测的算法, 能够完成数据的压缩这种事情, 最近看了看, 嗯, 至少咱还是能看懂的.
无损压缩【数据压缩算法】众所周知, 不管你是exe, word, txt, dmg等等, 在存储上都是以二进制进行存储的, 所以, 在讨论压缩时, 忽略文件格式即可, 只要将其看做一串数字即可.
方案一开始了, 上数字串: 11111111111111111111.
如果让你向别人口述这个字符串, 你会如何讲, "1111...1111". 我估计就算你这么讲, 人家听半天也没听明白你说的到底是几个1. 但是, 如果你这么说的话, 就不一样了: "20个1". 人家一听就明白了.
你以为这种方式用不到? 天真, 如果是一张黑白照片, 上面的每一个像素点, 非黑即白, 连续的相同内容必然有很多, 如此处理之后, 自然也会小的多. 当然, 这也存在这一定的局限性, 重复内容中间不能被隔开.
这是一种压缩的方式, 处理重复数据.
方案二再上一个数字串:
123456-78-123456-987-12345678
从我在这个字符串中打的波折号标记, 大概就能猜到该如何处理了吧. 后面的内容与前面的相同, 即重复数据. 那就可以去前面抄啊. 此数字串的处理方式如下: 123456 78 (返回8个, 复制6个) 987 (返回17个, 复制8个) 当然, 真正压缩后的数字串后没有这一坨中文, 以一个标志编码来表示, 咱就假设是r(return) 和 c (copy)吧. 那上面的数字串就变成了这样: 123456-78-r8c6-987-r17c8
这里有个很有意思的地方, 回忆一下方案一的20个1. 用这种copy 方式也能表示: 1r1c19. 往回数1个, 复制19个, 虽然前面只有一个数字, 但是随着复制, 长度是会变化的, 复制一个, 长度就对应变长, 就又可以复制新的一位了, 以此类推. 如何, 有意思吧.
这也是一种压缩的思路, 向前复制数据.
方案三这里为了方便说, 需要引用一下字母了.
看这个字符串: aaaaaaaaaaaaabc.
每个字母为了存储都需要进行编码, ASCII 编码下: a(97), b(98), c(99). 每个字母两位数, 那这个长度15的字符串就需要: 15*2=30位数字表示. 想必已经发现了, 此字符串字母 a 大量出现, 如果字母 a 能够用一位数字表示, 那整体长度就小得多了. 那我用9来表示 a 不就行了?
并不是, 如果你不做特殊标志的话, 计算机并不能分辨出98 应该是 9和8, 还是98. 所以, 需要有个标志, 比如, 以7开头的, 说明是1位编码, 以2开头的都是三位编码等等.
这个就厉害了, 是不是看出了什么, 没有错, 正是大名鼎鼎的哈夫曼编码. 将使用频率更高的内容使用更短的编码表示, 代价就是用较长的编码表示频率较低的内容. 对于哈夫曼编码就不多说了, 这玩意能单独写一篇.
你以为哈夫曼编码只能用来压缩文本文档? no. 它只需要是一个二进制串即可. 毕竟文本文档写到磁盘中也不过是二进制串. 你可以将二进制文件中的每块(比如2个字节)想象为上面的字母, 就可以直接使用哈夫曼编码进行处理了.
ZIP 压缩格式zip 压缩文件是日常使用中较为常见的压缩格式了, 它就是使用了上面的方案二和方案三进行压缩处理的结果. 其压缩步骤如下:

将文件使用方案二将大部分重复内容去掉.
将步骤一的处理结果, 通过哈夫曼编码进行处理, 用较短的编码表示频率较高的内容. 当然, 在这个步骤需要生成并记录一个编码对照表, 毕竟每个文件的高频率内容是不同的.
将步骤二中的结果直接输出保存到zip文件中, 包括编码表(毕竟还要解压嘛). 完成

据说, 在步骤二上会有些优化处理, 将文件分为多个不同的小块, 针对不同的小块单独进行编码, 以此实现不同文件的高效压缩.
其他当然, 不仅仅是文件的 zip 压缩, 包括在很多网络传输中, 为了减少传输的包体积, 也会将文件进行压缩后再发送.
有损压缩上面的无损压缩, 在将压缩文件解压后, 能够完全恢复压缩前的文件. 虽然已经很好了, 但是有损压缩的压缩文件要比它小很多, 当然代价就是无法还原. 不要以为没有用哦. 还记得在线看视频时, 会根据当前网速, 选择标清高清超清等格式, 清晰度越低, 对应消耗的流量就越少.
对于有损压缩就需要针对不同的文件进行不同的处理了. 咱也没有看, 咱也不敢说. 就简单举个例子.
图片压缩比如一张 1080*1080 分辨率的图片, 为了记住图片上的每个像素点, 就需要 1080*1080 个内容来保存. 这里, 如果将相邻的两个像素点, 统一使用左侧的保存, 将右侧的丢掉, 也就是每两列像素丢掉一列, 整体的大小就减少一倍了. 当然, 相对应的, 图片的清晰度也会下降.