您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

数据压缩算法

时间:2020-06-07 17:27:32  来源:  作者:

概述

之前在听到数据压缩的时候, 想着肯定是某些高深莫测的算法, 能够完成数据的压缩这种事情, 最近看了看, 嗯, 至少咱还是能看懂的.

无损压缩

众所周知, 不管你是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 压缩文件是日常使用中较为常见的压缩格式了, 它就是使用了上面的方案二和方案三进行压缩处理的结果. 其压缩步骤如下:

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

据说, 在步骤二上会有些优化处理, 将文件分为多个不同的小块, 针对不同的小块单独进行编码, 以此实现不同文件的高效压缩.

其他

当然, 不仅仅是文件的 zip 压缩, 包括在很多网络传输中, 为了减少传输的包体积, 也会将文件进行压缩后再发送.

有损压缩

上面的无损压缩, 在将压缩文件解压后, 能够完全恢复压缩前的文件. 虽然已经很好了, 但是有损压缩的压缩文件要比它小很多, 当然代价就是无法还原. 不要以为没有用哦. 还记得在线看视频时, 会根据当前网速, 选择标清 高清 超清 等格式, 清晰度越低, 对应消耗的流量就越少.

对于有损压缩 就需要针对不同的文件进行不同的处理了. 咱也没有看, 咱也不敢说. 就简单举个例子.

图片压缩

比如一张 1080*1080 分辨率的图片, 为了记住图片上的每个像素点, 就需要 1080*1080 个内容来保存. 这里, 如果将相邻的两个像素点, 统一使用左侧的保存, 将右侧的丢掉, 也就是每两列像素丢掉一列, 整体的大小就减少一倍了. 当然, 相对应的, 图片的清晰度也会下降.

当然, 这种直接丢弃的方式有些粗暴了, jpeg的压缩方式据说不错, 不过我还没有看. 至于其他的视频啊, 音频啊, 都有吧. 嗯, 我想.

总结

在数据的无损压缩上, 思想基本就是减少重复的数据, 不管是重复数据复制, 还是哈夫曼编码都可以说是围绕着这个思想来的.

在看过压缩编码之后, 让我想起了之前看到的纠错码. 纠错码是怎么处理的? 往原来的数据中添加内容, 通过数据冗余来进行纠错, 而压缩呢? 将源文件中的数据通过转换使得其体积减小. 有点意思, 就像一个事情的正反两面, 没有孰是孰非, 就看你怎么去用它了.



Tags:算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Tags: 算法  点击:(1)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  Tags: 算法  点击:(7)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15  Tags: 算法  点击:(16)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯·奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  Tags: 算法  点击:(24)  评论:(0)  加入收藏
基于算法的业务或者说AI的应用在这几年发展得很快。但是,在实际应用的场景中,我们经常会遇到一些非常奇怪的偏差现象。例如,Facebook将黑人标记为灵长类动物、城市图像识别系统...【详细内容】
2021-11-08  Tags: 算法  点击:(32)  评论:(0)  加入收藏
随着注册制的加速推进,新股越来越多,截止到今天A股上市公司的总数高达4500余家,A股一直就是重融资,轻投资的市场,而上市公司发行可转债这种再融资的(圈钱方式)是最能让普通投资者接...【详细内容】
2021-11-05  Tags: 算法  点击:(98)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  Tags: 算法  点击:(40)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  Tags: 算法  点击:(36)  评论:(0)  加入收藏
每个人都有过这样的经历:打开手机准备回消息或打电话,一看到微信图标右上方的小红点,于是忍不住先打开微信;看完微信,不知不觉又被另一个App牵引,直到关闭手机屏幕才发现自己早已...【详细内容】
2021-11-03  Tags: 算法  点击:(30)  评论:(0)  加入收藏
文丨互联网怪盗团在互联网行业,尤其是在投资人心目中,往往存在一种“算法迷信”或曰“技术迷信”:某公司的广告变现做得好,一定是因为有算法;某公司的云计算业务开展的好,也是因为...【详细内容】
2021-11-03  Tags: 算法  点击:(25)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(11)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(22)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(14)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯·奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(40)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条