1 Basic Techniques 17
1.1 Intuitive Compression 17
1.2 Run-Length Encoding 22
1.3 RLE Text Compression 23
1.4 RLE Image Compression 27
1.5 Move-to-Front Coding 37
1.6 Scalar Quantization 40
1.7 Recursive Range Reduction 42
2 Statistical Methods 47
2.1 Information Theory Concepts 48
2.2 Variable-Size Codes 54
2.3 Prefix Codes 55
2.4 Tunstall Code 61
2.5 The Golomb Code 63
2.6 The Kraft-MacMillan Inequality 71
2.7 Shannon-Fano Coding 72
2.8 Huffman Coding 74
2.9 Adaptive Huffman Coding 89
2.10 MNP5 95
2.11 MNP7 100
2.12 Reliability 101
2.13 Facsimile Compression 104
2.14 Arithmetic Coding 112
xxii Contents
2.15 Adaptive Arithmetic Coding 125
2.16 The QM Coder 129
2.17 Text Compression 139
2.18 PPM 139
2.19 Context-Tree Weighting 161
3 Dictionary Methods 171
3.1 String Compression 173
3.2 Simple Dictionary Compression 174
3.3 LZ77 (Sliding Window) 176
3.4 LZSS 179
3.5 Repetition Times 182
3.6 QIC-122 184
3.7 LZX 187
3.8 LZ78 189
3.9 LZFG 192
3.10 LZRW1 195
3.11 LZRW4 198
3.12 LZW 199
3.13 LZMW 209
3.14 LZAP 212
3.15 LZY 213
3.16 LZP 214
3.17 Repetition Finder 221
3.18 UNIX Compression 224
3.19 GIF Images 225
3.20 RAR and WinRAR 226
3.21 The V.42bis Protocol 228
3.22 Various LZ Applications 229
3.23 Deflate: Zip and Gzip 230
3.24 LZMA and 7-Zip 241
3.25 PNG 246
3.26 XML Compression: XMill 251
3.27 EXE Compressors 253
3.28 CRC 254
3.29 Summary 256
3.30 Data Compression Patents 256
3.31 A Unification 259
Contents xxiii
4 Image Compression 263
4.1 Introduction 265
4.2 Approaches to Image Compression 270
4.3 Intuitive Methods 283
4.4 Image Transforms 284
4.5 Orthogonal Transforms 289
4.6 The Discrete Cosine Transform 298
4.7 Test Images 333
4.8 JPEG 337
4.9 JPEG-LS 354
4.10 Progressive Image Compression 360
4.11 JBIG 369
4.12 JBIG2 378
4.13 Simple Images: EIDAC 389
4.14 Vector Quantization 390
4.15 Adaptive Vector Quantization 398
4.16 Block Matching 403
4.17 Block Truncation Coding 406
4.18 Context-Based Methods 412
4.19 FELICS 415
4.20 Progressive FELICS 417
4.21 MLP 422
4.22 Adaptive Golomb 436
4.23 PPPM 438
4.24 CALIC 439
4.25 Differential Lossless Compression 442
4.26 DPCM 444
4.27 Context-Tree Weighting 449
4.28 Block Decomposition 450
4.29 Binary Tree Predictive Coding 454
4.30 Quadtrees 461
4.31 Quadrisection 478
4.32 Space-Filling Curves 485
4.33 Hilbert Scan and VQ 487
4.34 Finite Automata Methods 497
4.35 Iterated Function Systems 513
4.36 Cell Encoding 529
xxiv Contents
5 Wavelet Methods 531
5.1 Fourier Transform 532
5.2 The Frequency Domain 534
5.3 The Uncertainty Principle 538
5.4 Fourier Image Compression 540
5.5 The CWT and Its Inverse 543
5.6 The Haar Transform 549
5.7 Filter Banks 566
5.8 The DWT 576
5.9 Multiresolution Decomposition 589
5.10 Various Image Decompositions 589
5.11 The Lifting Scheme 596
5.12 The IWT 608
5.13 The Laplacian Pyramid 610
5.14 SPIHT 614
5.15 CREW 626
5.16 EZW 626
5.17 DjVu 630
5.18 WSQ, Fingerprint Compression 633
5.19 JPEG 2000 639
6 Video Compression 653
6.1 Analog Video 653
6.2 Composite and Components Video 658
6.3 Digital Video 660
6.4 Video Compression 664
6.5 MPEG 676
6.6 MPEG-4 698
6.7 H.261 703
6.8 H.264 706
7 Audio Compression 719
7.1 Sound 720
7.2 Digital Audio 724
7.3 The Human Auditory System 727
7.4 WAVE Audio Format 734
7.5 μ-Law and A-Law Companding 737
7.6 ADPCM Audio Compression 742
7.7 MLP Audio 744
7.8 Speech Compression 750
7.9 Shorten 757
7.10 FLAC 762
7.11 WavPack 772
7.12 Monkey’s Audio 783
7.13 MPEG-4 Audio Lossless Coding (ALS) 784
7.14 MPEG-1/2 Audio Layers 795
7.15 Advanced Audio Coding (AAC) 821
7.16 Dolby AC-3 847
Contents xxv
8 Other Methods 851
8.1 The Burrows-Wheeler Method 853
8.2 Symbol Ranking 858
8.3 ACB 862
8.4 Sort-Based Context Similarity 868
8.5 Sparse Strings 874
8.6 Word-Based Text Compression 885
8.7 Textual Image Compression 888
8.8 Dynamic Markov Coding 895
8.9 FHM Curve Compression 903
8.10 Sequitur 906
8.11 Triangle Mesh Compression: Edgebreaker 911
8.12 SCSU: Unicode Compression 922
8.13 Portable Document Format (PDF) 928
8.14 File Differencing 930
8.15 Hyperspectral Data Compression 941
Answers to Exercises 953
Bibliography 1019
Glossary 1041
Joining the Data Compression Community 1067
Index 1069
本书《Data Compression: The Complete Reference, Fourth Edition》为数据压缩领域的权威参考资料,涵盖了数据压缩的基础理论与实践应用。作者David Salomon与合作者Giovanni Motta和David Bryant共同编写,适用于计算机科学家、工程师以及对数据压缩技术感兴趣的读者。
### 1. 基础技术
#### 1.1 直观压缩(Intuitive Compression)
介绍了数据压缩的基本概念,解释了如何通过数据结构简化来减少数据量。
#### 1.2 逐行编码(Run-Length Encoding, RLE)
详细阐述了RLE的原理和应用,特别是在文本和图像数据压缩中的作用。
#### 1.3 文本压缩(RLE Text Compression)
文本压缩利用RLE原理,通过统计文本中连续出现的字符来压缩文本数据。
#### 1.4 图像压缩(RLE Image Compression)
图像压缩利用RLE原理,通过统计图像中连续颜色或像素值来压缩图像数据。
#### 1.5 移动至前端编码(Move-to-Front Coding)
一种变换编码技术,通过将输入数据中重复出现的元素移至数据流的前端来提高压缩率。
#### 1.6 标量量化(Scalar Quantization)
将连续信号转换为离散信号的过程,以减少数据量。
#### 1.7 递归范围缩减(Recursive Range Reduction)
一种动态调整量化范围的方法,用于进一步减小数据量。
### 2. 统计方法
#### 2.1 信息论概念(Information Theory Concepts)
介绍了信息论的基本原理,包括信息熵、互信息等核心概念。
#### 2.2 变长编码(Variable-Size Codes)
变长编码通过为不同长度的符号分配不同大小的编码来减少数据量。
#### 2.3 前缀编码(Prefix Codes)
前缀编码是变长编码的一种,其中没有码字是其他码字的前缀。
#### 2.4 Tunstall编码
一种基于统计模型的最优前缀编码算法。
#### 2.5 Golomb编码(The Golomb Code)
一种用于算术编码的技巧,特别适用于几何分布的数据。
#### 2.6 Kraft-MacMillan不等式(The Kraft-MacMillan Inequality)
用于验证前缀码是否有效的数学不等式。
#### 2.7 Shannon-Fano编码(Shannon-Fano Coding)
一种基于字符概率分布构建最优前缀编码的方法。
#### 2.8 Huffman编码(Huffman Coding)
一种广泛使用的最优前缀编码技术,通过构建哈夫曼树来实现压缩。
#### 2.9 自适应Huffman编码(Adaptive Huffman Coding)
Huffman编码的一种变体,可以动态地适应数据的变化。
#### 2.10 MNP5和MNP7
MNP5和MNP7是用于调制解调器的数据压缩协议。
#### 2.11 可靠性(Reliability)
在压缩过程中确保数据完整性的方法。
#### 2.12 传真压缩(Facsimile Compression)
传真数据压缩的特定方法。
#### 2.13 算术编码(Arithmetic Coding)
一种高效的数据压缩技术,通过使用实数来表示数据序列。
#### 2.14 自适应算术编码(Adaptive Arithmetic Coding)
算术编码的自适应版本,可动态调整模型以适应数据变化。
#### 2.15 QM编码器(The QM Coder)
IBM开发的一种用于图像压缩的算术编码方法。
#### 2.16 文本压缩(Text Compression)
利用统计模型和语言特性来压缩文本数据。
#### 2.17 PPM(Prediction by Partial Matching)
一种预测编码方法,用于文本和数据压缩。
#### 2.18 上下文树加权(Context-Tree Weighting)
一种用于压缩数据的上下文模型技术。
### 3. 字典方法
#### 3.1 字符串压缩(String Compression)
介绍了基本的字符串压缩方法和理论。
#### 3.2 简单字典压缩(Simple Dictionary Compression)
通过替换频繁出现的字符串来减少数据量。
#### 3.3 LZ77(滑动窗口)
LZ77压缩算法的描述,是一种基于字典的压缩方法。
#### 3.4 LZSS
LZSS是LZ77的改进版本,更有效地使用字典。
#### 3.5 重复时间(Repetition Times)
描述了如何编码重复出现的序列。
#### 3.6 QIC-122
一种用于磁带驱动器的压缩算法。
#### 3.7 LZX
一种用于Microsoft CAB文件的压缩算法。
#### 3.8 LZ78
LZ78压缩算法的原理和应用。
#### 3.9 LZFG
LZFG是一种流式压缩算法,适合于动态数据。
#### 3.10 LZRW1 和 LZRW4
这两种是LZ77的变体,主要用于内存数据压缩。
#### 3.11 LZW
LZW压缩算法广泛应用于多种压缩标准,如GIF和TIFF。
#### 3.12 LZMW
LZMW是一种在微处理器上实现的高效字典编码方法。
#### 3.13 LZAP
LZAP是LZW的改进版本,具有更好的压缩效率。
#### 3.14 LZY
LZY是一种用于文本压缩的高效算法。
#### 3.15 LZP
LZP结合了预测编码和字典编码。
#### 3.16 Repetition Finder
用于识别重复数据序列的技术。
#### 3.17 UNIX压缩(UNIX Compression)
UNIX系统下常用的数据压缩工具。
#### 3.18 GIF图像(GIF Images)
GIF图像格式使用LZW压缩算法。
#### 3.19 RAR和WinRAR
RAR和WinRAR是广泛使用的文件压缩工具。
#### 3.20 V.42bis协议
V.42bis是一种调制解调器使用的压缩协议。
#### 3.21 各种LZ应用(Various LZ Applications)
介绍了LZ系列算法在不同领域的应用案例。
#### 3.22 压缩解压缩(Deflate: Zip and Gzip)
介绍了ZIP和GZIP格式,它们使用了DEFLATE压缩算法。
#### 3.23 LZMA和7-Zip
LZMA是一种高效压缩算法,7-Zip是使用LZMA算法的文件压缩工具。
#### 3.24 PNG
PNG格式使用了多种压缩方法,包括LZ77的变体。
#### 3.25 XML压缩(XML Compression: XMill)
一种针对XML文档的数据压缩方法。
#### 3.26 EXE压缩器(EXE Compressors)
专门用于压缩可执行文件的工具。
#### 3.27 CRC(CRC)
循环冗余校验,用于错误检测和数据完整性验证。
#### 3.28 摘要(Summary)
对上述内容的简要总结。
#### 3.29 数据压缩专利(Data Compression Patents)
介绍了数据压缩领域相关的专利信息。
#### 3.30 统一化(A Unification)
对不同数据压缩技术的整合和比较。
### 4. 图像压缩
#### 4.1 引言(Introduction)
阐述图像压缩的基本概念和重要性。
#### 4.2 图像压缩方法(Approaches to Image Compression)
对图像压缩技术进行分类和介绍。
#### 4.3 直观方法(Intuitive Methods)
介绍直观方法在图像压缩中的应用。
#### 4.4 图像变换(Image Transforms)
介绍了将图像从空间域转换到变换域的过程。
#### 4.5 正交变换(Orthogonal Transforms)
正交变换在图像压缩中的应用和原理。
#### 4.6 离散余弦变换(The Discrete Cosine Transform, DCT)
DCT是JPEG图像压缩标准的核心技术。
#### 4.7 测试图像(Test Images)
用于评估图像压缩算法性能的标准图像集。
#### 4.8 JPEG
JPEG是广泛使用的图像压缩标准。
#### 4.9 JPEG-LS
JPEG-LS是JPEG的无损压缩版本。
#### 4.10 渐进式图像压缩(Progressive Image Compression)
渐进式压缩允许图像以逐渐提高的质量被传输。
#### 4.11 JBIG
JBIG是一种用于黑白图像的压缩标准。
#### 4.12 JBIG2
JBIG2是JBIG的后继标准,用于压缩扫描文档。
#### 4.13 简单图像(Simple Images: EIDAC)
介绍EIDAC格式,一种用于高效图像表示的格式。
#### 4.14 矢量量化(Vector Quantization)
将图像像素块映射到最接近的码本矢量。
#### 4.15 自适应矢量量化(Adaptive Vector Quantization)
矢量量化的一种变体,可以根据图像内容自适应调整量化策略。
#### 4.16 块匹配(Block Matching)
块匹配用于块编码技术,通过在图像中寻找最匹配的块来减少数据量。
#### 4.17 块截断编码(Block Truncation Coding)
一种用于图像压缩的简化技术,通过使用较少的比特来表示图像块。
#### 4.18 基于上下文的方法(Context-Based Methods)
介绍基于图像内容上下文的压缩方法。
#### 4.19 FELICS
FELICS是一种用于图像压缩的快速编码算法。
#### 4.20 渐进式FELICS
FELICS的改进版本,支持渐进式图像传输。
#### 4.21 MLP
MLP(多层感知器)用于图像压缩中的预测建模。
#### 4.22 自适应Golomb
一种动态调整参数以适应图像内容的压缩方法。
#### 4.23 PPPM
PPPM是一种结合了预测和上下文模型的图像压缩方法。
#### 4.24 CALIC
CALIC是一种用于图像压缩的上下文自适应算术编码方法。
#### 4.25 差分无损压缩(Differential Lossless Compression)
通过差分编码提高无损压缩的效率。
#### 4.26 DPCM
DPCM(差分脉冲编码调制)是图像压缩中常用的一种技术。
#### 4.27 上下文树加权(Context-Tree Weighting)
用于图像压缩的上下文模型技术。
#### 4.28 块分解(Block Decomposition)
通过将图像分解成小块来简化图像压缩过程。
#### 4.29 二叉树预测编码(Binary Tree Predictive Coding)
使用二叉树结构对图像进行预测编码。
#### 4.30 四叉树(Quadtrees)
四叉树用于图像分割和表示。
#### 4.31 四分法(Quadrisection)
一种将图像分成四个相等部分的方法。
#### 4.32 空间填充曲线(Space-Filling Curves)
空间填充曲线用于图像的多维数据表示。
#### 4.33 Hilbert扫描和向量量化(Hilbert Scan and VQ)
Hilbert扫描用于图像的线性表示,向量量化用于减少Hilbert扫描后的数据量。
#### 4.34 有限自动机方法(Finite Automata Methods)
介绍有限自动机在图像压缩中的应用。
#### 4.35 迭代函数系统(Iterated Function Systems)
用于图像压缩的数学模型。
#### 4.** 单元编码(Cell Encoding)
一种基于单元编码技术的图像压缩方法。
### 5. 小波方法
#### 5.1 傅里叶变换(Fourier Transform)
介绍傅里叶变换在图像压缩中的应用。
#### 5.2 频域(The Frequency Domain)
解释频率域的概念及其在图像压缩中的作用。
#### 5.3 不确定性原理(The Uncertainty Principle)
介绍不确定性原理及其对图像压缩的影响。
#### 5.4 傅里叶图像压缩(Fourier Image Compression)
讨论傅里叶变换在图像压缩中的具体应用。
#### 5.5 CWT及其逆变换(The CWT and Its Inverse)
介绍连续小波变换及其逆变换。
#### 5.6 Haar变换(The Haar Transform)
Haar变换是一种简单的小波变换。
#### 5.7 滤波器组(Filter Banks)
滤波器组用于信号的分解和重构。
#### 5.8 离散小波变换(The DWT)
离散小波变换是图像压缩中一种有效的时频分析工具。
#### 5.9 多分辨率分解(Multiresolution Decomposition)
多分辨率分解是小波变换的进一步发展。
#### 5.10 各种图像分解(Various Image Decompositions)
介绍了小波变换中不同的图像分解方法。
#### 5.11 提升方案(The Lifting Scheme)
提升方案是构造第二代小波变换的一种方法。
#### 5.12 整数小波变换(The IWT)
整数小波变换将小波变换结果量化为整数,以简化计算。
#### 5.13 Laplacian金字塔(The Laplacian Pyramid)
Laplacian金字塔在图像压缩和图像处理中具有多种应用。
#### 5.14 SPIHT
SPIHT(Set Partitioning in Hierarchical Trees)是一种高效的小波图像压缩算法。
#### 5.15 CREW
CREW(Compression with Reversible Embedded Wavelets)是一种可逆的小波压缩方案。
#### 5.16 EZW
EZW(Embedded Zerotree Wavelet)是一种用于小波编码的嵌入式方法。
#### 5.17 DjVu
DjVu是一种用于文档图像压缩的格式。
#### 5.18 WSQ, 指纹压缩(WSQ, Fingerprint Compression)
WSQ是一种用于指纹图像压缩的小波编码方法。
#### 5.19 JPEG 2000
JPEG 2000是基于小波变换的图像压缩标准。
### 6. 视频压缩
#### 6.1 模拟视频(Analog Video)
介绍了模拟视频信号的基本概念。
#### 6.2 复合和分量视频(Composite and Components Video)
介绍了复合视频和分量视频的区别和应用。
#### 6.3 数字视频(Digital Video)
介绍了数字视频信号及其压缩技术。
#### 6.4 视频压缩(Video Compression)
探讨了视频数据压缩的必要性和挑战。
#### 6.5 MPEG
MPEG是广泛使用的视频压缩标准系列。
#### 6.6 MPEG-4
MPEG-4视频压缩标准特别适用于网络视频传输。
#### 6.7 H.261
H.261是早期用于视频会议的视频压缩标准。
#### 6.8 H.264
H.264是目前非常流行的高效视频压缩标准。
### 7. 音频压缩
#### 7.1 声音(Sound)
介绍了声音信号的基本概念。
#### 7.2 数字音频(Digital Audio)
解释了音频信号如何数字化并用于压缩。
#### 7.3 人耳听觉系统(The Human Auditory System)
介绍了人耳的听觉特性,这些特性被用于音频压缩。
#### 7.4 WAVE音频格式(WAVE Audio Format)
WAVE是Windows平台广泛支持的音频文件格式。
#### 7.5 μ-法则和A-法则压缩扩展(μ-Law and A-Law Companding)
介绍了音频信号在电话系统中使用的压缩扩展。
#### 7.6 ADPCM音频压缩(ADPCM Audio Compression)
ADPCM是一种音频信号的差分脉冲编码调制技术。
#### 7.7 MLP音频(MLP Audio)
MLP是多声道线性预测音频压缩技术。
#### 7.8 语音压缩(Speech Compression)
介绍了语音信号的压缩技术。
#### 7.9 Shorten
Shorten是一种开源的音频压缩工具。
#### 7.10 FLAC
FLAC是一种无损音频压缩格式。
#### 7.11 WavPack
WavPack是另一种无损音频压缩方案。
#### 7.12 Monkey’s Audio
Monkey’s Audio是一种流行的无损音频压缩软件。
#### 7.13 MPEG-4音频无损编码(MPEG-4 Audio Lossless Coding, ALS)
ALS是MPEG-4标准中用于音频无损压缩的部分。
#### 7.14 MPEG-1/2音频层(MPEG-1/2 Audio Layers)
MPEG-1/2音频层是早期MPEG音频压缩标准。
#### 7.15 高级音频编码(Advanced Audio Coding, AAC)
AAC是MPEG-4音频编码标准的后继者,提供了更好的音频质量。
#### 7.16 Dolby AC-3
Dolby AC-3是一种广泛用于电影和家庭影院的音频编码格式。
### 8. 其他方法
#### 8.1 Burrows-Wheeler方法(The Burrows-Wheeler Method)
介绍了Burrows-Wheeler变换,一种数据压缩技术。
#### 8.2 符号排序(Symbol Ranking)
符号排序是一种用于数据压缩的排序技术。
#### 8.3 ACB
ACB(Arithmetic Coding and Burrows-Wheeler Transform)结合了算术编码和Burrows-Wheeler变换。
#### 8.4 基于排序的上下文相似性(Sort-Based Context Similarity)
介绍了如何通过排序来发现数据中的相似性。
#### 8.5 稀疏字符串(Sparse Strings)
稀疏字符串技术用于压缩稀疏数据。
#### 8.6 基于单词的文本压缩(Word-Based Text Compression)
一种文本压缩方法,利用单词的重复性进行压缩。
#### 8.7 文字图像压缩(Textual Image Compression)
对文字图像进行压缩的方法。
#### 8.8 动态马尔可夫编码(Dynamic Markov Coding)
动态马尔可夫编码是一种统计模型压缩方法。
#### 8.9 FHM曲线压缩(FHM Curve Compression)
FHM曲线用于减少曲线数据的表示复杂性。
#### 8.10 Sequitur
Sequitur是一种上下文无关文法的压缩技术。
#### 8.11 三角形网格压缩(Triangle Mesh Compression: Edgebreaker)
介绍了一种高效的三维模型压缩方法。
#### 8.12 SCSU: Unicode压缩(SCSU: Unicode Compression)
SCSU是一种用于Unicode文本的压缩技术。
#### 8.13 便携式文档格式(Portable Document Format, PDF)
介绍了PDF文档的压缩技术。
#### 8.14 文件差异(File Differencing)
文件差异技术用于创建文件的更新版本。
#### 8.15 超光谱数据压缩(Hyperspectral Data Compression)
介绍了超光谱数据的压缩方法。
### 附录
#### 答案(Answers to Exercises)
包含了书中练习题的答案,便于读者学习和检查。
#### 参考文献(Bibliography)
列出了编写书籍时参考的文献。
#### 术语表(Glossary)
提供了书中所用专业术语的定义和解释。
#### 加入数据压缩社区(Joining the Data Compression Community)
提供了加入数据压缩领域相关组织的信息。
#### 索引(Index)
详细的索引部分,方便读者查找书中内容。
本书提供了大量关于数据压缩技术的理论知识和实践应用,是数据压缩领域的专业参考书籍。通过阅读本书,读者可以全面了解数据压缩的概念、方法和应用,掌握相关的技术知识,并能够应用这些技术解决实际问题。
1