1 基本概念
数据压缩的核心在于用更少的比特数表示信息，其可行性建立在大多数真实数据存在冗余的基础上。例如，一段英文文本中字母“e”的频繁出现、一幅图像中大面积的蓝色天空，都构成了可被压缩的统计规律或结构冗余。
1.1 信息熵与冗余
信息熵是衡量数据不确定性的度量，由克劳德·香农在1948年提出。一个符号集的熵越高，表示其每个符号携带的平均信息量越大，理论上能压缩到的极限就越小。冗余则是数据中可被去除的重复或可预测部分，它等于数据原始大小减去熵值对应的理论最小大小。
1.1.1 香农信息熵定义
对于离散随机变量 \(X\)，其取值集合为 \(\{x_1, x_2, \dots, x_n\}\)，概率分布为 \(p(x_i)\)，则信息熵 \(H(X)\) 定义为： \[ H(X) = -\sum_{i=1}^{n} p(x_i) \log_2 p(x_i) \quad (\text{单位：比特}) \] 当所有符号等概率出现时，熵达到最大值 \(\log_2 n\)；当某个符号概率为1时，熵为0。熵给出了无损压缩的理论下限。
1.2 压缩比与失真
压缩比定义为原始数据大小与压缩后数据大小的比值（如 10:1）。在有损压缩中，还需引入失真度量，描述恢复数据与原始数据的差异。压缩比与失真通常互为代价：追求高压缩比往往意味着更大的失真。
1.3 压缩的分类
根据是否允许信息损失，数据压缩分为两大类。
1.3.1 无损压缩
无损压缩要求解压后数据与原始数据完全一致，不丢失任何比特。典型应用包括文本文件、程序代码、数据库记录等。常见算法有霍夫曼编码、LZ系列等。
1.3.2 有损压缩
有损压缩允许一定程度的精度损失，以换取显著更高的压缩比。人类感官（视听）对某些细微差异不敏感，因此有损压缩广泛用于图像、音频、视频领域。典型算法包括JPEG、MP3等。
2 无损压缩算法
2.1 统计编码
统计编码基于符号出现的频率分配码字，高频符号用短码，低频符号用长码，实现平均码长接近熵。
2.1.1 霍夫曼编码
霍夫曼编码（Huffman Coding）由大卫·霍夫曼于1952年提出。它通过构建最优二叉树（霍夫曼树），为每个符号生成唯一前缀码。编码过程：将所有符号按概率排序，反复合并最小概率的两个节点，直到建成一棵树；然后从根到叶子的路径赋予二进制码（左0右1或相反）。霍夫曼编码在给定符号概率分布下能达到最小平均码长，属于最优前缀码。
2.1.1.1 动态霍夫曼编码
静态霍夫曼编码需要提前统计全局频率，并传送码表。动态（自适应）霍夫曼编码在编码过程中动态更新符号频次和树结构，无需预存码表，适合流式数据。常见实现有 FGK（Faller-Gallager-Knuth）算法和 Vitter 算法。
2.1.2 算术编码
算术编码将整个消息映射到[0,1)区间内的一个实数，而非为每个符号分配独立码字。它通过不断分割区间来编码，对概率分布逼近更精细，因此平均码长可无限接近熵。算术编码在压缩效率上优于霍夫曼编码，尤其当符号概率接近时。实用中常使用整数算术避免浮点计算，如标准的自适应算术编码。
2.1.3 香农-范诺编码
香农-范诺编码由香农和范诺独立提出，是霍夫曼编码的前身。它按概率降序排列符号，然后递归地将符号集分成概率和尽量接近的两组，分别赋予0和1。虽然可以得到前缀码，但它并非最优——某些情况下平均码长比霍夫曼编码略长，故在实际中已很少使用。
2.2 字典编码
字典编码将输入数据中重复出现的连续字符串（短语）用字典中的索引替代，从而压缩。
2.2.1 LZ77算法
LZ77由亚伯拉罕·兰佩尔和雅各布·齐夫于1977年提出。它使用滑动窗口，在编码时查找当前字符串之前出现的最长匹配，输出为（距离，长度）对。如果找不到匹配，则直接输出原始字符。LZ77奠定了许多后续压缩格式的基础，如DEFLATE（ZIP、gzip的核心）、LZSS等。
2.2.2 LZ78与LZW算法
LZ78（1978年）采用动态构建字典的方式，不在固定滑动窗口中查找，而是将首次出现的短语添加进字典，后续匹配时输出字典索引。特里·韦尔奇在此基础上改进得到LZW算法（1984年），它省略了LZ78中单独输出字符的处理，使得压缩率更高。LZW曾广泛用于GIF图像和Unix的compress工具。
2.3 游程编码（RLE）
游程编码（Run-Length Encoding, RLE）将连续重复的符号序列替换为“符号+重复次数”。它特别适合二值图像或含大量连续相同字节的数据（如传真、简单位图）。RLE实现简单，但在无连续重复的数据上可能反而增加体积（例如英文文本）。现代压缩方案常将RLE作为预处理步骤。
2.4 熵编码与预测结合
通过预测去除数据中的相关性，然后对预测误差（残差）进行熵编码，可以进一步提升压缩率。
2.4.1 差分编码
差分编码（Differential Coding）将每个采样值替换为它与前一个值的差值。若数据连续变化缓慢（如音频信号、时间序列），差值分布将高度集中在小值附近，从而更易压缩。它是许多有损/无损预测编码的基础。
2.4.2 上下文模型
上下文模型利用当前符号周围（之前或相邻位置）的符号来预测其概率，再对预测的残差或符号本身进行算术编码。例如，PNG图像压缩中使用的“预测器”（Filter），通过行间差分和Paeth预测器来降低像素冗余。更高级的上下文模型（如PAQ系列）能逼近压缩极限，但速度极慢。
3 有损压缩算法
3.1 量化技术
量化是有损压缩的核心步骤，它将连续的取值映射到离散的有限集合，引入误差。
3.1.1 标量量化
标量量化对每个独立数值进行量化。最简单的例子是均匀量化：将取值范围分成等宽的区间，每个区间用一个代表值代替。更有效的优化方法是根据概率分布设置非均匀量化间隔（如劳埃德-麦克斯算法），使得量化误差的期望最小。
3.1.2 向量量化
向量量化将多个数值视为一个向量，用一个码本中的索引代替该向量。码本通过聚类（如K-means）从训练数据中生成。向量量化可以达到比标量量化更低的比特率，但编码复杂度较高，常用于早期语音编码和图像压缩（如VQ-based方法）。
3.2 变换编码
变换编码将数据从时域/空域变换到频域，利用能量集中在少数低频系数的特点，舍弃高频分量以压缩。
3.2.1 离散余弦变换（DCT）
DCT将图像块（如8×8像素）从空间域变换到频率域，产生一个低频分量（DC）和多个高频分量（AC）。人眼对高频细节不敏感，因此对AC系数进行粗量化即可大幅压缩。JPEG压缩的核心就是DCT+量化+熵编码。
3.2.2 小波变换
小波变换提供多分辨率分析，将图像分解为逼近子带和多个细节子带。它避免了DCT的块效应，在低比特率下质量更优。JPEG 2000等标准采用离散小波变换（DWT），同时支持无损和有损压缩。
3.3 预测编码
预测编码根据已解码的样本预测当前样本，只编码预测误差。
3.3.1 DPCM与ADPCM
差分脉冲编码调制（DPCM）对相邻采样值（如音频幅度）的差值进行量化和编码。自适应DPCM（ADPCM）根据信号变化动态调整量化步长，在保持较高压缩比的同时降低失真。ADPCM广泛用于电话语音编码（如G.726标准）。
3.4 感知编码
感知编码利用人类听觉或视觉的感知局限性，忽略人耳/人眼无法察觉的信息。
3.4.1 心理声学模型
心理声学模型基于人耳的掩蔽效应：一个强音会掩盖其附近频率上较弱的声音。MP3、AAC等音频编码器利用该模型，在量化时保留掩蔽阈值以上的频率成分，舍去不可闻的部分，从而大幅降低数据量。
3.4.2 视觉掩蔽效应
视觉掩蔽效应包括亮度掩蔽（人眼对暗区噪声更敏感）和纹理掩蔽（复杂纹理区域可容忍更高的噪声）。在JPEG、H.264等视频编码中，量化步长会根据局部视觉特性进行调整，以在相同比特率下提供更好的主观质量。
4 常见压缩格式与应用
4.1 文本与通用数据
通用压缩工具通常组合多种算法以取得较好压缩率。
4.1.1 ZIP、gzip与bzip2
- ZIP：使用DEFLATE算法（LZ77+霍夫曼编码），支持多文件存档，是最常见的通用压缩格式。
- gzip：同样基于DEFLATE，但通常仅压缩单文件（配合tar打包），广泛应用于Unix/Linux。
- bzip2：使用Burrows-Wheeler变换（BWT）+游程编码+霍夫曼编码，压缩率高于DEFLATE，但速度较慢。
4.2 图像压缩
4.2.1 JPEG（有损）
JPEG（Joint Photographic Experts Group）是广泛使用的有损图像标准。它采用8×8块DCT、量化、之字形扫描和霍夫曼编码。自然照片中可获得10:1～20:1的压缩比而基本不产生可见失真。但JPEG不支持透明背景，且在高压缩比下出现块效应。
4.2.2 PNG（无损）
PNG（Portable Network Graphics）采用DEFLATE算法和行间预测（Filter），支持真彩色、索引色和Alpha通道。它取代了GIF，用于网页和需要无损保存的图像（如截图、图标）。PNG压缩比通常不如有损格式，但零质量损失。
4.2.3 WebP与AVIF
- WebP：Google开发，支持有损（基于VP8关键帧）和无损（类似PNG但更高效），通常比JPEG小25-34%的同时保持同等视觉质量。
- AVIF：基于AV1视频编码的静止图像格式，支持HDR、广色域，压缩效率比WebP再提升约20%，但编码速度较慢。
4.3 音频压缩
4.3.1 MP3、AAC与Vorbis
- MP3：最早普及的有损音频格式，采用心理声学模型和MDCT（改进型离散余弦变换），典型比特率128-320 kbps。
- AAC：MPEG-2/4标准，比MP3在同等比特率下音质更优，被用于iTunes、YouTube等。
- Vorbis：开源有损编码，不使用专利技术，通常在中低比特率下表现优于MP3，常见于游戏和Ogg容器。
4.3.2 FLAC（无损）
FLAC（Free Lossless Audio Codec）提供无损压缩，压缩率通常为原始CD的50-60%。它基于线性预测和残差编码，支持流式播放和快速定位。发烧友和档案保存中广泛使用。
4.4 视频压缩
4.4.1 H.264/AVC
H.264（AVC）是目前最普及的视频编码标准。它采用基于块的帧内/帧间预测、整数DCT、去块滤波和上下文自适应熵编码（CABAC/CAVLC）。在相同画质下，比特率比MPEG-2降低约50%。用于蓝光、YouTube、视频会议等。
4.4.2 H.265/HEVC
HEVC（High Efficiency Video Coding）相比H.264效率提升约50%。它采用了更大的编码树单元（CTU，最大64×64）、更灵活的预测模式和更精细的运动估计。4K/8K视频中广泛应用，但专利授权纠纷较少。
4.4.3 AV1与VVC
- AV1：由互联网联盟（AOMedia）开发，开源免专利费，压缩效率比HEVC高约20-30%，但编码极其复杂（解码相对较轻）。用于YouTube、Netflix等流媒体。
- VVC（H.266）：最新国际标准，目标是比HEVC再提升约30%的效率，预计用于未来8K/VR视频。
5 压缩性能评估
5.1 压缩比
压缩比 = 原始大小 / 压缩后大小。无损压缩的压缩比受数据本身冗余度限制（一般文本2-5:1，程序代码2-3:1）。有损压缩的压缩比可任意调节，典型值如JPEG 10:1、MP3 10:1（128 kbps）、H.264 50:1等。
5.2 压缩/解压速度
压缩速度和解压速度通常不对称（如LZMA解压比压缩快）。速度受算法复杂度、实现优化（SIMD、多线程）影响。实时场景（如视频直播）要求极低延迟快速解码。
5.3 失真度量
5.3.1 均方误差（MSE）
MSE = \(\frac{1}{n}\sum_{i=1}^n (x_i - y_i)^2\)，其中\(x_i\)为原始数据，\(y_i\)为恢复数据。MSE越小表示失真越小。
5.3.2 峰值信噪比（PSNR）
PSNR = \(10\log_{10}\left(\frac{MAX^2}{MSE}\right)\)，其中MAX为数据最大可能取值（如图像255）。单位dB，通常30 dB以上可接受，40 dB以上质量优秀。
5.3.3 结构相似性（SSIM）
SSIM综合考虑亮度、对比度和结构，更符合人眼感知。值在0到1之间，接近1表示与原图结构高度相似。它比PSNR更可靠，尤其对于块效应和模糊的评估。
6 前沿与趣谈
6.1 无损压缩的理论极限：香农极限
香农信源编码定理指出：无损压缩的最低平均码长不能低于信源熵。这一极限称为香农极限。例如，对于均匀分布的256个符号（字节），每个符号熵为8比特，理论上完全随机数据无法被无损压缩。实际数据由于存在冗余，才使得压缩可行。某些极端优化算法（如PAQ8）曾逼近香农极限，但速度极慢。
6.2 有损压缩的“玄学”争议：MP3 vs 无损发烧友
自MP3流行以来，“不同MP3编码器音质差异能否听出”一直是音响圈热议话题。有人认为320 kbps MP3已接近透明（与CD无异），但发烧友坚持认为听感差异明显，归咎于“数字味”和“高频丢失”。双盲测试往往并不支持后者的观点，但这不妨碍“无损才是真理”成为玄学圈的一种信仰。类似争议也出现在视频领域（如电影人物发际线有没有被压缩糊掉）。
6.3 数据压缩在AI中的应用：神经网络压缩
随着深度学习模型越来越大（如GPT-3有1750亿参数），模型压缩成为落地关键。常见方法包括：量化（将32位浮点权重量化为8位或更少）、剪枝（删除冗余连接）、知识蒸馏（小模型模仿大模型输出）、低秩分解等。这些技术本质上也是数据压缩——用更少的比特存储或推理神经网络。有趣的是，压缩理论也被用于分析神经网络的信息瓶颈和泛化能力。
6.4 彩蛋：压缩档案的“塞爆”梗——如何把1GB文件压成1KB（不可能任务）
网络上流传着一些“压缩神技”：先往文件里塞满重复的0，然后用RLE或ZIP压到极小。确实，一个全部由重复字节组成的1GB文件可以被压缩到几乎只有头信息的大小（例如1KB）。但这是“杠精式”压缩——因为原始数据的“信息量”本来就只有一丁点。真正的随机数据（如加密的1GB文件）是无法被压缩的，如果有人说能把“任何1GB文件”压到1KB，那不是在变魔术，就是在做白日梦。这个梗常常用来调侃那些伪造压缩率软件的广告。