萨尤得编著的《数据压缩导论(第4版)》是“图灵计算机科学丛书”之一。本书共19章节，内容包括引言、无损压缩的数学预备知识、霍夫曼编码、算术编码、词典方法、基于上下文的压缩、无损图像压缩、有损编码的数学预备知识、标量量化、矢量量化、差分编码等。本书非常适合从事数据压缩相关工作的专业技术人员、软硬件工程师、学生等阅读。

萨尤得编著的《数据压缩导论（第4版）》是数据压缩方面的经典著作，目前已经出到了第4版。数据压缩技术及其应用从未停止前进的步伐，图像、语音、文本、音频、视频等新的应用领域层出不穷。《数据压缩导论（第4版）》也与时俱进，不断更新，这一版基本涵盖了数据压缩领域的最新发展。书中首先介绍了基本压缩方法（包括无损压缩和有损压缩）涉及的数学知识，然后从无损压缩开始，依次讲述了霍夫曼编码、算术编码以及词典编码技术等。对于有损压缩，还描述了标量、矢量以及微分编码和分形压缩技术。《数据压缩导论（第4版）》在上一版的基础上，扩展讨论了基于小波的压缩技术，特别是越来越流行的JPEG2000标准，还增加了范式霍夫曼码以及更多有关二进制算术编码的信息。

《数据压缩导论（第4版）》非常适合从事数据压缩相关工作的专业技术人员、软硬件工程师、学生等阅读，数字图书馆、多媒体等领域的技术人员也可参考。

第1章　引言　1

1.1　压缩技术　3

 1.1.1　无损压缩　3

 1.1.2　有损压缩　4

 1.1.3　性能的测量　4

1.2　建模与编码　5

1.3　小结　8

1.4　项目与习题　8

第2章　无损压缩的数学预备知识　9

2.1　概述　9

2.2　信息论简介　9

2.3　模型　18

 2.3.1　物理模型　18

 2.3.2　概率模型　19

 2.3.3　马尔可夫模型　19

 2.3.4　复合信源模型　21

2.4　编码　22

 2.4.1　独特可译码　22

 2.4.2　前缀码　25

 2.4.3　Kraft-McMillan不等式★　25

2.5　算法信息论　28

2.6　最小描述长度原则　28

2.7　小结　29

2.8　项目与习题　30

第3章　霍夫曼编码　32

3.1　概述　32

3.2　霍夫曼编码算法　32

 3.2.1　最小方差霍夫曼码　35

 3.2.2　范式霍夫曼码　37

 3.2.3　有限长度的霍夫曼码　39

 3.2.4　霍夫曼码的最优性★　41

 3.2.5　霍夫曼码的长度★　42

 3.2.6　扩展霍夫曼码★　44

 3.2.7　霍夫曼码的实现　46

3.3　非二进制霍夫曼码★　49

3.4　自适应霍夫曼编码　51

 3.4.1　更新过程　52

 3.4.2　编码过程　54

 3.4.3　解码过程　56

3.5　Golomb码　57

3.6　Rice码　58

3.7　Tunstall码　60

3.8　霍夫曼编码的应用　62

 3.8.1　无损图像压缩　62

 3.8.2　文本压缩　63

 3.8.3　音频压缩　64

3.9　小结　65

3.10　项目与习题　66

第4章　算术编码　68

4.1　概述　68

4.2　引言　68

4.3　为一个序列编码　69

 4.3.1　生成标签　70

 4.3.2　解读标签　75

4.4　生成二进制码　77

 4.4.1　算术代码的独特性和效率　77

 4.4.2　算法实现　80

 4.4.3　整数实现　84

4.5　自适应算术编码　91

4.6　二进制算术编码　91

 4.6.1　QM编码器　95

 4.6.2　MQ编码器　95

 4.6.3　M编码器　96

4.7　霍夫曼编码与算术编码的对比　97

4.8　应用　99

4.9　小结　99

4.10　项目与习题　100

