Lossless and Lossy Data Compression

无损压缩和有损压缩

核心定义

• 无损压缩：压缩后能 100% 还原原始数据，无任何信息丢失，适用于对准确性要求极高的场景（如文本、程序文件）。
• 有损压缩：通过丢弃次要信息减少数据量，还原后与原始数据有差异，但人眼 / 耳难以感知，适用于多媒体（如图片、音频）。

无损压缩

文本压缩仅能用无损压缩（否则会导致文字错乱、语义丢失），核心是 "用更短的编码替代重复 / 高频信息"，常见两种思路：

LZW 算法

LZW 算法是无损字典编码的核心，核心逻辑是 "动态建字典 + 用短编码替代重复字符串"，无需提前统计字符频率，压缩和解压共用同一套字典构建规则，效率高且易实现。

一、LZW 算法核心步骤（以文本压缩为例）

1. 初始化字典（基础字符集）

先将文本中所有不重复的单个字符加入字典，分配唯一的短编码（通常是整数）。

例：文本 "TOBEORNOTTOBEORTOBEORNOT"，基础字符集是 {T,O,B,E,R,N}，初始化字典：

字符	T	O	B	E	R	N
编码	0	1	2	3	4	5

2. 动态扩展字典（压缩核心）

遍历文本，不断寻找 "当前字符 + 下一个字符" 组成的新字符串，若不在字典中则添加，并用已有编码替代重复字符串。

步骤拆解（简化版）：

• 取第一个字符 "T"（编码 0），下一个字符 "O"，组合 "TO" 不在字典→添加字典（编码 6），输出 "T" 的编码 0；
• 接着取 "O"（编码 1），下一个字符 "B"，组合 "OB" 不在字典→添加字典（编码 7），输出 "O" 的编码 1；
• 取 "B"（编码 2），下一个字符 "E"，组合 "BE" 不在字典→添加字典（编码 8），输出 "B" 的编码 2；
• 取 "E"（编码 3），下一个字符 "O"，组合 "EO" 不在字典→添加字典（编码 9），输出 "E" 的编码 3；
• 当遇到重复字符串（如后续的 "TO"），直接输出其编码 6，无需重复存储字符。

3. 输出压缩结果

最终输出的是一串短整数编码（替代原始字符串），数据量大幅减少。

例：上述文本压缩后，输出编码序列可能是：0,1,2,3,4,1,5,0,6,4,1,8,3,1,...

4. 解压过程（反向还原）

解压时用相同的初始化字典，根据编码反向查找字典，同时还原动态扩展的过程。

例：收到编码 0→查字典得 "T"，编码 1→"O"，编码 6→"TO"，依次拼接，最终完全还原原始文本。

二、LZW 算法的关键优势（适合文本压缩）

• 无损还原：字典构建和编码过程可逆，解压后与原文完全一致，不会丢失字符或语义；
• 自适应：无需提前分析文本，动态扩展字典，对重复率高的文本（如小说、代码、文档）压缩率极高（可达 30%-70%）；
• 效率高：编码和解码仅需遍历文本 1-2 次，计算开销小，是 ZIP、GIF 等格式的核心压缩算法。

例：文本 "abracadabra" 中，"abra" 重复 2 次、"a" 出现 5 次，构建字典后，用 "0" 代 "abra"、"1" 代 "a"，原文本可从 11 个字符压缩为更短的编码组合。

三、LZW 算法的优点

• 文本的核心冗余是 "重复字符串" 而非 "连续重复字符"：普通文本中，连续重复的单个字符（如 "AAAA"）很少见，更多是重复的单词、短语（如 "的""和""hello""if"），LZW 能动态捕捉这些多字符重复片段。
• LZW 自适应能力更强：无需提前分析文本，动态构建字典，无论文本重复模式如何（单字符、多字符、连续 / 非连续），都能有效压缩。
• 实际应用场景：用 LZW 压缩小说、论文、代码文件（如 .txt、.py），压缩率稳定且高效。

游程编码（RLE）

游程编码（RLE）是最基础的无损压缩算法，核心逻辑是 "用'重复字符 + 重复次数'替代连续重复的序列"，原理简单、计算开销极低，适合处理重复率高的数据（如文本、位图、日志）。

一、核心原理（文本压缩场景）

当文本中出现连续重复的相同字符时，用 "字符 + 重复次数" 的组合替代原序列，减少数据量。

核心规则：非连续重复字符不压缩（或按 "字符 + 1" 表示），仅处理连续重复片段。

二、文本压缩示例（直观易懂）

原始文本：AAABBBCCCCDDDEEE（连续重复字符密集）

压缩过程：

• AAA → A3（A 连续出现 3 次）
• BBB → B3（B 连续出现 3 次）
• CCCC → C4（C 连续出现 4 次）
• DDD → D3（D 连续出现 3 次）
• EEE → E3（E 连续出现 3 次）

压缩后结果：A3B3C4D3E3（原 20 个字符→10 个字符，压缩率 50%）

三、特殊情况（无连续重复的文本）

若文本无连续重复字符（如 ABCDEFG），压缩后为 A1B1C1D1E1F1G1，反而比原文更长，因此 RLE 仅适用于重复率高的场景（如纯文本小说中的换行符、连续空格，或代码中的重复注释符号）。

四、实际应用（不止文本）

除了文本，RLE 还常用于：

• 位图压缩（如 BMP 格式）：连续相同颜色的像素用 "颜色值 + 像素数" 表示；
• 日志文件压缩：连续重复的日志字段（如时间戳、固定前缀）快速压缩。

