压缩感知——简介
 
压缩感知，compressed sensing又称compressed sampling，是在采样过程中完成了数据压缩的过程。
 压缩感知在信号采样的过程中，用很少的采样点，实现了和全采样一样的效果。
 
压缩感知——信号采样
 
学过通信原理或信号与系统的都知道奈奎斯特采样定理，即想让采样之后的数字信号完整保留原始信号中的信息，采样频率必须大于信号中最高频率的2倍。原因是时域以τ为间隔进行采样，频域会以1/τ为周期发生周期延拓。那么如果采样频率低于两倍的信号最高频率，信号在频域频谱搬移后就会发生混叠。
 2004年，Candes，陶哲轩和Donoho提出了压缩感知理论，该理论认为：如果信号是稀疏的，那么它可以由远低于采样定理要求的采样点重建恢复。
 突破的关键就在于采样的方式。当我们说“采样频率”的时候，意味着做的是等间距采样，数字信号领域通常都是做等间距采样，也服从奈奎斯特采样定律。
 
 但是压缩感知采用不等间距采样，比如采用随机亚采样（图b上方的红点），那么这时候频域就不再是以固定周期进行延拓了，而是会产生大量不相关（incoherent）的干扰值。如图c，最大的几个峰值还依稀可见，只是一定程度上被干扰值覆盖。这些干扰值看上去非常像随机噪声，但实际上是由于三个原始信号的非零值发生能量泄露导致的（不同颜色的干扰值表示它们分别是由于对应颜色的原始信号的非零值泄露导致的）
 之所以随机亚采样会有这样的效果，可以理解成随机采样使得频谱不再是整齐地搬移，而是一小部分一小部分胡乱地搬移，频率泄露均匀地分布在整个频域，因而泄漏值都比较小，从而有了恢复的可能。
 
压缩感知——信号恢复
 
压缩感知——两个前提条件
 
刚刚的例子之所以能够实现最终信号的恢复，是因为它满足了两个前提条件：
 
这个信号在频域只有3个非零值，所以可以较轻松地恢复出它们。
采用了随机亚采样机制，因而使频率泄露均匀地分布在整个频域。
 这两点对应了CS的两个前提条件——稀疏性（sparsity）、不相关性（incoherence）。
 稀疏性可以简单直观地理解为：若信号在某个域中只有少量非零值，即信号在某个域中非零点远远小于信号总点数，那么它在该域稀疏，该域也被称为信号的稀疏域。
 因此，第一个前提条件要求信号必须在某一个变换域具有稀疏性。比如例子中，信号在频域是稀疏的，因而可以通过所述的重建方法轻松地在稀疏域（频域）复原出原信号。
 然而通常信号在变换域中不会呈现完全的稀疏性。其实只要它近似满足稀疏性，即大部分值趋于零，只有少量大的非零值，就可以认为它是可压缩信号，可以对它进行CS亚采样。
 对于之前讲的例子，如果它在频域中不稀疏，我们可以做DWT、DCT等，找到它的稀疏变换。
 
前提条件1——稀疏性
 
前提条件2——非相关性/等距约束性
 
在讲第二个前提条件之前，需要引入必要的数学表达。
 
 上面这张图把亚采样的过程用矩阵的方式表达出来：
 如图，x是为长度N的一维信号，也就是原信号，稀疏度为k。此刻它是未知的。
 Φ为观测矩阵，对应着亚采样这一过程。它将高维信号x投影到低维空间，是已知的。
 y=Φx为长度M的一维测量值，也就是亚采样后的结果。显然它也是已知的。
 因此，压缩感知问题就是在已知测量值y和测量矩阵Φ的基础上，求解欠定方程组y=Φx得到原信号x。
 然而，一般的自然信号x本身并不是稀疏的，需要在某种稀疏基上进行稀疏表示。令x=Ψs，Ψ为稀疏基矩阵，s为稀疏系数。
 于是最终方程就变成了：y=ΦΨs。已知y、Φ、Ψ，求解s。
 y=ΦΨs有点长，我们把ΦΨ合并成一个矩阵，称之为传感矩阵。即令Θ=ΦΨ ，则y=ΘS。问题即为，已知y和Θ，求解S。
 对应到一开始的例子中：
 x就是三个正弦信号叠加在一起的原信号a；
 稀疏矩阵Ψ就是傅里叶变换，将信号变换到频域S；
 观测矩阵Φ就是我们采用的随机亚采样方式；
 y就是最终的随机亚采样的结果c。
 
 求解出S后，由x=Ψs即可得到恢复出的原信号x。
 然而在正常情况下，方程的个数远小于未知数的个数，方程是没有确定解的，无法重构信号。但是，由于信号是K稀疏，如果上式中的Φ满足有限等距性质(RIP)，则K个系数就能够从M个测量值准确重构（得到一个最优解）。
 陶哲轩和Candès证明了RIP是观测矩阵要满足的准确要求。但是，要确认一个矩阵是否满足RIP非常复杂。于是Baraniuk证明：RIP的等价条件是观测矩阵和稀疏表示基不相关（incoherent）。即压缩感知的第二个前提条件。
 
 
 那怎样找到不相关的观测矩阵呢？陶哲轩和Candès又证明： 独立同分布的高斯随机测量矩阵可以成为普适的压缩感知测量矩阵。
 于是满足高斯分布的随机测量矩阵就成了CS最常用的观测矩阵。
 对于二维信号，往往就采用二维高斯随机测量采样矩阵对图像进行亚采样。
 对于一维信号，采用前文提到的随机不等间距的亚采样即可。
 
压缩感知——重建方法
 