第5章　词典方法　102

5.1　概述　102

5.2　引言　102

5.3　静态词典　103

5.4　自适应词典　105

 5.4.1　LZ77方法　105

 5.4.2　LZ78方法　109

5.5　应用　114

 5.5.1　文件压缩——UNIX compress　115

 5.5.2　图像压缩——图形交换格式　115

 5.5.3　图像压缩——可移植网络图形　116

 5.5.4　调制解调器中的压缩——V. 42 bis　117

5.6　超越压缩——Lempel-Ziv复杂度★　118

5.7　小结　120

5.8　项目与习题　120

第6章　基于上下文的压缩　123

6.1　概述　123

6.2　引言　123

6.3　部分匹配预测　124

 6.3.1　基本算法　124

 6.3.2　转义符号　129

 6.3.3　上下文的长度　130

 6.3.4　排除原则　131

6.4　Burrows-Wheeler变换　131

6.5　Buyanovsky关联编码器(ACB)　135

6.6　动态马尔可夫压缩　136

6.7　小结　138

6.8　项目与习题　138

第7章　无损图像压缩　139

7.1　概述　139

7.2　引言　139

7.3　CALIC　141

7.4　JPEG-LS　144

7.5　使用条件平均值进行预测　146

7.6　多分辨率方法　147

7.7　传真编码　151

 7.7.1　游程长度编码　151

 7.7.2　CCITT第3组与第4组——建议T.4与T.6　152

 7.7.3　JBIG　154

 7.7.4　MH、MR、MMR和JBIG的对比　158

 7.7.5　JBIG2-T.88　159

7.8　MRC-T.44　160

7.9　小结　162

7.10　项目与习题　162

第8章　有损编码的数学预备知识　164

8.1　概述　164

8.2　引言　164

8.3　失真度标准　166

 8.3.1　人类视觉系统　168

 8.3.2　听觉　169

8.4　信息论回顾★　169

 8.4.1　条件熵　170

 8.4.2　平均互信息　171

 8.4.3　微分熵　172

8.5　率失真理论★　175

8.6　模型　181

 8.6.1　概率模型　181

 8.6.2　线性系统模型　183

 8.6.3　物理模型　187

8.7　小结　187

8.8　项目与习题　188

第9章　标量量化　189

9.1　概述　189

9.2　引言　189

9.3　量化问题　189

9.4　均匀量化器　193

9.5　自适应量化　201

 9.5.1　前向自适应量化　201

 9.2.5　后向自适应量化　203

9.6　非均匀量化　208

 9.6.1　pdf优化量化　209

 9.6.2　压扩量化　212

9.7　熵编码量化　217

 9.7.1　Lloyd-Max量化器输出的熵编码　217

 9.7.2　熵约束量化★　217

 9.7.3　高速率最优量化★　218

9.8　小结　221

9.9　项目与习题　221

第10章　矢量量化　223

10.1　概述　223

10.2　引言　223

10.3　矢量量化器相对于标量量化器的优势　225

 10.4　Linde-Buzo-Gray算法　229

 10.4.1　初始化LBG算法　233

 10.4.2　空单元格问题　237

 10.4.3　用LBG压缩图像　237

10.5　树状结构的矢量量化器　240

 10.5.1　树状结构矢量量化器的设计　243

 10.5.2　剪枝树状结构矢量量化器　244

10.6　结构化矢量量化器　244

 10.6.1　金字塔矢量量化　245

 10.6.2　极矢量量化器和球面矢量量化器　246

 10.6.3　格型矢量量化器　246

10.7　矢量量化的变体　250

 10.7.1　增益?形状矢量量化　250

 10.7.2　去均值矢量量化器　250

 10.7.3　分类矢量量化　251

 10.7.4　多级矢量量化　251

 10.7.5　自适应矢量量化　252

10.8　网格编码量化　253

10.9　小结　256

10.10　项目与习题　257

第11章　差分编码　259

11.1　概述　259

