比较常见的有JPEG 也就是JPG的压缩算法GIF的索引色压缩算法PNG使用从LZ77派生的无损数据压缩算法TIFF用的是7z算法这只是常用图形文件的压缩算法 更详细的就需要查资料了 我记不住。。
B. 多媒体数据压缩算术研究 论文笔记
多媒体图像压缩技术
姓名:Vencent Lee
摘要：多媒体数据压缩技术是现代网络发展的关键性技术之一。由于图像和声音信号中存在各种各样的冗余，为数据压缩提供了可能。数据压缩技术有无损压和有损压缩两大类，这些压缩技术又各有不同的标准。
一、多媒体数据压缩技术
仙农(C．E．Shannon)在创立信息论时，提出把数据看作是信息和冗余度的组合。早期的数据压缩之所以成为信息论的一部分是因为它涉及冗余度问题。而数据之所以能够被压缩是因为其中存在各种各样的冗余；其中有时间冗余性、空间冗余性、信息熵冗余、先验知识冗余、其它冗余等。时间冗余是语音和序列图像中常见的冗余，运动图像中前后两帧间就存在很强的相关性，利用帧间运动补兴就可以将图像数据的速率大大压缩。语音也是这样。尤其是浊音段，在相当长的时间内(几到几十毫秒)语音信号都表现出很强的周期性，可以利用线性预测的方法得到较高的压缩比。空间冗余是用来表示图像数据中存在的某种空间上的规则性，如大面积的均匀背景中就有很大的空间冗余性。信息熵冗余是指在信源的符号表示过程中由于未遵循信息论意义下最优编码而造成的冗余性，这种冗余性可以通过熵编码来进行压缩，经常使用的如Huff-man编码。先验知识冗余是指数据的理解与先验知识有相当大的关系，如当收信方知道一个单词的前几个字母为administrato时，立刻就可以猜到最后一个字母为r，那么在这种情况下，最后一个字母就不带任何信息量了，这就是一种先验知识冗余。其它冗余是指那些主观无法感受到的信息等带来的冗余。
通常数据压缩技术可分为无损压缩(又叫冗余压缩)和有损压缩(又叫熵压缩)两大类。无损压缩就是把数据中的冗余去掉或减少，但这些冗余量是可以重新插入到数据中的，因而不会产生失真。该方法一般用于文本数据的压缩，它可以保证完全地恢复原始数据；其缺点是压缩比小(其压缩比一般为2：1至5：1)。有损压缩是对熵进行压缩，因而存在一定程度的失真；它主要用于对声音、图像、动态视频等数据进行压缩，压缩比较高(其压缩比一般高达20：1以上。最新被称为“E—igen—ID”的压缩技术可将基因数据压缩1．5亿倍)。对于多媒体图像采用的有损压缩的标准有静态图像压缩标准(JPEG标准，即‘JointPhotographicExpertGroup’标准)和动态图像压缩标准(MPEG标准，即‘MovingPictureExpertGroup’标准)。
JPEG利用了人眼的心理和生理特征及其局限性来对彩色的、单色的和多灰度连续色调的、静态图像的、数字图像的压缩，因此它非常适合不太复杂的以及一般来源于真
实景物的图像。它定义了两种基本的压缩算法：一种是基于有失真的压缩算法，另一种是基于空间线性预测技术(DPCM)无失真的压缩算法。为了满足各种需要，它制定了四种工作模式：无失真压缩、基于DCT的顺序工作方式、累进工作方式和分层工作方式。
MPEG用于活动影像的压缩。MPEG标准具体包三部分内容：(1)MPEG视频、(2)MPEG音频、(3)MP系统(视频和音频的同步)。MPEG视频是标准的核心分，它采用了帧内和帧间相结合的压缩方法，以离散余变换(DCT)和运动补偿两项技术为基础，在图像质量基不变的情况下，MPEG可把图像压缩至1／100或更MPEG音频压缩算法则是根据人耳屏蔽滤波功能。利用音响心理学的基本原理，即“某些频率的音响在重放其频率的音频时听不到”这样一个特性，将那些人耳完全不到或基本上听到的多余音频信号压缩掉，最后使音频号的压缩比达到8：1或更高，音质逼真，与CD唱片可媲美。按照MPEG标准，MPEG数据流包含系统层和压层数据。系统层含有定时信号，图像和声音的同步、多
分配等信息。压缩层包含经压缩后的实际的图像和声数据，该数据流将视频、音频信号复合及同步后，其数据输率为1．5MB／s。其中压缩图像数据传输率为1．2M压缩声音传输率为0．2MB／s。
MPEG标准的发展经历了MPEG—I,MPEG一2、MPEG一4、MPEG-7、MPEG一21等不同层次。在MPEG的不同标准中，每—个标准都是建立在前面的标准之上的，并与前面的标准向后的兼容。目前在图像压缩中，应用得较多的是MPEG一4标准，MPEG-是在MPEG-2基础上作了很大的扩充，主要目标是多媒体应用。在MPEG一2标准中，我们的观念是单幅图像，而且包含了一幅图像的全部元素。在MPEG一4标准下，我们的观念变为多图像元素，其中的每—个多图像元素都是独立编码处理的。该标准包含了为接收器所用的指令，告诉接收器如何构成最终的图像。
上图既表示了MPEG一4解码器的概念，又比较清楚地描绘了每个部件的用途。这里不是使用单一的视频或音频解码器，而是使用若干个解码器，其中的每一个解码器只接收某个特定的图像(或声音)元素，并完成解码操作。每个解码缓冲器只接收属于它自己的灵敏据流，并转送给解码器。复合存储器完成图像元素的存储，并将它们送到显示器的恰当位置。音频的情况也是这样，但显然不同点是要求同时提供所有的元素。数据上的时间标记保证这些元素在时间上能正确同步。MPEG一4标准对自然元素(实物图像)和合成元素进行区分和规定，计算机生成的动画是合成元素的一个例子。比如，一幅完整的图像可以包含一幅实际的背景图，并在前面有一幅动画或者有另外一幅自然图像。这样的每一幅图像都可以作最佳压缩，并互相独立地传送到接收器，接收器知道如何把这些元素组合在一起。在MPEG一2标准中，图像被看作一个整体来压缩；而在MPEG一4标准下，对图像中的每一个元素进行优化压缩。静止的背景不必压缩到以后的I帧之中去，否则会使带宽的使用变得很紧张。而如果这个背景图像静止10秒钟，就只要传送一次(假设我们不必担心有人在该时间内切人此频道)，需要不断传送的仅是前台的比较小的图像元素。对有些节目类型，这样做会节省大量的带宽。MPEG一4标准对音频的处理也是相同的。例如，有一位独唱演员，伴随有电子合成器，在MPEG一2标准下，我们必须先把独唱和合成器作混合，然后再对合成的音频信号进行压缩与传送。在MPEG一4标准下，我们可以对独唱作单独压缩，然后再传送乐器数字接口的声轨信号，就可以使接收器重建伴音。当然，接收器必须能支持MIDI放音。与传送合成的信号相比，分别传送独唱信号和MIDI数据要节省大量的带宽。其它的节目类型同样可以作类似的规定。MPEG一7标准又叫多媒体内容描述接口标准。图像可以用色彩、纹理、形状、运动等参数来描述，MPEG一7标准是依靠众多的参数对图像与声音实现分类，并对它们的数据库实现查询。
二、多媒体数据压缩技术的实现方法
目前多媒体压缩技术的实现方法已有近百种，其中基于信源理论编码的压缩方法、离散余弦变换(DCT)和小波分解技术压缩算法的研究更具有代表性。小波技术突破了传统压缩方法的局限性，引入了局部和全局相关去冗余的新思想，具有较大的潜力，因此近几年来吸引了众多的研究者。在小波压缩技术中，一幅图像可以被分解为若干个叫做“小片”的区域；在每个小片中，图像经滤波后被分解成若干个低频与高频分量。低频分量可以用不同的分辨率进行量化，即图像的低频部分需要许多的二进制位，以改善图像重构时的信噪比。低频元素采用精细量化，高频分量可以量化得比较粗糙，因为你不太容易看到变化区域的噪声与误差。此外，碎片技术已经作为一种压缩方法被提出，这种技术依靠实际图形的重复特性。用碎片技术压缩图像时需要占用大量的计算机资源，但可以获得很好的结果。借助于从DNA序列研究中发展出来的模式识别技术，能减少通过WAN链路的流量，最多时的压缩比率能达到90％，从而为网络传送图像和声音提供更大的压缩比，减轻风络负荷，更好地实现网络信息传播。
三、压缩原理
由于图像数据之间存在着一定的冗余，所以使得数据的压缩成为可能。信息论的创始人Shannon提出把数据看作是信息和冗余度（rendancy）的组合。所谓冗余度，是由于一副图像的各像素之间存在着很大的相关性，可利用一些编码的方法删去它们，从而达到减少冗余压缩数据的目的。为了去掉数据中的冗余，常常要考虑信号源的统计特性，或建立信号源的统计模型。图像的冗余包括以下几种：
(1) 空间冗余：像素点之间的相关性。
(2) 时间冗余：活动图像的两个连续帧之间的冗余。
(3) 信息熵冗余：单位信息量大于其熵。
(4) 结构冗余：图像的区域上存在非常强的纹理结构。
(5) 知识冗余：有固定的结构，如人的头像。
(6) 视觉冗余：某些图像的失真是人眼不易觉察的。
对数字图像进行压缩通常利用两个基本原理：
(1) 数字图像的相关性。在图像的同一行相邻像素之间、活动图像的相邻帧的对应像素之间往往存在很强的相关性，去除或减少这些相关性，也就去除或减少图像信息中的冗余度，即实现了对数字图像的压缩。
(2) 人的视觉心理特征。人的视觉对于边缘急剧变化不敏感(视觉掩盖效应)，对颜色分辨力弱，利用这些特征可以在相应部分适当降低编码精度，而使人从视觉上并不感觉到图像质量的下降，从而达到对数字图像压缩的目的。
编码压缩方法有许多种，从不同的角度出发有不同的分类方法，比如从信息论角度出发可分 为两大类：
(1)冗余度压缩方法，也称无损压缩，信息保持编码或熵编码。具体讲就是解码图像和压缩 编码前的图像严格相同，没有失真，从数学上讲是一种可逆运算。
(2)信息量压缩方法，也称有损压缩，失真度编码或熵压缩编码。也就是讲解码图像和原始图像是有差别的，允许有一定的失真。
应用在多媒体中的图像压缩编码方法，从压缩编码算法原理上可以分类为：
(1)无损压缩编码种类 •哈夫曼编码 •算术编码 •行程编码 •Lempel zev编码
(2)有损压缩编码种类 •预测编码：DPCM，运动补偿 •频率域方法：正文变换编码(如DCT)，子带编码 •空间域方法：统计分块编码 •模型方法：分形编码，模型基编码 •基于重要性：滤波，子采样，比特分配，矢量量化
(3)混合编码 •JBIG，H261，JPEG，MPEG等技术标准
衡量一个压缩编码方法优劣的重要指标
(1)压缩比要高，有几倍、几十倍，也有几百乃至几千倍；
(2)压缩与解压缩要快，算法要简单，硬件实现容易；
(3)解压缩的图像质量要好。
四、JPEG图像压缩算法
1．.JPEG压缩过程
JPEG压缩分四个步骤实现：
1.颜色模式转换及采样；
2.DCT变换；
3.量化；
4.编码。
2．1．颜色模式转换及采样
RGB色彩系统是我们最常用的表示颜色的方式。JPEG采用的是YCbCr色彩系统。想要用JPEG基本压缩法处理全彩色图像，得先把RGB颜色模式图像数据，转换为YCbCr颜色模式的数据。Y代表亮度，Cb和Cr则代表色度、饱和度。通过下列计算公式可完成数据转换。
Y=0.2990R+0.5870G+0.1140B
Cb=-0.1687R-0.3313G+0.5000B+128
Cr=0.5000R-0.4187G-0.0813B＋128
人类的眼晴对低频的数据比对高频的数据具有更高的敏感度，事实上，人类
的眼睛对亮度的改变也比对色彩的改变要敏感得多，也就是说Y成份的数据是比较重要的。既然Cb成份和Cr成份的数据比较相对不重要，就可以只取部分数据来处理。以增加压缩的比例。JPEG通常有两种采样方式：YUV411和YUV422，它们所代表的意义是Y、Cb和Cr三个成份的资料取样比例。
2．2.DCT变换
DCT变换的全称是离散余弦变换(Discrete Cosine Transform)，是指将一组光强数据转换成频率数据，以便得知强度变化的情形。若对高频的数据做些修饰，再转回原来形式的数据时，显然与原始数据有些差异，但是人类的眼睛却是不容易辨认出来。
压缩时，将原始图像数据分成8*8数据单元矩阵，例如亮度值的第一个矩阵内容如下：
JPEG将整个亮度矩阵与色度Cb矩阵，饱和度Cr矩阵，视为一个基本单元称作MCU。每个MCU所包含的矩阵数量不得超过10个。例如，行和列采样的比例皆为4:2:2，则每个MCU将包含四个亮度矩阵，一个色度矩阵及一个饱和度矩阵。
当图像数据分成一个8*8矩阵后，还必须将每个数值减去128，然后一一代入DCT变换公式中，即可达到DCT变换的目的。图像数据值必须减去128，是因为DCT转换公式所接受的数字范围是在-128到+127之间。
DCT变换公式：
x,y代表图像数据矩阵内某个数值的坐标位置
f(x,y)代表图像数据矩阵内的数个数值
u,v代表DCT变换后矩阵内某个数值的坐标位置
F(u,v)代表DCT变换后矩阵内的某个数值
u=0 且 v=0 c(u)c(v)=1/1.414
u>0 或 v>0 c(u)c(v)=1
经过DCT变换后的矩阵数据自然数为频率系数，这些系数以F（0，0）的值最大，称为DC，其余的63个频率系数则多半是一些接近于0的正负浮点数，一概称之为AC。
3．3、量化
图像数据转换为频率系数后，还得接受一项量化程序，才能进入编码阶段。
量化阶段需要两个8*8矩阵数据，一个是专门处理亮度的频率系数，另一个则是
针对色度的频率系数，将频率系数除以量化矩阵的值，取得与商数最近的整数，
即完成量化。
当频率系数经过量化后，将频率系数由浮点数转变为整数，这才便于执行最
后的编码。不过，经过量化阶段后，所有数据只保留整数近似值，也就再度损失
了一些数据内容，JPEG提供的量化表如下：
2．4、编码
Huffman编码无专利权问题，成为JPEG最常用的编码方式，Huffman编码通常是以完整的MCU来进行的。
编码时，每个矩阵数据的DC值与63个AC值，将分别使用不同的Huffman编码表，而亮度与色度也需要不同的Huffman编码表，所以一共需要四个编码表，才能顺利地完成JPEG编码工作。
DC编码
DC是彩采用差值脉冲编码调制的差值编码法，也就是在同一个图像分量中取得每个DC值与前一个DC值的差值来编码。DC采用差值脉冲编码的主要原因是由于在连续色调的图像中，其差值多半比原值小，对差值进行编码所需的位数，会比对原值进行编码所需的位数少许多。例如差值为5，它的二进制表示值为101，如果差值为-5，则先改为正整数5，再将其二进制转换成1的补码即可。所谓1的补码，就是将每个Bit若值为0，便改成1；Bit为1，则变成0。差值5应保留的位数为3，下表即列出差值所应保留的Bit数与差值内容的对照。
在差值前端另外加入一些差值的霍夫曼码值，例如亮度差值为5（101）的位数为3，则霍夫曼码值应该是100，两者连接在一起即为100101。下列两份表格分别是亮度和色度DC差值的编码表。根据这两份表格内容，即可为DC差值加上霍夫曼码值，完成DC的编码工作。
AC编码
AC编码方式与DC略有不同，在AC编码之前，首先得将63个AC值按Zig-zag排序，即按照下图箭头所指示的顺序串联起来。
63个AC值排列好的，将AC系数转换成中间符号，中间符号表示为RRRR/SSSS，RRRR是指第非零的AC之前，其值为0的AC个数，SSSS是指AC值所需的位数，AC系数的范围与SSSS的对应关系与DC差值Bits数与差值内容对照表相似。
如果连续为0的AC个数大于15，则用15/0来表示连续的16个0，15/0称为ZRL（Zero Rum Length），而（0/0）称为EOB（Enel of Block）用来表示其后所
剩余的AC系数皆等于0，以中间符号值作为索引值，从相应的AC编码表中找出适当的霍夫曼码值，再与AC值相连即可。
例如某一组亮度的中间符为5/3，AC值为4，首先以5/3为索引值，从亮度AC的Huffman编码表中找到1111111110011110霍夫曼码值，于是加上原来100（4）即是用来取[5，4]的Huffman编码1111111110011110100，[5，4]表示AC值为4的前面有5个零。
由于亮度AC，色度AC霍夫曼编码表比较长，在此省略去，有兴趣者可参阅相关书籍。
实现上述四个步骤，即完成一幅图像的JPEG压缩。
C. 序列比对BWA(Burrows-Wheeler Aligner)
BWA主要是将reads比对到大型基因组上，主要功能是：序列比对。首先通过 BWT (Burrows-Wheeler Transformation， BWT压缩算法 )为大型参考基因组建立索引，然后将reads比对到基因组。特点是快速、准确、省内存。由三种类似算法组成：BWA-backtrack，BWA-SW和BWA-MEM。首推BWA-MEM。
0.6版本以来，BWA可以处理长度在4G以上的基因组。这样有可能将正负链互补的基因组序列整合到一个索引(FM-index)中去，可以使BWA-short和BWA-SW更快。
最新版本BWA-SW同样可以处理长度大于100bp的pair-end reads。与BWA-short相比，BWA-SW对高度唯一的reads准确性更高和相对更长的插入与结构突变时更稳健。尽管如此，从许多次优比对中选取最优比对时，BWA-short更好。
本文主要参考 BWA官方说明文档 及 BWA手册
D. 模型压缩：剪枝算法
过参数化主要是指在训练阶段，在数学上需要进行大量的微分求解，去捕抓数据中的微小变化信息，一旦完成迭代式的训练之后，网络模型推理的时候就不需要这么多参数。而剪枝算法正是基于过参数化的理论基础而提出的。
剪枝算法核心思想就是减少网络模型中参数量和计算量，同时尽量保证模型的性能不受影响。
那在AI框架中，实际上剪枝主要作用在右下角的端侧模型推理应用场景中，为的就是让端侧模型更小，无论是平板、手机、手表、耳机等小型IOT设备都可以轻松使用AI模型。而实际在训练过程更多体现在剪枝算法和框架提供的剪枝API上面。
实际上大部分刚接触剪枝算法的时候，都会从从宏观层面去划分剪枝技术，主要是分为Drop Out和Drop Connect两种经典的剪枝算法，如下图所示。
1）Drop Out：随机的将一些神经元的输出置零，称之为神经元剪枝。
2）Drop Connect：随机将部分神经元间的连接Connect置零，使得权重连接矩阵变得稀疏。
下面会把剪枝的更多种方式呈现出来，可能会稍微复杂哈。从剪枝的粒度来划分，可以分为结构化剪枝和非结构化剪枝，2个剪枝结构方法。下面来看看具体的剪枝方法有4种：
细粒度剪枝、向量剪枝、核剪枝在参数量与模型性能之间取得了一定的平衡，但是网络模型单层的神经元之间的组合结构发生了变化，需要专门的算法或者硬件结构来支持稀疏的运算，这种叫做 结构化剪枝（Unstructured Pruning） 。
其中，非结构化剪枝能够实现更高的压缩率，同时保持较高的模型性能，然而会带来网络模型稀疏化，其稀疏结构对于硬件加速计算并不友好，除非底层硬件和计算加速库对稀疏计算有比较好的支持，否则剪枝后很难获得实质的性能提升。
滤波器剪枝（Filter-level）主要改变网络中的滤波器组和特征通道数目，所获得的模型不需要专门的算法和硬件就能够运行，被称为 结构化剪枝（Structured Pruning） 。结构化剪枝又可进一步细分：可以是channel-wise，也可以是filter-wise，还可以是在shape-wise。
结构化剪枝与非结构化剪枝恰恰相反，可以方便改变网络模型的结构特征，从而达到压缩模型的效果，例如知识蒸馏中的student网络模型、NAS搜索或者如VGG19和VGG16这种裁剪模型，也可以看做变相的结构化剪枝行为。
虽然剪枝算法的分类看上去很多，但是核心思想还是对神经网络模型进行剪枝，目前剪枝算法的总体流程大同小异，可以归结为三种：标准剪枝、基于子模型采样的剪枝、以及基于搜索的剪枝，如下图所示。
标准剪枝是目前最流行的剪枝流程，在Tensorflow、Pytroch都有标准的接口。主要包含三个部分：训练、剪枝、以及微调。
1） 训练 ：首先是对网络模型进行训练。在剪枝流程中，训练部分主要指预训练，训练的目的是为剪枝算法获得在特定基础SOTA任务上训练好的原始模型。
3） 微调 ：微调是恢复被剪枝操作影响的模型表达能力的必要步骤。结构化模型剪枝会对原始模型结构进行调整，因此剪枝后的模型参数虽然保留了原始的模型参数，但是由于模型结构的改变，剪枝后模型的表达能力会受到一定程度的影响。实现上，微调网络模型，参数在计算的时候先乘以该Mask，Mask为1的参数值将继续训练通过BP调整梯度，而Mask为0的部分因为输出始终为0则不对后续部分产生影响。
4） 再剪枝 ：再剪枝过程将微调之后的网络模型再送到剪枝模块中，再次进行模型结构评估和执行剪枝算法。目的是使得每次剪枝都在性能更优的模型上面进行，不断迭代式地进行优化剪枝模型，直到模型能够满足剪枝目标需求。
最后输出模型参数储存的时候，因为有大量的稀疏，所以可以重新定义储存的数据结构， 仅储存非零值以及其矩阵位置。重新读取模型参数的时候，就可以还原矩阵。
除标准剪枝之外，基于子模型采样的剪枝《EagleEye: Fast sub-net evaluation for efficient neural network pruning》最近也表现出比较好的剪枝效果。得到训练好的模型之后，进行子模型采样过程。一次子模型采样过程为：
1）对训练好的原模型中可修剪的网络结构，按照剪枝目标进行采样，采样过程可以是随机的，也可以按照网络结构的重要性或者通过KL散度计算进行概率采样。
2）对采样后的网络结构进行剪枝，得到采样子模型。子模型采样过程通常进行 次，得到 个子模型（ ≥1）, 之后对每一个子模型进行性能评估。子模型评估结束之后，选取最优的子模型进行微调以得倒最后的剪枝模型。
基于搜索的剪枝主要依靠强化学习等一系列无监督学习或者半监督学习算法，也可以是神经网络结构搜索相关理论。
给定剪枝目标之后，基于搜索的剪枝在网络结构中搜索较优的子结构，这个搜索过程往往伴随着网络参数的学习过程，因此一些基于搜索的剪枝算法在剪枝结束后不需要再进行微调。
这几年神经网络剪枝pruning作为模型压缩技术的四小龙之一，正在受到越来越多的关注。当然，各种更好的pruning参数选取方法一定还会层出不穷。另外，从趋势来看，以下几个方向值得关注：
打破固定假设 ：挑战已有的固有的假设，例如ICLR2019会议的best paper彩票假说《The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks 》的出现。还有一开始提到的对于over-parameterization，与重用已有参数是否有有益的反思非常有意思。这样的工作会给剪枝算法非常大的启发，从而根本改变解决问题的思路。
自动化剪枝 ：随着AutoML的大潮，越来越多的算法开始走向自动化。模型压缩能拉下吗？当然不能。经过前面的介绍我们知道，像ADC，RNP，N2N Learning这些工作都是试图将剪枝中部分工作自动化。如量化中的《HAQ: Hardware-Aware Automated Quantization》考虑网络中不同层信息的冗余程度不一样，所以自动化使用混合量化比特进行压缩。
与NAS融合 ：如前面模型剪枝流程中提到，剪枝算法与神经网络搜索NAS的界限已经模糊了。NAS有针对结构化剪枝进行搜索方法，如One-Shot Architecture Search是先有一个大网络，然后做减法。NAS与模型压缩两个一开始看似关系不是那么大的分支，在近几年的发展过程中因为下游任务和部署场景的需求，最后似乎会走到一块去。这两个分支今天有了更多的交集，也必将擦出更多的火花。
与GAN融合 ：这几年机器学习最火热的分支之一GAN，正在不断渗透到已有领域，在pruning中也开始有它的身影。如2019年《Towards Optimal Structured CNN Pruning via Generative Adversarial Learning》让generator生成裁剪后网络，discrimintor来判别是否属于原网络还是裁剪后网络，从而进行更有效的网络结构化裁剪。
硬件稀疏性支持 ：剪枝会给神经网络模型带来稀疏性特征，参数稀疏性在计算中会有大量的索引，所以并不能加速。现在虽然有像cuSPARSE这样的计算库，但底层硬件AI芯片本身设计并不是专门为稀疏数据处理打造的。如果能将稀疏计算和处理能力做进芯片那必将极大提高计算效率。仅2021年中国就推出了10+款基于ASIC的AI加速芯片，相信针对稀疏性场景的支持在未来会有所突破。
模型压缩算法中针对已有的模型，有：张量分解，模型剪枝，模型量化。针对新构建的网络，有：知识蒸馏，紧凑网络设计等方法。
剪枝只是模型压缩方法中的一种，它与其它模型压缩方法并不冲突，因此会与量化、蒸馏、NAS、强化学习等方法慢慢融合，这些都是很值得研究的方向。另外在上面的发展来看，打破固有的假设定义，与NAS、GAN、AutoML、RL等技术进行相互的融合，可能到最后会模糊purning方式，出现新的范式或者压缩模式也是很吸引的。
E. Elasticsearch之数据压缩算法
Lucene使用FST算法以字节的方式来存储所有的Term，重复利用Term Index的前缀和后缀，使Term Index小到可以放进内存，减少存储空间，不过相对的也会占用更多的cpu资源。FST在Lucene4.0以后的版本中用于快速定位所查单词在字典中的位置。
Finite StateTranscers，简称 FST，通常中文译作 有穷状态转换器 ，在语音识别和自然语言搜索、处理等方向被广泛应用。
FST的功能类似于字典，可以表示成FST<Key, Value>的形式。其最大的特点是，可以用 O(length(key)) 的复杂度来找到key对应的value，也就是说查找复杂度仅取决于所查找的key长度。
假设我们现在要将以下term index映射到term dictionary的block序号：
最简单的做法就是定义个Map<string, integer="">，大家找到自己的位置对应入座就好了，但从内存占用少的角度想想，有没有更优的办法呢？答案就是FST。
对于经典FST算法来说，要求 Key必须按字典序从小到大加入到FST 中。上面的例子中key已经排好序了。
按照以下步骤建立FST：
最后加入 dogs ，得到最后的结果：
从上图可以看出，每条边有两条属性，一个表示label（key的元素），另一个表示Value(out)。注意Value不一定是数字，还可一是另一个字符串，但要求Value必须满足叠加性，如这里的正整数2 + 8 = 10。字符串的叠加行为： aa + b = aab。
建完这个图之后，我们就可以很容易的查找出任意一个key的Value了。例如：查找dog，我们查找的路径为：0 → 4 → 8 → 9。 其权值和为： 2 + 0 + 0 + 0 = 2。其中最后一个零表示 node[9].finalOut = 0。所以“dog”的Value为2。
Lucene除了上面说到用FST压缩term index外，对posting list也会进行压缩。
有人可能会有疑问：“posting list不是已经只存储文档id了吗？还需要压缩吗？”。设想这样一种情况，Lucene需要对一千万个同学的性别进行索引，而世界上只有男/女这样两个性别，每个posting list都会有数百万个文档id，这里显然有很大的压缩空间与价值，对于减少索引尺寸有非常重要的意义。
Lucene使用 Frame Of Reference 编码来实现对posting list压缩，其思路简单来说就是： 增量编码压缩，将大数变小数，按字节存储 。
示意图如下：
除此之外，Lucene在执行filter操作还会使用一种叫做 Roaring bitmaps 的数据结构来存储文档ID，同样可以达到压缩存储空间的目的。
说到Roaring bitmaps，就必须先从bitmap说起。bitmap是一种很直观的数据结构，假设有某个posting list：
对应的bitmap就是：
非常直观，用0/1表示某个值是否存在，比如10这个值就对应第10位，对应的bit值是1，这样用一个字节就可以代表8个文档id，旧版本(5.0之前)的Lucene就是用这样的方式来压缩的，但这样的压缩方式仍然不够高效，如果有1亿个文档，那么需要12.5MB的存储空间，这仅仅是对应一个索引字段(我们往往会有很多个索引字段)。于是有人想出了Roaring bitmaps这样更高效的数据结构。Roaring bitmaps压缩的原理可以理解为，与其保存100个0，占用100个bit，还不如保存0一次，然后声明这个0有100个。
Bitmap的缺点是存储空间随着文档个数线性增长，Roaring bitmaps需要打破这个魔咒就一定要用到某些指数特性：
将posting list按照65535为界限分块，比如第一块所包含的文档id范围在0 65535之间，第二块的id范围65536 131071，以此类推。再用<商，余数>的组合表示每一组id，这样每组里的id范围都在0~65535内了，剩下的就好办了，既然每组id不会变得无限大，那么我们就可以通过最有效的方式对这里的id存储。
为什么是以65535为界限呢？
程序员的世界里除了1024外，65535也是一个经典值，因为它=2^16-1，正好是用2个字节能表示的最大数，一个short的存储单位，注意到上图里的最后一行“If a block has more than 4096 values, encode as a bit set, and otherwise as a simple array using 2 bytes per value”，如果是大块，用节省点用bitset存，小块就豪爽点，2个字节我也不计较了，用一个short[]存着方便。
那为什么用4096来区分大块还是小块呢？
都说程序员的世界是二进制的，4096*2bytes ＝ 8192bytes < 1KB, 磁盘一次寻道可以顺序把一个小块的内容都读出来，再大一位就超过1KB了，需要两次读。
一种常见的压缩存储时间序列的方式是把多个数据点合并成一行。Opentsdb支持海量数据的一个绝招就是定期把很多行数据合并成一行，这个过程叫compaction。类似的vivdcortext使用mysql存储的时候，也把一分钟的很多数据点合并存储到mysql的一行里以减少行数。
这个过程可以示例如下：
合并之后就变成了：
可以看到，行变成了列了。每一列可以代表这一分钟内一秒的数据。
Elasticsearch有一个功能可以实现类似的优化效果，那就是Nested Document。我们可以把一段时间的很多个数据点打包存储到一个父文档里，变成其嵌套的子文档。示例如下：
可以打包成：
这样可以把数据点公共的维度字段上移到父文档里，而不用在每个子文档里重复存储，从而减少索引的尺寸。
在存储的时候，无论父文档还是子文档，对于 Lucene 来说都是文档，都会有文档 Id。但是对于嵌套文档来说，可以保存起子文档和父文档的文档 id 是连续的，而且父文档总是最后一个。有这样一个排序性作为保障，那么有一个所有父文档的 posting list 就可以跟踪所有的父子关系。也可以很容易地在父子文档 id 之间做转换。把父子关系也理解为一个 filter，那么查询时检索的时候不过是又 AND 了另外一个 filter 而已。前面我们已经看到了 Elasticsearch 可以非常高效地处理多 filter 的情况，充分利用底层的索引。
使用了嵌套文档之后，对于 term 的 posting list 只需要保存父文档的 doc id 就可以了，可以比保存所有的数据点的 doc id 要少很多。如果我们可以在一个父文档里塞入 50 个嵌套文档，那么 posting list 可以变成之前的 1/50。
F. linux zip和gzip的区别
zip是将文件打包为zip格式的压缩文件
gzip是将文件打包为tar.gz格式的压缩文件
unzip是从zip包中解压出某个文件
gunzip从tar.gz包中解压出某个文件
locate命令和find命令都用于查找文件，locate比find命令的搜索速度快，它需要一个数据库，称为“索引”，这个数据库由每天的例行工作（crontab）程序来建立。当我们建立好这个数据库后，就可以方便地来搜寻所需文件了。
find命令在目录结构中搜索文件，并执行指定的操作。此命令提供了相当多的查找条件，功能很强大。 但搜索速度可能不如locate命令快
grep命令是用来列出符合指定样式的那一行或者若干行内容
如ls |grep c 是列出当前目录下中含有字母c的所有项
全部手敲出来的~望采纳
G. 什么是压缩算法
LZW压缩算法的基本概念：LZW压缩有三个重要的对象：数据流(CharStream)、编码流(CodeStream)和编译表(String Table)。在编码时，数据流是输入对象（文本文件的据序列），编码流就是输出对象（经过压缩运算的编码数据）；在解码时，编码流则是输入对象，数据流是输出对象；而编译表是在编码和解码时都须要用借助的对象。字符(Character)：最基础的数据元素，在文本文件中就是一个字节，在光栅数据中就是一个像素的颜色在指定的颜色列表中的索引值；字符串(String)：由几个连续的字符组成； 前缀(Prefix)：也是一个字符串，不过通常用在另一个字符的前面，而且它的长度可以为0；根(Root)：一个长度的字符串；编码(Code)：一个数字，按照固定长度（编码长度）从编码流中取出，编译表的映射值；图案：一个字符串，按不定长度从数据流中读出,映射到编译表条目. LZW压缩算法的基本原理：提取原始文本文件数据中的不同字符，基于这些字符创建一个编译表，然后用编译表中的字符的索引来替代原始文本文件数据中的相应字符，减少原始数据大小。看起来和调色板图象的实现原理差不多，但是应该注意到的是，我们这里的编译表不是事先创建好的，而是根据原始文件数据动态创建的，解码时还要从已编码的数据中还原出原来的编译表.
H. ETC1压缩算法详解
ETCPACK
如何将一个 4x4 的像素块编码为 64 位数据呢?
以上就是编码后的 64 位数据块表示的意义
以RGB555基本色和RGB3333颜色差表示的编码为例，每个4x4 像素块经过ETC1 编码后的 64 位数据的内存布局大概是这样
假如编码前像素块表示为下图
我们需要得到图中编号2对应像素的颜色，需要进行如下的解码步骤：
indivial 模式，直接将4位数复制到尾部，得到8位
differential 模式，将5位中的高3位复制到尾部，得到8位
differential 模式，一定是将子块1基本色和子块2偏移值相加后再进行补位
上面知道目标像素位于子块2，这里还需要从编码数据的34-36获得子块2的修正表索引，得到索引为(1,1,0)=6，根据上面的映射表，根据下标(6, -b) 可以索引到像素的颜色差值为-106
其实从上面的解压过程可以推测出编码的过程
参考：
UI图集压缩优化，以及对Dither和ETC1算法的深入了解
几种主流贴图压缩算法的实现原理详解
OES_compressed_ETC1_RGB8_texture