哈夫曼编码

哈夫曼编码（Huffman Coding）是无损压缩的经典算法，核心是 "给高频字符分配短编码、低频字符分配长编码"，通过 "前缀不重叠" 保证无歧义解码，压缩效率高且实现简单，是文本、文件压缩的核心算法之一（如 GZIP、PNG 的辅助压缩）。

一、核心原理（3 个关键逻辑）

• 频率优先：统计文本中每个字符的出现频率，频率越高，编码越短（减少总编码长度）；
• 前缀编码：任何字符的编码都不是其他字符编码的前缀（如 "A"→0，"B"→01 是无效的，因为 "0" 是 "01" 的前缀，会导致解码歧义）；
• 二叉树构建：通过 "合并频率最低的节点" 构建哈夫曼树，编码由树的 "左枝 = 0、右枝 = 1" 生成（或反之）。

二、动画原理讲解

LZW 算法、游程编码和霍夫曼编码的对比

这三种都是经典无损压缩算法，核心差异集中在压缩原理、适用数据特征、压缩效率上，LZW 通用性最强（文本首选），哈夫曼编码压缩率稳定，游程编码仅适合高连续重复数据。

一、核心维度对比表

对比维度	LZW 算法	游程编码（RLE）	哈夫曼编码（Huffman）
核心原理	动态构建字典，用短编码替代重复字符串（单字符 / 多字符）	用 "字符 + 连续重复次数" 替代连续重复的单个字符	按字符频率分配可变长前缀编码（高频短、低频长）
适用数据特征	重复字符串多（如小说、代码、文档），无需连续重复	连续重复单字符密集（如空格、重复符号、位图）	字符频率差异大的任意数据（文本、文件）
压缩率（文本场景）	高（30%-70%），重复字符串越多效果越好	极低（仅连续重复时有效，无连续重复则 "膨胀"）	中高（30%-60%），频率差异越大效果越好
预处理要求	无（动态建字典，无需提前统计）	无（直接遍历连续字符）	有（需提前统计所有字符频率，生成编码表）
编码 / 解码复杂度	中等（动态维护字典，遍历 1-2 次）	极低（仅遍历 1 次，无复杂计算）	中等（构建哈夫曼树 + 遍历编码，解码需依赖编码表）
关键优势	通用性强、自适应数据、无预处理成本	原理简单、计算开销小、解码速度快	压缩率稳定、无数据膨胀风险、实现成熟
关键劣势	小文件可能因字典开销导致压缩率下降	通用性极差，非连续重复数据失效	需额外存储编码表（小文件 overhead 明显）
典型应用	ZIP 压缩、GIF 格式、文本 / 代码压缩	BMP 位图、日志文件、连续重复符号数据	GZIP、PNG 辅助压缩、文本 / 文件压缩

有损压缩

有损压缩核心是丢弃 "人眼 / 耳难以感知的次要信息"，常见例子集中在多媒体领域，以下是最贴近日常的场景：

一、图片压缩（最常用）

• JPEG/JPG：主流图片格式，通过丢弃高频色彩细节（如细微纹理、相近色调）压缩，适合照片、海报，压缩率可达 10:1~50:1，肉眼基本看不出差异。
• WebP：比 JPEG 压缩率更高（同等质量下体积小 30%），同样丢弃次要色彩信息，广泛用于网页、APP 图标。

注意：PNG 是无损压缩，注意区分！

二、音频压缩

• MP3：经典音频格式，丢弃人耳听不到的高频 / 低频声音，压缩后体积仅为原始 WAV 格式的 1/10，是音乐、语音的主流存储格式。
• AAC：比 MP3 音质更好、压缩效率更高，常用于 iPhone 铃声、流媒体音乐（如 Spotify）。

注意：WAV 是无损压缩，FLAC 是无损压缩，注意区分！

三、视频压缩

• H.264/AVC：主流视频编码，通过丢弃画面细节、优化帧间冗余（如重复背景）压缩，是电影、短视频（抖音 / 快手）的核心格式，1 小时视频可压缩至几百 MB。
• H.265/HEVC：比 H.264 压缩率高 50%，同等画质下体积更小，常用于 4K 视频、蓝光电影。

注意：MKV、MP4 是容器格式，内部多采用有损编码！

四、其他场景

• 语音通话（如微信语音、手机通话）：自动丢弃冗余语音频段，仅保留能听清的核心语音信息，减少传输带宽。
• 卫星图像 / 医疗影像（特殊有损）：在不影响关键分析的前提下，丢弃次要像素信息，方便存储和传输。

练习题

练习题 1（基础入门：5 个字符，频率简单）

题目

给定文本 "AABBBCDD"，完成以下任务：

1. 统计各字符出现频率
2. 构建哈夫曼树（按 "每次合并频率最小的两个节点" 规则）
3. 生成哈夫曼编码表
4. 将原文压缩为编码序列（合并后）

练习题 2（进阶：含频率相同节点，编码唯一性）

题目

给定字符及频率：X(4)、Y(2)、Z(2)、W(1)，回答以下问题：

1. 构建哈夫曼树（频率相同节点可任意合并，需体现编码前缀不重叠）
2. 生成编码表（允许因合并顺序不同产生不同编码，但需符合规则）
3. 验证编码是否满足 "前缀编码" 要求

练习题 3（实战：文本压缩与解压还原）

题目

已知哈夫曼编码表如下，现有压缩编码 "1001101011110"，请还原原始文本：

字符	甲	乙	丙	丁
编码	10	0	110	111