11.2　引言　259

11.3　基本算法　261

11.4　DPCM中的预测　264

11.5　自适应DPCM　268

 11.5.1　DPCM中的自适应量化　269

 11.5.2　DPCM中的自适应预测　269

11.6　增量调制　272

 11.6.1　常因子自适应增量调制(CFDM)　273

 11.6.2　连续可变斜率增量调制　274

11.7　语音编码　274

11.8　图像编码　277

11.9　小结　279

11.10　项目与习题　279

第12章　变换、子带与小波的数学预备知识　281

12.1　概述　281

12.2　引言　281

12.3　矢量空间　281

 12.3.1　点积或内积　282

 12.3.2　矢量空间　283

 12.3.3　子空间　284

 12.3.4　基　284

 12.3.5　内积的正式定义　285

 12.3.6　正交集与标准正交集　285

12.4　傅里叶级数　286

12.5　傅里叶变换　288

 12.5.1　帕伐瓦尔定理　289

 12.5.2　调制性质　290

 12.5.3　卷积定理　290

12.6　线性系统　290

 12.6.1　时不变　291

 12.6.2　传递函数　291

 12.6.3　冲激响应　292

 12.6.4　滤波器　293

12.7　采样　295

 12.7.1　理想采样——频域视角　295

 12.7.2　理想采样——时域视角　296

12.8　离散傅里叶变换　298

12.9　Z变换　299

 12.9.1　查表法　302

 12.9.2　部分分式展开　302

 12.9.3　长除　306

 12.9.4　Z变换的性质　306

 12.9.5　离散卷积　307

12.10　小结　308

12.11　项目与习题　308

第13章　变换编码　310

13.1　概述　310

13.2　引言　310

13.3　变换　313

13.4　所关心的变换　317

 13.4.1　Karhunen-Loéve变换　317

 13.4.2　离散余弦变换　318

 13.4.3　离散正弦变换　320

 13.4.4　离散Walsh-Hadamard变换　320

13.5　变换系数的量化与编码　321

13.6　在图像压缩中的应用——JPEG　327

 13.6.1　变换　327

 13.6.2　量化　328

 13.6.3　编码　329

 13.6.4　格式——JFIF　332

13.7　MDCT在音频压缩中的应用　334

13.8　小结　336

13.9　项目与习题　337

第14章　子带编码　339

14.1　概述　339

14.2　引言　339

14.3　滤波器　343

14.4　基本子带编码算法　348

 14.4.1　分析　349

 14.4.2　量化与编码　349

 14.4.3　合成　350

14.5　滤波器组设计★　350

 14.5.1　降采样★　351

 14.5.2　升采样★　353

14.6　使用两通道滤波器组的完美重构★　354

 14.6.1　两通道PR正交镜像滤波器★　357

 14.6.2　功率对称FIR滤波器★　359

14.7　M频带正交镜像滤波器组★　360

14.8　多相分解★　362

14.9　比特分配　366

14.10　在语音编码中的应用G. 722　368

14.11　在音频编码中的应用——MPEG音频　369

14.12　在图像压缩中的应用　369

 14.12.1　分解图像　371

 14.12.2　对子带进行编码　373

14.13　小结　374

14.14　项目与习题　375

第15章　小波　377

15.1　概述　377

15.2　引言　377

15.3　小波　379

15.4　多分辨率分析和尺度函数　383

15.5　用滤波器实现　388

 15.5.1　尺度变换与小波系数　390

 15.5.2　小波族　392

15.6　双正交小波　394

15.7　提升　397

15.8　小结　400

15.9　项目与习题　401

第16章　基于小波的图像压缩　402

16.1　概述　402

16.2　引言　402

16.3　嵌入式零树编码器　404

16.4　多级树集合分裂　410

16.5　JPEG 2000　415

 16.5.1　色彩分量变换　416

 16.5.2　分片　417

 16.5.3　小波变换　417

 16.5.4　量化　418

 16.5.5　第I层编码　419

 16.5.6　第II层编码　425

 16.5.7　JPEG 2000比特流　426