信号采样后需要将其恢复。CS的重建也就是求解欠定方程组y=ΘS的方法。这是一个零范数（l0）最小化问题，是一个NP完全问题（没有快速解法的问题），因此往往转换成一范数（l1）最小化的求解，或者用一些近似估计的算法。
 匹配追踪是一种典型的算法。以上文中的例子为例：
 (1) 由于原信号的频率非零值在亚采样后的频域中依然保留较大的值，其中较大的两个可以通过设置阈值，检测出来（图a）。
 (2) 然后，假设信号只存在这两个非零值（图b），则可以计算出由这两个非零值引起的干扰（图c）。
 (3) 用a减去c，即可得到仅由蓝色非零值和由它导致的干扰值(图d），再设置阈值即可检测出它，得到最终复原频域（图e）
 (4) 如果原信号频域中有更多的非零值，则可通过迭代将其一一解出。
 
 
扩展：图像压缩与压缩感知
 
信号的稀疏性已经在图像压缩领域有了很广泛的应用。利用信号的稀疏性，可以对信号进行压缩。如图像压缩领域的JPEG格式，就是将图像变换到离散余弦域，得到近似稀疏矩阵，只保留较大的值，从而实现压缩。
 图像压缩和压缩感知这两个概念有着本质上的区别。
 图像压缩是先进行了全采样，然后再变换域丢弃小系数，完成压缩；
 而压缩感知不同，它的思想其实从图像压缩中借鉴了很多：既然全采样了还要再丢弃，我们为什么不能直接少采样一些点？因此，压缩感知直接进行了亚采样，然后再用算法消除亚采样导致的伪影。可以说，压缩感知直接在采样时就完成了压缩。
 
 这种直接减少采样点，采集完后重建的方式，相比于图像压缩的全采用之后再压缩的方式，对于很多情形，比如照相机拍摄照片，并没有优势。因为所有像素的采集在一瞬间就都完成了。但是对于一些采集比较慢的情形，比如核磁共振成像，CS就可以发挥巨大优势。原本一副MRI图像常常需要几十秒，速度慢也是MRI的一大缺陷。而应用CS技术后，只需要采集全采样几分之一的数据，就可以重建出原图。这样就可以把成像速度提高好几倍，同时对图像质量影响不大。
 
总结
 
什么是压缩感知：
 如果一个信号在某个变换域是稀疏的，那么就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上，然后通过求解一个优化问题就可以从这些少量的投影中以高概率重构出原信号。
 压缩感知理论主要包括三部分：
 （1）信号的稀疏表示；
 （2）设计测量矩阵，要在降低维数的同时保证原始信号x的信息损失最小；
 （3）设计信号恢复算法，利用M个观测值无失真地恢复出长度为N的原始信号。
 
从06年提出至今，已经发展出了很多算法，原来的基于l1 minimization的BP算法很慢，现在都是快速算法，而且求解算法也从纯优化方面扩展到了estimation方面，有很多基于贝叶斯估计的方法了，目前最火的也是Donoho他们组搞得AMP算法，是用Graph model里面的message passing算法通过近似求解MMSE（MAP）解。在测量矩阵方面，也已经设计出了各种矩阵，除了i.i.d. Gaussian的矩阵还有很多正交的矩阵，比如partial random DFT/DCT 矩阵。对信号的要求也从稀疏变成了存在某种结构，比如low rank，group sparse等等。（2017年进展）
 
压缩感知和矩阵填充
 
矩阵填充的要领是通过低秩矩阵中的已知要素还原出该矩阵的其他未知要素的进程。这几年，关于矩阵填充方法的理论研究成为压缩感知技术的一个研究热点。在实际的应用领域中涉及对高维数据的分析与处理，可以运用矩阵填充的方法来解决。其过程主要是：通过观测到的局部数据来准确填充缺失数据,从而获得完整数据矩阵的过程。
 压缩感知和矩阵填充都是稀疏约束下的反问题，压缩感知利用信号本身或在变换域中的稀疏约束性求解欠定方程，矩阵填充利用矩阵的低秩约束性求解欠定方程。
 压缩感知理论的核心问题是信号的稀疏表示、观测矩阵的设计和重构算法，信号本身或在变换域中的系数越稀疏，观测矩阵和稀疏基构成的压缩感知矩阵的受限等距常数越小，则压缩感知的性能越好。
 矩阵填充理论的核心问题是矩阵的低秩特性、非相干特性和重构算法，寻找性能良好的重构算法一直是矩阵填充理论中的一个研究重点。此外，压缩感知的应用领域已经拓展得较为广泛，但矩阵填充的应用尚处于起步阶段，挖掘矩阵填充的应用，进而将矩阵填充和压缩感知结合起来进行应用方面的探索，是非常重要和有意义的课题。
 压缩感知的性能取决于3个要素：信号的稀疏性、压缩感知矩阵的非相干性和重构算法的快速有效性。
 矩阵填充性能也取决于3个要素：矩阵的低秩性、矩阵的不相关性和重构算法的快速有效性。
 
低秩矩阵
 
还记得我们怎么手工求矩阵的秩吗？为了求矩阵A的秩，我们是通过矩阵初等变换把A化为阶梯型矩阵，若该阶梯型矩阵有r个非零行，那A的秩rank(A)就等于r。从物理意义上讲，矩阵的秩度量的就是矩阵的行列之间的相关性。如果矩阵的各行或列是线性无关的，矩阵就是满秩的，也就是秩等于行数。回到上面线性方程组来说吧，因为线性方程组可以用矩阵描述嘛。秩就表示了有多少个有用的方程了。上面的方程组有3个方程，实际上只有2个是有用的，一个是多余的，所以对应的矩阵的秩就是2了。
 OK。既然秩可以度量相关性，而矩阵的相关性实际上就表示了矩阵的结构信息。如果矩阵之间各行的相关性很强，那么就表示这个矩阵实际可以投影到更低维的线性子空间，也就是用几个向量就可以完全表达了，它就是低秩的。所以我们总结的一点就是：如果矩阵表达的是结构性信息，例如图像、用户-商品推荐表等等，那么这个矩阵各行之间存在这一定的相关性，那这个矩阵一般就是低秩的。
 如果X是一个m行n列的数值矩阵，rank(X)是X的秩，假如rank (X)远小于m和n，则我们称X是低秩矩阵。低秩矩阵每行或每列都可以用其他的行或列线性表出，可见它包含大量的冗余信息。利用这种冗余信息，可以对缺失数据进行恢复，也可以对数据进行特征提取。
 
应用
 
矩阵填充越来越多的应用在协同滤波、系统识别、无线传感网络、视频去噪、人脸识别、医学成像等领域，正在发挥着巨大的作用。特别是在室内定位中的 应用越来越多，是当下的研究热点之一。
 
参考网址：
 形象易懂讲解算法II——压缩感知（非常好）
 AndyJee：浅谈压缩感知系列——博客园（非常丰富）
 压缩感知理论
 机器学习——低秩矩阵分解中低秩的意义、矩阵填补、交叉验证

 
雷达线性调频信号的脉冲压缩处理
 
一、设计目的和意义
二、设计原理
1、 匹配滤波器
2、线性调频信号
3、LFM 信号的脉冲压缩
  
三、MATLAB具体仿真
四、小结
参考文献

 
一、设计目的和意义
 
掌握雷达测距的工作原理，掌握匹配滤波器的工作原理及其白噪声背景下的匹配滤波的设计，线性调频信号是大时宽频宽积信号； 其突出特点是匹配滤波器对回波的多普勒频移不敏感以及更好的低截获概率特性。LFM 信号在脉冲压缩体制雷达中广泛应用；利用线性调频信号具有大带宽、长脉冲的特点，宽脉冲发射已提高发射的平均功率保证足够的作用距离；而接受时采用相应的脉冲压缩算法获得窄脉冲已提高距离分辨率， 较好的解决了雷达作用距离和距离分辨率之间的矛盾。而利用脉冲压缩技术除了可以改善雷达系统的分辨力和检测能力，还增强了抗干扰能力、灵活性，能满足雷达多功能、多模式的需要。
 
二、设计原理
 
1、 匹配滤波器
 
匹配滤波器（match filter）是最佳线性滤波器的一种，该滤波器的准则是输出信噪比最大，常用于通信、雷达等系统的接收机中，下面对其冲激响应/系统函数进行推导。
 设该滤波器传递函数为H(f)H(f)，冲激响应为h(t)h(t)，输入信号为
 r(t)=s(t)+n(t)
 
其中s(t)为输入信号，n(t)为高斯白噪声。设输入信号的频谱密度函数为S(f)，而高斯白噪声的单边功率谱为n0/2，其中n0为高斯白噪声单边功率谱密度。 该信号通过匹配滤波器输出如图1.1所示
 
 其中：
 S(t)=Acos(2πf_0 t+πμt^2) (0≤t≤τ)
 h(t)=ks_t^ (t_0-t)
 H(f)=kS_t^ (f)e^(-j2πft_0 )
 τ^’=1/B=1/μτ**
 
 
 
在通信系统中，滤波器是其中重要部件之一，滤波器特性的选择直接影响数字信号的恢复。在数字信号接收中，滤波器的作用有两个方面，使滤波器输出有用信号成分尽可能强；抑制信号外带噪声，使滤波器输出噪声成分尽可能小，减少噪声对信号判决的影响。对最佳线形滤波器的设计有两种准则其中一种是是滤波器输出信噪比在某一特定时刻达到最大，由此而导出的最佳线性滤波器成为匹配滤波器。在数字通信中，匹配滤波器具有广泛的应用。因此匹配滤波器是指滤波器的性能与信号的特性取得某种一致，使滤波器输出端的信号瞬时功率与噪声平均功率的比值最大。
 
 
在信号处理中，匹配滤波器可以用来解调基频带脉冲信号，基频带脉冲信号意指信号内容为同一波形信号乘上一个常数，在每个周期出现，每个周期中代表着或多或少的信息量。匹配滤波器解调出来的结果其SNR
 (Signal Noise Ratio)为最大的，匹配滤波器需要事先知道：1.传送的信号；2.信号的同步。这样才能解调出传送的信号。
 
 
此外，匹配滤波器也可用于模式识别、相似度测试（similarity measure）。
 
 
2、线性调频信号
 
线性调频信号指持续期间频率连续线性变化的信号，是一种常用的雷达信号。可以采用如下数学表达式表示：
 
S(t)=Acos(2πf_0 t+πμt^2) (0≤t≤τ)
 
其中：f0为中心频率；k=B/为调频频率；B为频率变化范围；tao为脉冲宽度；a(t)为线性调频脉冲的包络。
 
 
 
线性调频信号通过对载波频率进行调制以增加信号的发射带宽并在接收时实现脉冲压缩。由于线性调频信号具有较高的距离分辨力，当在速度上无法区分多目标时，可以通过增加目标距离测试解决多目标的分辨问题；同时在抗干扰方面，线性调频信号可以在距离上区分干扰和目标，因而可以有效地对抗拖曳式干扰，这使得线性调频信号在雷达波形设计中得到了广泛的应用。由于线性调频信号是通过一个发射脉冲实现距离高分辨的，因此该信号对目标多普勒频移不敏感，即使回波信号有较大的多普勒频移，脉冲压缩系统仍能起到压缩的作用。这将大大简化信号处理系统。
 
 
线性调频信号经过压缩处理接收后的信号幅度峰值是原来发射信号峰值的D的1/2次方（D为脉压比，等于脉冲宽度与B的乘积）倍，即输出脉冲峰值功率比输入脉冲峰值功率增大了D倍。在要求发射机输出功率一定的情况下，接收机输出的目标回波信号经过匹配滤波压缩处理，具有窄的脉冲宽度和更高的峰值功率，前者提高距离分辨率而后者符合探测距离远的要求，这便充分体现了脉压体制独特的优越性。从反侦察的角度来说，脉压雷达比普通雷达具有更强的生存能力。由于线性调频信号的幅度和信噪比更小，由侦察方程可知，同等灵敏度的侦察机其侦察距离为原来的D的负1/2次方，所以在雷达应用领域，脉压雷达具有功率优势，应用前景十分广阔。
 
 
3、LFM 信号的脉冲压缩
 
 
 
脉冲压缩技术是匹配滤波理论和相关接收理论的一个很好的实际应用。它的提出很好的解决了这样的一个问题：在发射端发射大时宽、带宽信号，以提高信号的速度测量精度和速度分辨力，而在接收端，将宽脉冲信号压缩为窄脉冲，以提高雷达对目标的距离分辨精度和距离分辨力。
 
 
三、MATLAB具体仿真
 
匹配滤波在通信和雷达等系统中有很多应用，其中以雷达系统中的脉冲压缩较为典型，本文以雷达系统中的脉冲压缩(pulse compress)为例，进行仿真。
 
在雷达目标检测中，希望距离分辨率和探测威力都足够大。而距离分辨率与发射波形的时宽成反比，探测威力（能量）与发射波形的时宽成正比。若发射波形为方波，其时宽τ与带宽B乘积约等于1，说明距离分辨率和探测威力是相互矛盾的。此时采用线性调频信号，可以很好的解决这个矛盾。
 对于一个理想的脉冲压缩系统， 要求发射信号具有非线性的相位谱， 并使其包络接近矩形；其中 S(t )就是信号 s(t)的复包络。由傅立叶变换性质， S(t)与 s(t)具有相同的幅频特性，只是中心频率不同而已。因此， Matlab 仿真时，只需考虑S(t)。
 
下面对脉冲压缩进行仿真，仿真参数设置如下
 
参数
取值
信号带宽
40MHz
信号时宽
20μs
脉冲周期
2ms
采样频率
20MHz
信噪比
20dB
目标距离
T∗fs/2
以下Matlab 程序产生的线性调频信号，并作出其时域波形和幅频特性，如图：
 
 对应代码：
 
%%demo of chirp signal
T=20e-6;
B=40e6;%chirp frequency modulation bandwidth 30MHz
K=B/T; %chirp slope
Fs=2*B;Ts=1/Fs; %sampling frequency and sample spacing
N=T/Ts;
t=linspace(-T/2,T/2,N);
St=exp(j*pi*K*t.^2); %generate chirp signal
subplot(211)
plot(t*1e6,St);
xlabel('Time in u sec');
title(' 线性调频信号');
grid on;axis tight;
subplot(212)
freq=linspace(-Fs/2,Fs/2,N);
plot(freq*1e-6,fftshift(abs(fft(St))));
xlabel('Frequency in MHz');
title(' 线性调频信号的幅频特性');
grid on;axis tight;

 
以下Matlab 程序段仿真了LFM信号的脉冲压缩，仿真结果如图:
 
 图中，时间轴进行了归一化，（t /(1/ B)= t *B）。图中反映出理论与仿真结果吻合良好。
 对应代码：
 
%%demo of chirp signal after matched filter
T=20e-6;
B=40e6; %chirp frequency modulation bandwidth 30MHz
K=B/T; %chirp slope
Fs=10*B;Ts=1/Fs; %sampling frequency and sample spacing
N=T/Ts;
t=linspace(-T/2,T/2,N);
St=exp(j*pi*K*t.^2); %chirp signal
Ht=exp(-j*pi*K*t.^2); %matched filter
Sot=conv(St,Ht); %chirp signal after matched filter
subplot(211)
L=2*N-1;
t1=linspace(-T,T,L);
Z=abs(Sot);Z=Z/max(Z); %normalize
Z=20*log10(Z+1e-6);
Z1=abs(sinc(B.*t1)); %sinc function
Z1=20*log10(Z1+1e-6);
t1=t1*B;
plot(t1,Z,t1,Z1,'r.');
axis([-15,15,-50,inf]);grid on;
legend('emulational','sinc');
xlabel('Time in sec \times\itB');
ylabel('幅度,dB');
title(' 傅里叶变换后的线性调频信号');
subplot(212) %zoom
N0=3*Fs/B;
t2=-N0*Ts:Ts:N0*Ts;
t2=B*t2;
plot(t2,Z(N-N0:N+N0),t2,Z1(N-N0:N+N0),'r.');
axis([-inf,inf,-50,inf]);grid on;
set(gca,'Ytick',[-13.4,-4,0],'Xtick',[-3,-2,-1,-0.5,0,0.5,1,2,3]);
xlabel('Time in sec \times\itB');
ylabel('幅度,dB');
title(' 傅里叶变换后的线性调频信号(Zoom)');

 
以下Matlab 程序段仿真了线性调制信号和噪声的生成，仿真结果如图:
 
 对应代码：
 
% 加白噪声后的线性调频信号
T=20e-6;
B=40e6; %chirp frequency modulation bandwidth 30MHz
K=B/T; %chirp slope
Fs=2*B;Ts=1/Fs; %sampling frequency and sample spacing
N=T/Ts;
t=linspace(0,T,N);
St=exp(j*pi*K*t.^2);
subplot(211)
plot(t*1e6,St);
xlabel('Time in u sec');
title(' 线性调频信号');
grid on;axis tight;
SNR=20；
x=awgn(St, 5); %generate chirp signal
subplot(212)
plot(t*1e6,x);
xlabel('Time ');
title(' 加噪后的线性调频信号');
grid on;axis tight;

 
实际实际雷达系统中， LFM 脉冲的处理过程如图：
 
 雷达回波信号 sr (t )经过正交解调后， 得到基带信号，再经过匹配滤波脉冲压缩后就可以作出判决。正交解调原理如图：
 
 雷达回波信号经正交解调后得两路相互正交的信号I(t) 和Q(t)。一种数字方法处理的的匹配滤波原理如图：
 
 以下为经过脉冲压缩输出的已加噪声的线性调频信号（模拟雷达回波信号）的matlab仿真结果，仿真结果如图:
 
 
四、小结
 
本文首先介绍了匹配滤波器的工作原理，特性特点；其次介绍了LFM 信号的形式以及matlab 的仿真情况，然后从雷达信号处理上进行改进，最后在对LFM 信号进行matlab 仿真，对LFM 在加噪前后脉冲压缩匹配滤波的仿真情况进行详细的分析，明确了脉冲压缩技术不但降低了对雷达发射机峰值功率的要求， 也解决雷达作用距离和距离分辨力之间的矛盾； 在对低截获概率雷达信号处理中将有广阔的应用前景。
 
参考文献
 
【1】信号与系统（第二版） 西安交通大学出版社
 【2】matlab 基础与编程入门（第二版）西安电子科技大学出版社
 【3】随机信号分析（第一版） 科学出版社
 【4】雷达原理（第三版）西安电子科技大学出版社

写一个对文件进行压缩和解压缩的程序，功能如下：
 
① 可以对纯英文文档实现压缩和解压；
 
② 较好的界面程序运行的说明。
 
 
 
 
 
介绍哈夫曼：
 
 
 
 
 
效率最高的判别树即为哈夫曼树
 
在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。
 
例如，在英文中，e的出现机率最高，而z的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时，e极有可能用一个比特来表示，而z则可能花去25个比特（不是26）。用普通的表示方法时，每个英文字母均占用一个字节，即8个比特。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。
 
霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln），N个权值Wi（i=1,2,...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,...n）。可以证明霍夫曼树的WPL是最小的。
 
 
 
文件压缩与解压
 
姓名：  范天祚 
 
1 程序说明
 
1.1数据结构
 
哈夫曼树
 
1.2函数功能说明
 
printfPercent界面
 
compress()读取文件内容并加以压缩，将压缩内容写入另一个文档
 
uncompress()解压缩文件，并将解压后的内容写入新文件
 
1.3 程序编写的思路及流程
 
压缩：统计字符出现次数、将节点按出现次数排序、构造哈夫曼树、设置字符编码、读文件字符、按设置好的编码替换字符、写入存储文件
 
解压：读取文件各参数、转换成二进制码、按码求对应字符、写入存储文件
 
#define _CRT_SECURE_NO_WARNINGS
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

struct head
{
    int b;						  //字符
    long count;                   //文件中该字符出现的次数
    long parent, lch, rch;        //make a tree
    char bits[256];               //the huffuman code
};

struct head header[512], tmp;  //节点树

void printfPercent(int per)
{
	int i = 0;
	printf("|");
	for(i = 0; i < 10; i++)
	{
		if(i < per/10)
			printf(">");
		else
			printf("-");
	}
	printf("|已完成%d%%\n",per);
}

//函数：compress()
//作用：读取文件内容并加以压缩
//将压缩内容写入另一个文档
int compress(const char *filename,const char *outputfile)
{
    char buf[512];
    unsigned char c;
    long i, j, m, n, f;
    long min1, pt1, flength;
    FILE *ifp, *ofp;
	int per = 10;
    ifp = fopen(filename, "rb");                  //打开原始文件
    if (ifp == NULL)
    {
        printf("打开文件失败:%s\n",filename);
        return 0;                             //如果打开失败，则输出错误信息
    }
    ofp = fopen(outputfile,"wb");                 //打开压缩后存储信息的文件
    if (ofp == NULL)
    {
        printf("打开文件失败:%s\n",outputfile);
        return 0;
    }
    flength = 0;
    while (!feof(ifp))
    {
        fread(&c, 1, 1, ifp);
        header[c].count ++;                       //读文件，统计字符出现次数
        flength ++;                               //记录文件的字符总数
    }
    flength --;
    header[c].count --;
    for (i = 0; i < 512; i ++)                    //HUFFMAN算法中初始节点的设置
    {
        if (header[i].count != 0)
            header[i].b = (unsigned char) i;
        else
            header[i].b = -1;
        header[i].parent = -1;
        header[i].lch = header[i].rch = -1;
    }

    for (i = 0; i < 256; i ++)                    //将节点按出现次数排序
    {
        for (j = i + 1; j < 256; j ++)
        {
            if (header[i].count < header[j].count)
            {
                tmp = header[i];
                header[i] = header[j];
                header[j] = tmp;
            }
        }
    }


    for (i = 0; i < 256; i ++)                    //统计不同字符的数量
	{
        if (header[i].count == 0)
            break;
	}

    n = i;
    m = 2 * n - 1;
    for (i = n; i < m; i ++)
    {
        min1 = 999999999;
        for (j = 0; j < i; j ++)
        {
            if (header[j].parent != -1) continue;
            if (min1 > header[j].count)
            {
                pt1 = j;
                min1 = header[j].count;
                continue;
            }
        }
        header[i].count = header[pt1].count;
        header[pt1].parent = i;
        header[i].lch = pt1;
        min1 = 999999999;
        for (j = 0; j < i; j ++)
        {
            if (header[j].parent != -1) continue;
            if (min1 > header[j].count)
            {
                pt1 = j;
                min1 = header[j].count;
                continue;
            }
        }
        header[i].count += header[pt1].count;
        header[i].rch = pt1;
        header[pt1].parent = i;
    }

    for (i = 0; i < n; i ++)                        //构造HUFFMAN树，设置字符的编码
    {
        f = i;
        header[i].bits[0] = 0;
        while (header[f].parent != -1)
        {
            j = f;
            f = header[f].parent;
            if (header[f].lch == j)
            {
                j = strlen(header[i].bits);
                memmove(header[i].bits + 1, header[i].bits, j + 1);
                header[i].bits[0] = '0';
            }
            else
            {
                j = strlen(header[i].bits);
                memmove(header[i].bits + 1, header[i].bits, j + 1);
                header[i].bits[0] = '1';
            }
        }
    }

    //下面的就是读原文件的每一个字符，按照设置好的编码替换文件中的字符
    fseek(ifp, 0, SEEK_SET);                                                //将指针定在文件起始位置
    fseek(ofp, 8, SEEK_SET);                                //以8位二进制数为单位进行读取
    buf[0] = 0;
    f = 0;
    pt1 = 8;

	printf("读取将要压缩的文件:%s\n",filename);
	printf("当前文件有:%d字符\n",flength);
	printf("正在压缩\n");

    while (!feof(ifp))
    {
        c = fgetc(ifp);
        f ++;
        for (i = 0; i < n; i ++)
        {
            if (c == header[i].b) break;
        }
        strcat(buf, header[i].bits);
        j = strlen(buf);
        c = 0;
        while (j >= 8)                                             //当剩余字符数量不小于8个时
        {
            for (i = 0; i < 8; i ++)                               //按照八位二进制数转化成十进制ASCII码写入文件一次进行压缩
            {
                if (buf[i] == '1') c = (c << 1) | 1;
                else c = c << 1;
            }
            fwrite(&c, 1, 1, ofp);
            pt1 ++;
            strcpy(buf, buf + 8);
            j = strlen(buf);
        }
		if(100 * f/flength > per)
		{
			printfPercent(per);
			per += 10;
		}
        if (f == flength)
			break;
    }
	printfPercent(100);

    if (j > 0)                                                      //当剩余字符数量少于8个时
    {
        strcat(buf, "00000000");
        for (i = 0; i < 8; i ++)
        {
            if (buf[i] == '1') c = (c << 1) | 1;
            else c = c << 1;                                        //对不足的位数进行补零
        }
        fwrite(&c, 1, 1, ofp);
        pt1 ++;
    }
    fseek(ofp, 0, SEEK_SET);                                        //将编码信息写入存储文件
	fwrite(&flength,1,sizeof(flength),ofp);
    fwrite(&pt1, sizeof(long), 1, ofp);
    fseek(ofp, pt1, SEEK_SET);
    fwrite(&n, sizeof(long), 1, ofp);
    for (i = 0; i < n; i ++)
    {
		tmp = header[i];

        fwrite(&(header[i].b), 1, 1, ofp);
		pt1++;
        c = strlen(header[i].bits);
        fwrite(&c, 1, 1, ofp);
		pt1++;
        j = strlen(header[i].bits);

        if (j % 8 != 0)                                             //当位数不满8时，对该数进行补零操作
        {
            for (f = j % 8; f < 8; f ++)
                strcat(header[i].bits, "0");
        }

        while (header[i].bits[0] != 0)
        {
            c = 0;
            for (j = 0; j < 8; j ++)
            {
                if (header[i].bits[j] == '1') c = (c << 1) | 1;
                else c = c << 1;
            }
            strcpy(header[i].bits, header[i].bits + 8);
            fwrite(&c, 1, 1, ofp);                                            //将所得的编码信息写入文件
			pt1++;
        }

		header[i] = tmp;
    }
    fclose(ifp);
    fclose(ofp);                                                              //关闭文件

	printf("压缩后文件为:%s\n",outputfile);
    printf("压缩后文件有:%d字符\n",pt1 + 4);

    return 1;                                       //返回压缩成功信息
}


//函数：uncompress()
//作用：解压缩文件，并将解压后的内容写入新文件
int uncompress(const char *filename,const char *outputfile)
{
    char buf[255], bx[255];
    unsigned char c;
	char out_filename[512];
    long i, j, m, n, f, p, l;
    long flength;
	int per = 10;
	int len = 0;
    FILE *ifp, *ofp;
	char c_name[512] = {0};
    ifp = fopen(filename, "rb");                                              //打开文件
    if (ifp == NULL)
    {
        return 0;     //若打开失败，则输出错误信息
    }

													  //读取原文件长
	if(outputfile)
		strcpy(out_filename,outputfile);
	else
		strcpy(out_filename,c_name);

    ofp = fopen(out_filename, "wb");                                            //打开文件
    if (ofp == NULL)
    {
        return 0;
    }

	fseek(ifp,0,SEEK_END);
	len = ftell(ifp);
	fseek(ifp,0,SEEK_SET);

	printf("将要读取解压的文件:%s\n",filename);
	printf("当前文件有:%d字符\n",len);
	printf("正在解压\n");

    fread(&flength, sizeof(long), 1, ifp);                                    //读取原文件长
    fread(&f, sizeof(long), 1, ifp);
    fseek(ifp, f, SEEK_SET);
    fread(&n, sizeof(long), 1, ifp);                                          //读取原文件各参数
    for (i = 0; i < n; i ++)                                                  //读取压缩文件内容并转换成二进制码
    {
        fread(&header[i].b, 1, 1, ifp);
        fread(&c, 1, 1, ifp);
        p = (long) c;
        header[i].count = p;
        header[i].bits[0] = 0;
        if (p % 8 > 0) m = p / 8 + 1;
        else m = p / 8;
        for (j = 0; j < m; j ++)
        {
            fread(&c, 1 , 1 , ifp);
            f = c;
            _itoa(f, buf, 2);
            f = strlen(buf);
            for (l = 8; l > f; l --)
            {
                strcat(header[i].bits, "0");                                  //位数不足，执行补零操作
            }
            strcat(header[i].bits, buf);
        }
        header[i].bits[p] = 0;
    }

    for (i = 0; i < n; i ++)
    {
        for (j = i + 1; j < n; j ++)
        {
            if (strlen(header[i].bits) > strlen(header[j].bits))
            {
                tmp = header[i];
                header[i] = header[j];
                header[j] = tmp;
            }
        }
    }

    p = strlen(header[n-1].bits);
    fseek(ifp, 8, SEEK_SET);
    m = 0;
    bx[0] = 0;


    while (1)
    {
        while (strlen(bx) < (unsigned int)p)
        {
            fread(&c, 1, 1, ifp);
            f = c;
            _itoa(f, buf, 2);
            f = strlen(buf);
            for (l = 8; l > f; l --)
            {
                strcat(bx, "0");
            }
            strcat(bx, buf);
        }
        for (i = 0; i < n; i ++)
        {
            if (memcmp(header[i].bits, bx, header[i].count) == 0) break;
        }
        strcpy(bx, bx + header[i].count);
        c = header[i].b;
        fwrite(&c, 1, 1, ofp);
        m ++;

		if(100 *  m/flength > per)
		{
			printfPercent(per);
			per += 10;
		}
        if (m == flength) break;
    }
	printfPercent(100);

    fclose(ifp);
    fclose(ofp);

	printf("解压后文件为:%s\n",out_filename);
    printf("解压后文件有:%d字符\n",flength);

    return 1;                   //输出成功信息
}

int main(int argc,const char *argv[])
{
	memset(&header,0,sizeof(header));
    memset(&tmp,0,sizeof(tmp));

	compress("测试文档.txt","测试文档.txt.zip");
	uncompress("测试文档.txt.zip","测试文档.txt 解压后.txt");
	system("pause");

	return 0;
}
 
 
 
2 功能展示
 
2.1 控制台显示
 
 
2.2 文件效果
 
开始时只有一个文件《测试文档.txt》：
 
 
打开《测试文档.txt》
 
 
《测试文档.txt》文件大小：
 
 
程序运行结束后多了两个文件：
 
 
以文本形式打开压缩二进制文件《测试文档.txt.zip》：
 
 
《测试文档.txt.zip》文件属性：
 

 

  
 
 
图像有损压缩与无损压缩
 
Lossy and lossless compression are two kinds of data compression techniques. Here in this article, you will get to learn about what is lossy and lossless compression, their differences, and uses.
 
 
 有损和无损压缩是两种数据压缩技术。 在本文的此处，您将了解什么是有损和无损压缩，它们的区别和用途。 
 
 
So, let’s start with the basics.
 
 
 因此，让我们从基础开始。 
 
 
 什么是数据压缩？ (What is Data Compression?)
 
 
Data compression is the process of diminishing the storage size of any data or file so that it consumes less space on the disk. It is the technique of modifying, restructuring, encoding and converting the schema or instance of any data to reduce its size.
 
 
 数据压缩是减小任何数据或文件的存储大小，以使其在磁盘上占用较少空间的过程。 它是一种修改，重组，编码和转换任何数据的模式或实例以减小其大小的技术。 
 
 
In simple words, it is converting the file in such a way that its size is reduced to a maximum extent. Data compressions is also known as bit-rate reduction or source coding.
 
 
 简而言之，它将以最大程度减小文件大小的方式转换文件。 数据压缩也称为比特率降低或源编码。 
 
 
Check the diagram below:
 
 
 检查下图： 
 
 

  
 
 
An example of an image that is converted or compressed to reduce its size without losing the ability to reconstruct the image.
 
 
 转换或压缩以减小其尺寸而又不损失重建图像能力的图像的示例。 
 
 
Now, the question here is why there is a need for data compression?
 
 
 现在，这里的问题是为什么需要数据压缩？ 
 
 
There are two primary reasons for the same.
 
 
 造成这种情况的主要原因有两个。 
 
 
Storage – it helps in reducing the size of data that is required to store it on the disk
 存储–它有助于减少将数据存储在磁盘上所需的数据量 
Time – saves time in data transmission as the size is reduced to an extent
 时间–尺寸减小到一定程度，节省了数据传输时间 
 
You are getting the point!
 
 
 您明白了！ 
 
 
Now coming back to the main topic, there are mainly two types of data compression techniques. Let’s discuss them.
 
 
 现在回到主要主题，主要有两种类型的数据压缩技术。 让我们讨论一下。 
 
 
 数据压缩技术 (Data Compression Techniques)
 
 

  
 
 
 有损压缩 (Lossy Compression)
 
 
Lossy compression is a technique that involves the elimination of a specific amount of data. It helps in reducing the file size to a great extent without any noticeable thing. Also, once the file is compressed, it cannot be restored back to its original form as the data from the file is significantly reduced. This technique is much more useful when the quality of the file is not essential. Additionally, it helps to save much space on the disk to store the data.
 
 
 有损压缩是一种涉及消除特定数量数据的技术。 它有助于在没有任何明显注意的情况下大大减小文件大小。 同样，一旦压缩了文件，由于来自文件的数据将大大减少，因此无法将其恢复为原始格式。 当文件的质量不是很重要时，此技术会更加有用。 此外，它有助于节省磁盘上的大量空间来存储数据。 
 
 
Lossy compression is not useful when the quality of the file is essential. Besides, if there’s any further analysis to be processed on the record, this method is not ideal. This method is generally used for audio and video compression, where there is a significant amount of data loss, and even users cannot recognize it.
 
 
 当文件的质量至关重要时，有损压缩是没有用的。 此外，如果记录上有任何进一步的分析要处理，这种方法也不理想。 此方法通常用于音频和视频压缩，这会导致大量数据丢失，甚至用户也无法识别它。 
 
 
Example of lossy compression: JPEG image
 
 
 有损压缩的示例：JPEG图像 
 
 

  
 
 
Image Source
 
 
 图片来源 
 
 
“Compressed image (left) shows blocking artifacts compared to the original image (right) as a result of the JPEG compression scheme used.”
 
 
 “由于使用了JPEG压缩方案，与原始图像(右)相比，压缩图像(左)显示出块状伪影。” 
 
 
 无损压缩 (Lossless Compression)
 
 
Lossless compression is a technique that involves only a certain amount of elimination of data. This technique also helps in reducing the file size, but not to the greater extent as that of lossy compression. Instead, in this method, if the file is compressed, it can be restored back to its original form. Further, the quality of the data is not compromised; hence, the reduction in size is not much.
 
 
 无损压缩是一种仅涉及消除一定量数据的技术。 此技术还有助于减小文件大小，但不会像有损压缩那样在很大程度上。 相反，在这种方法中，如果文件被压缩，则可以将其还原回其原始形式。 此外，数据的质量不会受到影响； 因此，尺寸减小不多。 
 
 
Lossless compression is not useful when you want reduced size for extra storage. Also, if there is any further analysis to be performed on the file, lossless compression is not beneficial. It is useful for maintaing the originality of files by eliminating only unwanted data. This technique is commonly used for text files, sensitive documents, and confidential information.
 
 
 当您希望减小尺寸以增加存储空间时，无损压缩将无用。 此外，如果要对文件执行任何进一步的分析，则无损压缩将无益。 通过仅消除不需要的数据，对于保持文件的原始性很有用。 此技术通常用于文本文件，敏感文档和机密信息。 
 
 
Example of lossless compression: PNG image
 
 
 无损压缩示例：PNG图像 
 
 

  
 
 
Image Source
 
 
 图片来源 
 
 
“The original image (left) is identical to the compressed image (right). It is represented by the identical graphs at the bottom that show the grey values for the pixels in each column is the same between the two images.”
 
 
 “原始图像(左)与压缩图像(右)相同。 它由底部的相同图形表示，该图形显示两列图像中每列像素的灰度值相同。” 
 
 
 有损压缩与无损压缩之间的区别 (Difference between Lossy and Lossless Compression)
 
 
Basis
Lossy Compression
Lossless Compression
Definition
Lossy compression is a technique that involves the elimination of a specific amount of data. It helps in reducing the file size to a great extent without any noticeable thing
Lossless compression is a technique that involves only a certain amount of elimination of data. This technique also helps in reducing the file size, but not to the greater extent
Compression Ratio
High
Low
File Quality
Low
High
Elimination of Data
Even the necessary data is also removed which isn’t noticeable
Only some specific amount of unwanted data is removed
Restoration
Cannot restore its original form
Can restore its original form
Loss of Information
This technique involves some loss of information
This technique doesn’t include any loss of information
Data Accommodation
More data accommodation
Less data accommodation
Distortion
Files are distorted
No distortion
Data holding capacity
More
Less
Algorithms Used
Transform coding, DCT, DWT, fractal compression, RSSMS
RLW, LZW, Arithmetic encoding, Huffman encoding, Shannon Fano coding
File Types
JPEG, GIF, MP3, MP4, MKV, OGG, etc.
RAW, BMP, PNG, WAV, FLAC, ALAC, etc.
 
 
 基础 
 有损压缩 
 无损压缩 
 定义 
 有损压缩是一种涉及消除特定数量数据的技术。 它有助于在没有任何明显注意的情况下大大减小文件大小 
 无损压缩是一种仅涉及消除一定量数据的技术。 此技术还有助于减小文件大小，但不会在更大程度上 
 压缩率 
 高 
 低 
 档案品质 
 低 
 高 
 消除数据 
 即使必要的数据也被删除，这并不明显 
 仅删除了特定数量的有害数据 
 恢复 
 无法恢复其原始形式 
 可以恢复其原始形式 
 信息丢失 
 此技术涉及一些信息丢失 
 此技术不包括任何信息丢失 
 数据调整 
 更多数据住宿 
 数据容纳量减少 
 失真 
 文件变形 
 无失真 
 资料储存能力 
 更多 
 减 
 使用的算法 
 变换编码，DCT，DWT，分形压缩，RSSMS 
 RLW，LZW，算术编码，霍夫曼编码，香农法诺编码 
 文件类型 
 JPEG，GIF，MP3，MP4，MKV，OGG等 
 RAW，BMP，PNG，WAV，FLAC，ALAC等 
 
 
 使用哪个？ (Which One to Use?)
 
 
Although both are the types of data compression, each can be useful under different situations. Like, lossy compression helps in reducing the file size, which means it is helpful to those who have vast amounts of data stored on the database. So, this technique is useful in storing the data with a much-diminished size. Also, for webpages files of such lower size is beneficial for faster loading.
 
 
 尽管这两种都是数据压缩的类型，但是每种压缩在不同情况下都是有用的。 像，有损压缩有助于减小文件大小，这对那些在数据库上存储大量数据的用户有帮助。 因此，此技术在存储大小减小的数据时很有用。 同样，对于网页而言，这种较小的文件有利于更快地加载。 
 
 
Further, this process doesn’t allow any after analysis of the data once the compression is completed. Also, the file cannot be restructured in its original form as it involves the loss of data.
 
 
 此外，压缩完成后，此过程将不允许对数据进行任何后续分析。 同样，该文件不能以其原始形式进行重组，因为它涉及数据丢失。 
 
 
Unlike lossy compression, lossless compression doesn’t involve any loss of data. Neither the quality of data is compromised, nor the size of data is excessively reduced. It keeps the original format so it can be restored, and further operation can be performed. This method is helpful for those who need to access the data back again without compromising its quality.
 
 
 与有损压缩不同，无损压缩不涉及任何数据丢失。 既不会损害数据质量，也不会过度减少数据大小。 它保留了原始格式，因此可以还原，并且可以执行进一步的操作。 此方法对需要再次访问数据而不影响其质量的用户很有用。 
 
 
 最后的话 (Final Words)
 
 
Both lossy compression and lossless compression helps in the compression of data in their unique way. While lossy compression is useful to store data by compromising the data, lossless compression doesn’t. Lossless compression technique is beneficial for maintaing the originality of data, and lossy compression, on the other hand, doesn’t. Both the methods are helpful in database management, to identify and compress files accordingly.
 
 
 有损压缩和无损压缩都以其独特的方式帮助压缩数据。 尽管有损压缩通过破坏数据来存储数据很有用，但无损压缩却没有。 无损压缩技术有利于保持数据的原始性，而无损压缩则不能。 两种方法都有助于数据库管理，从而相应地识别和压缩文件。 
 
 
If there’s any other query regarding data compression or both the techniques of data compression, then let us know in the comment box below.
 
 
 如果还有关于数据压缩或这两种数据压缩技术的任何其他查询，请在下面的注释框中告知我们。 
 
 

  
翻译自: https://www.thecrazyprogrammer.com/2019/12/lossy-and-lossless-compression.html
 
 
图像有损压缩与无损压缩