1 基本概念
1.1 定义与作用
源编码是信息论中的一个基本环节，指对信息源输出的符号、数据或消息进行重新表示，使其以更少的比特数完成传输、存储或处理。其核心任务不是改变信息内容本身，而是通过更紧凑的表示方式，减少不必要的重复与冗余。
在实际系统中，源编码既可以用于无失真压缩，也可以用于允许一定信息损失的压缩。前者强调原始数据可以完全恢复，后者则在可接受的质量下降范围内换取更高的压缩比。无论采用何种形式，源编码的目的都在于提升数据表示的经济性。
1.2 与信息论的关系
源编码是信息论研究的重点之一，与信源模型、熵、平均码长等概念紧密相连。信息论从统计规律的角度描述数据的不确定性，而源编码则试图找到一种接近理论极限的表示方法。
在香农理论框架下，信源熵给出了信息平均不确定性的下界，源编码则研究如何设计码字，使平均码长尽量逼近这一界限。因此，源编码不仅是工程实现问题，也是信息论中关于“最紧凑表示”的理论体现。
1.3 源编码的目标
源编码的目标通常可以概括为三个方面：降低冗余、提高传输效率和减少存储开销。这些目标彼此关联，通常通过统一的编码设计来实现。
1.3.1 降低冗余
数据中的冗余表现为可预测重复、统计分布不均衡或结构性重复。源编码通过识别并消除这些可压缩部分，使编码结果更接近信息本身的最小描述长度。
1.3.2 提高传输效率
当数据经过压缩后，所需传输比特数减少，通信链路的带宽利用率随之提高。对于实时系统而言，这种效率提升往往还能降低传输延迟并缓解网络拥塞。
1.3.3 减少存储开销
压缩后的数据占用更少存储空间，便于长期保存和批量管理。对于大规模数据库、媒体库和备份系统而言，源编码能够显著降低硬件成本与管理负担。
2 数学基础
2.1 信源与概率模型
信息论通常将信源视为一个随机过程，其输出符号按照一定概率分布出现。若离散信源由符号集组成，则每个符号可对应一个发生概率，整个信源的统计特性由概率模型刻画。
这种概率描述是源编码设计的基础。编码器通过利用符号出现频率的差异，为高概率符号分配较短码字，为低概率符号分配较长码字，从而降低平均码长。
2.2 熵与平均码长
熵反映了信源输出的不确定程度，而平均码长衡量编码方案在实际中的资源消耗。源编码的核心问题之一，就是使平均码长尽可能接近熵。
2.2.1 香农熵
香农熵是离散随机变量不确定性的度量，常写作各符号概率的对数加权和。熵越大，说明信源越难预测；熵越小，说明数据结构越集中，压缩潜力通常也越大。
2.2.2 条件熵
条件熵描述在已知某些信息后，随机变量剩余的不确定性。对于具有上下文依赖的数据，条件熵能够更准确地反映真实可压缩性，因此在预测编码和上下文建模中具有重要意义。
2.2.3 码长下界
对无失真离散源编码而言，平均码长不可能无限接近于零，它至少受到信源熵的约束。一般来说，任何可译码方案的平均码长都存在理论下界，实际编码只能在此基础上逼近，无法突破。
2.3 编码效率
编码效率通常用信源熵与平均码长的比值来描述，用于衡量编码方法对理论极限的接近程度。效率越高，说明编码越紧凑，冗余越少。
在工程实践中，编码效率还会受到算法复杂度、码表管理、有限长度效应和实现开销的影响。因此，理想的高效率编码并不一定在所有场景中都最优，还需兼顾计算代价与系统约束。
3 编码类型
3.1 定长编码
定长编码为每个符号分配相同长度的码字，结构简单，便于快速编码和译码。它的优点是实现容易、同步性好，缺点则是难以利用符号概率的差异，压缩能力有限。
在符号分布接近均匀时，定长编码较为合适；但当数据存在明显偏斜时，其平均码长通常高于可变长方案。
3.2 变长编码
变长编码允许不同符号使用不同长度的码字，通常让高频符号使用短码，低频符号使用长码。它比定长编码更符合数据统计特性，因此在压缩中应用广泛。
3.2.1 前缀码
前缀码是一类重要的变长码，要求任一码字都不是另一码字的前缀。该性质保证了译码时可以逐步识别，不会发生歧义，是许多经典压缩算法的基础。
3.2.2 唯一可译码
唯一可译码指的是整串编码后可以无歧义地还原出原始符号序列。前缀码必然属于唯一可译码，但唯一可译码的范围更广，并不一定满足前缀约束。
3.2.3 最优码
在给定符号概率和码字约束条件下，若某种编码方案使平均码长达到最小，则可称为最优码。哈夫曼码是无失真场景中最著名的最优前缀码之一。
3.3 无失真源编码
无失真源编码要求压缩后的数据能够完全恢复原文，不允许丢失任何信息。其适用对象包括文本、程序文件、结构化数据以及部分对精度要求极高的科学数据。
3.3.1 可逆压缩
可逆压缩强调编码与解码过程严格对应，解压后结果与原始输入完全一致。它常用于档案保存、数据库传输和软件分发等场景。
3.3.2 常见实现方法
常见的无失真压缩方法包括哈夫曼编码、算术编码、游程编码以及字典压缩等。实际系统中，往往将多种技术组合使用，以适应不同数据的统计结构。
3.4 有损源编码
有损源编码允许在压缩过程中丢弃部分信息，以换取更高压缩率。它主要用于图像、音频和视频等人类感知较强的数据类型。
3.4.1 失真度量
失真度量用于描述重构数据与原始数据之间的差异。常见指标包括均方误差、绝对误差以及感知质量相关指标，不同应用会采用不同的评价方式。
3.4.2 率失真权衡
率失真理论研究压缩比与失真程度之间的平衡关系。一般而言，允许的失真越大，所需比特率越低；反之，若要求更高保真度，则必须保留更多信息。
4 经典编码方法
4.1 香农编码
香农编码是一种基于符号概率的经典变长编码方法，通常按符号出现概率排序后，为每个符号分配长度接近其自信息量的码字。它为后续更高效的编码方法提供了理论与构造思路。
该方法结构清晰，便于说明“概率越高，码字越短”的基本原则，但在实际最优性上通常不如哈夫曼编码。
4.2 费诺编码
费诺编码又称香农-费诺编码，其构造思路是将符号集合按概率排序后递归划分成两部分，并分别赋予不同前缀。该方法直观、易于手工构造，具有较好的教学示范意义。
与哈夫曼编码相比，费诺编码不一定达到最优平均码长，但在符号数量较少或需要快速构造时仍有一定价值。
4.3 哈夫曼编码
哈夫曼编码是一种广泛使用的无失真压缩方法，通过构建最优前缀码来最小化平均码长。它在文本压缩、文件格式和通信系统中都有重要地位。
4.3.1 构造过程
哈夫曼编码通常从各符号概率或频率出发，反复合并最小的两个权值，形成一棵二叉树。最终，树的路径长度对应码字长度，较高频符号被安排在较浅层，从而获得较短编码。
4.3.2 最优性证明
哈夫曼编码的最优性建立在前缀码约束下的贪心选择性质之上。它能够保证在所有二元前缀码中实现最小平均码长，因此成为经典的最优无失真编码方案。
4.3.3 应用场景
哈夫曼编码常见于文本压缩、图像格式、音频压缩中的局部步骤以及各类数据流编码。由于其实现相对成熟，且解码速度较快，仍是许多系统中的基础工具。
4.4 算术编码
算术编码不是为每个符号单独分配整段码字，而是将整个消息映射到一个逐步缩小的区间内，再用区间中的一个数表示整段信息。它能够更细致地利用概率分布，因此压缩效率通常很高。
4.4.1 基本原理
在算术编码中，消息序列被逐个符号细分为概率区间，编码结果对应于最终区间内的一段数值表示。随着符号增加，区间不断缩小，所需比特数也随之增长。
4.4.2 与哈夫曼编码的比较
相比哈夫曼编码，算术编码对概率分布的适应性更强，尤其适合符号分布不均匀或概率值较精细的场景。不过，它的实现复杂度较高，对数值精度和容错设计也更敏感。
4.5 游程编码
游程编码通过记录连续重复符号的长度来压缩数据，常用于存在大量连续相同元素的序列。它的思想简洁，适合结构规则明显的数据。
4.5.1 适用数据特征
游程编码最适合长串重复值较多的数据，如黑白图像的扫描线、简单图形中的大片空白区域或某些传感器输出序列。若数据变化频繁，则其效果往往不佳。
4.5.2 压缩效果分析
在重复段较长时，游程编码可显著减少表示长度；但若符号交替频繁，不仅难以压缩，反而可能增加开销。因此，它通常与其他压缩技术结合使用，以提高适应性。
5 理论极限
5.1 香农第一定理
香农第一定理指出，信源的信息量存在一个由熵决定的理论极限。对于无失真表示而言，任何编码方案都无法将平均描述长度压缩到低于熵所暗示的下界。
这一结论奠定了源编码的基本理论框架，也说明了压缩性能终究受信源统计特性制约。
5.2 源编码定理
源编码定理表明，在足够长的码长条件下，可以构造出平均码长任意接近信源熵的编码方案。换言之，只要允许足够长的块编码，压缩效率就能逼近理论最优。
该定理是无失真压缩可行性的核心依据，也解释了为何许多实际压缩算法会采用分组、预测或上下文建模来接近极限。
5.3 接近熵极限的编码
接近熵极限的编码通常需要更精细的概率建模和更长的块处理方式。算术编码、上下文建模和高阶统计压缩方法，都是向熵极限逼近的常见手段。
不过，越接近理论极限，往往越依赖复杂计算与高质量模型，因此工程上需要在压缩率与实现成本之间折中。
5.4 有限长编码问题
理论结果通常以长序列为前提，而实际系统处理的数据块长度有限，因此会出现边界效应和额外开销。有限长条件下，编码性能往往略低于渐近理论值。
这类问题包括码表建立成本、块间独立假设偏差以及随机波动带来的效率损失，都是工程实现中需要考虑的现实因素。
6 实际应用
6.1 文本压缩
文本数据通常具有较强的符号统计规律和重复结构，因此很适合采用无失真源编码。常见做法包括字典压缩、哈夫曼编码和混合型压缩策略。
在文档存储、网页传输和日志归档中，文本压缩能够有效降低带宽与磁盘占用，同时保持内容完全可恢复。
6.2 图像压缩
图像数据兼具空间相关性和人类视觉冗余，因而既可用于无损压缩，也广泛用于有损压缩。不同目标下会选用不同编码策略。
6.2.1 无损图像编码
无损图像编码保留每个像素值的精确内容，适用于医学影像、图像归档和专业制图等场景。它通常利用预测、变换后的符号统计和熵编码来提高压缩率。
6.2.2 有损图像编码
有损图像编码通过舍弃视觉上不敏感的信息来提升压缩效率，常见于照片存储和网络传播。其目标是在尽量保持观感质量的前提下减少比特数。
6.3 音频压缩
音频压缩通常结合感知模型与源编码技术，利用人耳对某些频段或细节不敏感的特点进行数据削减。无损音频主要用于高保真存档，有损音频则更适合日常播放和流媒体。
6.4 视频压缩
视频压缩利用时间相关性、空间相关性以及视觉感知特性来减少数据量。由于视频数据规模庞大，源编码在其中通常与预测、变换和熵编码联合使用。
6.5 数据存储与通信系统
在存储系统中，源编码能降低容量需求并提高访问效率；在通信系统中，则可减少发送比特数并改善链路利用率。它是多种现代数据处理链路中的基础模块。
7 性能评估
7.1 压缩率
压缩率是衡量源编码效果的最直观指标，通常表示原始数据与压缩后数据大小之比。压缩率越高，说明压缩效果越明显，但仍需结合失真程度与复杂度综合判断。
7.2 编码复杂度
编码复杂度反映算法在时间和空间上的实现成本。复杂度过高可能影响实时性，尤其在大规模数据流或嵌入式设备中更为明显。
7.3 解码延迟
解码延迟是数据从接收或读取到恢复可用状态所经历的时间。某些编码方法虽然压缩率较好，但解码过程较慢，可能不适合对响应速度要求较高的场景。
7.4 鲁棒性与容错性
源编码系统需要考虑在数据损坏、丢包或同步失配情况下的表现。鲁棒性较强的编码方式更能适应复杂传输环境，而容错性则关系到局部错误是否会扩散并影响整体恢复。
8 相关概念
8.1 信道编码
信道编码关注在噪声和干扰存在时如何可靠传输信息，主要目标是纠错和抗干扰。它与源编码方向不同：前者提升可靠性，后者提高压缩效率。
8.2 联合源信道编码
联合源信道编码将压缩与抗错设计结合起来，试图在带宽受限和信道不稳定的条件下取得整体最优效果。它适用于需要同时考虑码率和可靠性的通信场景。
8.3 数据压缩
数据压缩是比源编码更宽泛的概念，既包括无损压缩，也包括有损压缩。源编码通常被视为数据压缩中的理论基础与核心组成部分。
8.4 冗余与信息密度
冗余指数据中可被替代或预测的部分，而信息密度则描述单位比特所承载的有效信息量。源编码的本质，就是尽量减少冗余并提高信息密度，使表示更接近数据的真实信息结构。