16.6　小结　430

16.7　项目与习题　430

第17章　音频编码　432

17.1　概述　432

17.2　引言　432

 17.2.1　频谱屏蔽　433

 17.2.2　时间屏蔽　434

 17.2.3　心理声学模型　434

17.3　MPEG音频编码　435

 17.3.1　第I层编码　435

 17.3.2　第II层编码　437

 17.3.3　第III编码——MP3　437

17.4　MPEG高级音频编码　440

 17.4.1　MPEG-2 AAC　441

 17.4.2　MPEG-4 AAC　444

17.5　Dolby AC-3(Dolby Digital)　445

17.6　其他标准　446

17.7　小结　447

第18章　分析/合成与合成分析方案　448

18.1　概述　448

18.2　引言　448

18.3　语音压缩　449

 18.3.1　信道声码器　450

 18.3.2　线性预测编码器(美国政府标准LPC-10)　451

 18.3.3　码激励线性预测(CELP)　457

 18.3.4　正弦编码器　459

 18.3.5　混合激励线性预测(MELP)　461

18.4　宽带语音压缩ITU-T G.722.2　463

18.5　互联网应用的语音编码　464

 18.5.1　iLBC　464

 18.5.2　G.729　468

 18.5.3　SILK　471

18.6　图像压缩　473

18.7　小结　478

18.8　项目与习题　479

第19章　视频压缩　480

19.1　概述　480

19.2　引言　480

19.3　运动补偿　481

19.4　视频信号表示　483

19.5　ITU-T建议书H.261　488

 19.5.1　运动补偿　488

 19.5.2　环路滤波器　489

 19.5.3　变换　490

 19.5.4　量化与编码　490

 19.5.5　速率控制　491

19.6　基于模型的编码　492

19.7　非对称应用　493

19.8　MPEG-1视频标准　494

19.9　MPEG-2视频标准H.262　496

19.10　ITU-T建议书H.263　498

 19.10.1　不受限运动矢量模式　500

 19.10.2　基于语法的算术编码模式　500

 19.10.3　高级预测模式　500

 19.10.4　PB帧模式和改进的PB帧模式　500

 19.10.5　先进的帧内编码模式　500

 19.10.6　块效应消除滤波模式　501

 19.10.7　参考图片选择模式　501

 19.10.8　时间、SNR和空间伸缩性模式　501

 19.10.9　参考图片重新采样　501

 19.10.10　降低分辨率的更新模式　501

 19.10.11　交替帧间变长编码模式　501

 19.10.12　改进量化模式　501

 19.10.13　增强型参考图片选择模式　502

19.11　ITU-T建议书H.264　502

 19.11.1　运动补偿预测　503

 19.11.2　变换　503

 19.11.3　帧间预测　504

 19.11.4　量化　504

 19.11.5　编码　506

19.12　MPEG-4第二部分　506

19.13　数据包视频　507

 19.13.1　ATM网络　508

 19.13.2　ATM网络中的压缩问题　508

 19.13.3　数据包视频的压缩算法　509

19.14　小结　510

19.15　项目与习题　510

附录A　概率与随机过程　511

A.1　概率　511

 A.1.1　发生频率　511

 A.1.2　信任度量　512

 A.1.3　公理方法　513

A.2　随机变量　514

A.3　分布函数　515

A.4　期望　517

 A.4.1　均值　518

 A.4.2　二阶矩　518

 A.4.3　方差　518

A.5　分布的类型　519

 A.5.1　均匀分布　519

 A.5.2　高斯分布　519

 A.5.3　拉普拉斯分布　519

 A.5.4　伽玛分布　519

A.6　随机过程　520

A.7　项目与习题　521

附录B　矩阵概念简要回顾　522

B.1　矩阵　522

B.2　矩阵运算　523

附录C　根格　527

参考文献　529

索引　544