数据压缩完全指南第四版：大卫·萨洛蒙

5星 · 超过95%的资源需积分: 10 115 浏览量更新于2023-07-13 1 收藏 7.21MB PDF 举报

"《Data Compression - The Complete Reference, Fourth Edition》是戴维·萨洛蒙教授撰写的一本关于数据压缩的权威参考书籍，第四版增加了由乔瓦尼·莫塔和大卫·布莱恩特的贡献。这本书深入探讨了数据压缩的各个方面，包括理论、算法和技术。" 在数据压缩领域，这本著作提供了全面的指导，涵盖了从基础概念到高级技术的广泛知识。数据压缩是一种减少数据量的技术，常用于存储、传输和处理大量信息时提高效率。书中的内容可能包括以下关键知识点： 1. **压缩原理**：解释了数据压缩的基本原理，如熵、信息理论和编码理论，这些是理解压缩技术的基础。 2. **无损压缩**：介绍了如何通过无损压缩算法（如霍夫曼编码、算术编码）在不损失数据的情况下减小文件大小。 3. **有损压缩**：讨论了有损压缩技术，如脉冲编码调制（PCM）、离散余弦变换（DCT，如JPEG）和小波变换（如JPEG 2000），以及它们在图像和音频处理中的应用。 4. **熵编码与预测编码**：分析了熵编码（如游程编码、字典编码）和预测编码（如差分脉冲编码调制，DPCM）等方法，这些是数据压缩的重要组成部分。 5. **数据压缩标准**：书中可能会涵盖各种标准，如ZIP、RAR、GZIP、PNG、MP3和MPEG，这些标准在实际应用中广泛使用。 6. **视频压缩**：讨论了视频编码技术，如MPEG系列、H.26x系列，以及如何处理时间序列数据以实现高效视频压缩。 7. **字典方法**：如LZ77、LZ78和他们的变体，这些方法在文本压缩和数据流压缩中起到重要作用。 8. **源码压缩**：介绍了如何针对特定编程语言或数据格式进行压缩，以优化代码或程序的大小。 9. **实时压缩与硬件实现**：探讨了如何在硬件上实现压缩和解压缩算法，以及在实时系统中的应用。 10. **压缩与解压缩算法的性能评估**：书中可能包含关于算法复杂度、压缩比、解压速度等指标的分析，帮助读者理解不同算法的优缺点。此外，这本书还可能包含了大量实例、实践案例和练习，以帮助读者理解和应用所学知识。对于IT专业人士、研究人员和学生来说，这是一本不可或缺的数据压缩参考书。

xvi Preface to the Second Edition

The second new chapter, Chapter 6, discusses video compression. The chapter

opens with a general description of CRT operation and basic analog and digital video

concepts. It continues with a general discussion of video compression, and it concludes

with a description of MPEG-1 and H.261.

Audio compression is the topic of the third new chapter, Chapter 7. The ﬁrst

topic in this chapter is the properties of the human audible system and how they can

be exploited to achieve lossy audio compression. A discussion of a few simple audio

compression methods follows, and the chapter concludes with a description of the three

audio layers of MPEG-1, including the very popular mp3 format.

Other new material consists of the following:

Conditional image RLE (Section 1.4.2).

Scalar quantization (Section 1.6).

The QM coder used in JPEG, JPEG 2000, and JBIG is now included in Section 2.16.

Context-tree weighting is discussed in Section 2.19. Its extension to lossless image

compression is the topic of Section 4.24.

Section 3.4 discusses a sliding buﬀer method called repetition times.

The troublesome issue of patents is now also included (Section 3.25).

The relatively unknown Gray codes are discussed in Section 4.2.1, in connection

with image compression.

Section 4.3 discusses intuitive methods for image compression, such as subsampling

and vector quantization.

The important concept of image transforms is discussed in Section 4.4. The discrete

cosine transform (DCT) is described in detail. The Karhunen-Lo`eve transform, the

Walsh-Hadamard transform, and the Haar transform are introduced. Section 4.4.5 is a

short digression, discussing the discrete sine transform, a poor, unknown cousin of the

DCT.

JPEG-LS, a new international standard for lossless and near-lossless image com-

pression, is the topic of the new Section 4.7.

JBIG2, another new international standard, this time for the compression of bi-level

images, is now found in Section 4.10.

Section 4.11 discusses EIDAC, a method for compressing simple images. Its main

innovation is the use of two-part contexts. The intra context of a pixel P consists of

several of its near neighbors in its bitplane. The inter context of P is made up of pixels

that tend to be correlated with P even though they are located in diﬀerent bitplanes.

There is a new Section 4.12 on vector quantization followed by sections on adaptive

vector quantization and on block truncation coding (BTC).

Block matching is an adaptation of LZ77 (sliding window) for image compression.

It can be found in Section 4.14.

Preface to the Second Edition xvii

Diﬀerential pulse code modulation (DPCM) is now included in the new Section 4.23.

An interesting method for the compression of discrete-tone images is block decom-

position (Section 4.25).

Section 4.26 discusses binary tree predictive coding (BTPC).

Preﬁx image compression is related to quadtrees. It is the topic of Section 4.27.

Another image compression method related to quadtrees is quadrisection.Itis

discussed, together with its relatives bisection and octasection,inSection4.28.

The section on WFA (Section 4.31) was wrong in the ﬁrst edition and has been

completely rewritten with much help from Karel Culik and Raghavendra Udupa.

Cell encoding is included in Section 4.33.

DjVu is an unusual method, intended for the compression of scanned documents.

It was developed at Bell Labs (Lucent Technologies) and is described in Section 5.17.

The new JPEG 2000 standard for still image compression is discussed in the new

Section 5.19.

Section 8.4 is a description of the sort-based context similarity method. This method

uses the context of a symbol in a way reminiscent of ACB. It also assigns ranks to

symbols, and this feature relates it to the Burrows-Wheeler method and also to symbol

ranking.

Preﬁx compression of sparse strings has been added to Section 8.5.

FHM is an unconventional method for the compression of curves. It uses Fibonacci

numbers, Huﬀman coding, and Markov chains, and it is the topic of Section 8.9.

Sequitur, Section 8.10, is a method especially suited for the compression of semistruc-

tured text. It is based on context-free grammars.

Section 8.11 is a detailed description of edgebreaker, a highly original method for

compressing the connectivity information of a triangle mesh. This method and its various

extensions may become the standard for compressing polygonal surfaces, one of the

most common surface types used in computer graphics. Edgebreaker is an example of a

geometric compression method.

All the appendices have been deleted because of space considerations. They are

freely available, in PDF format, at the book’s Web site. The appendices are (1) the

ASCII code (including control characters); (2) space-ﬁlling curves; (3) data structures

(including hashing); (4) error-correcting codes; (5) ﬁnite-state automata (this topic is

needed for several compression methods, such as WFA, IFS, and dynamic Markov cod-

ing); (6) elements of probability; and (7) interpolating polynomials.

The answers to the exercises have also been deleted and are available at the book’s

Web site.

Currently, the book’s Web site is part of the author’s Web site, which is located

at http://www.ecs.csun.edu/~dxs/. Domain name BooksByDavidSalomon.com has

been reserved and will always point to any future location of the Web site. The author’s

Preface to the

First Edition

Historically, data compression was not one of the ﬁrst ﬁelds of computer science. It

seems that workers in the ﬁeld needed the ﬁrst 20 to 25 years to develop enough data

before they felt the need for compression. Today, when the computer ﬁeld is about 50

years old, data compression is a large and active ﬁeld, as well as big business. Perhaps

the best proof of this is the popularity of the Data Compression Conference (DCC, see

endofbook).

Principles, techniques, and algorithms for compressing diﬀerent types of data are

being developed at a fast pace by many people and are based on concepts borrowed from

disciplines as varied as statistics, ﬁnite-state automata, space-ﬁlling curves, and Fourier

and other transforms. This trend has naturally led to the publication of many books on

the topic, which poses the question, Why another book on data compression?

The obvious answer is, Because the ﬁeld is big and getting bigger all the time,

thereby “creating” more potential readers and rendering existing texts obsolete in just

a few years.

The original reason for writing this book was to provide a clear presentation of

both the principles of data compression and all the important methods currently in

use, a presentation geared toward the nonspecialist. It is the author’s intention to have

descriptions and discussions that can be understood by anyone with some background

in the use and operation of computers. As a result, the use of mathematics is kept to a

minimum and the material is presented with many examples, diagrams, and exercises.

Instead of trying to be rigorous and prove every claim, the text many times says “it can

be shown that ...”or“itcanbeprovedthat....”

The exercises are an especially important feature of the book. They complement the

material and should be worked out by anyone who is interested in a full understanding of

data compression and the methods described here. Almost all the answers are provided

(at the book’s Web page), but the reader should obviously try to work out each exercise

before peeking at the answer.

xx Preface to the First Edition

Acknowledgments

I would like especially to thank Nelson Beebe, who went meticulously over the entire

text of the ﬁrst edition and made numerous corrections and suggestions. Many thanks

also go to Christopher M. Brislawn, who reviewed Section 5.18 and gave us permission

to use Figure 5.64; to Karel Culik and Raghavendra Udupa, for their substantial help

with weighted ﬁnite automata (WFA); to Jeﬀrey Gilbert, who went over Section 4.28

(block decomposition); to John A. Robinson, who reviewed Section 4.29 (binary tree

predictive coding); to Øyvind Strømme, who reviewed Section 5.10; to Frans Willems

and Tjalling J. Tjalkins, who reviewed Section 2.19 (context-tree weighting); and to

Hidetoshi Yokoo, for his help with Sections 3.17 and 8.4.

The author would also like to thank Paul Amer, Guy Blelloch, Mark Doyle, Hans

Hagen, Emilio Millan, Haruhiko Okumura, and Vijayakumaran Saravanan, for their help

with errors.

We seem to have a natural fascination with shrinking and expanding objects. Since

our practical ability in this respect is very limited, we like to read stories where people

and objects dramatically change their natural size. Examples are Gulliver’s Travels by

Jonathan Swift (1726), Alice in Wonderland by Lewis Carroll (1865), and Fantastic

Voyage by Isaac Asimov (1966).

Fantastic Voyage started as a screenplay written by the famous writer Isaac Asimov.

While the movie was being produced (it was released in 1966), Asimov rewrote it as

a novel, correcting in the process some of the most glaring ﬂaws in the screenplay.

The plot concerns a group of medical scientists placed in a submarine and shrunk to

microscopic dimensions. They are then injected into the body of a patient in an attempt

to remove a blood clot from his brain by means of a laser beam. The point is that the

patient, Dr. Benes, is the scientist who improved the miniaturization process and made

it practical in the ﬁrst place.

Because of the success of both the movie and the book, Asimov later wrote Fantastic

Voyage II: Destination Brain, but the latter novel proved a ﬂop.

But before we continue here is a question that you

might have already asked: “OK, but why should I

be interested in data compression?” Very simple:

“DATA COMPRESSION SAVES YOU MONEY!”

More interested now? We think you should be. Let

us give you an example of data compression application

that you see every day. Exchanging faxes every day

...

From http://www.rasip.etf.hr/research/compress/index.html

Northridge, California David Salomon

剩余1117页未读，继续阅读

tianjiazi

粉丝: 0
资源: 3

数据压缩完全指南第四版：大卫·萨洛蒙

[数据压缩技术简介（第三版）].Introduction.to.Data.Compression.pdf

Data compression the complete reference 4th edition

Data Compression The Complete Reference

Data_Compression+The+Complete+Reference+4th+edition

COMISR Compression-Informed Video Super-Resolution.pdf

Data.Compression.The.Complete.Reference.

mina-filter-compression-2.0.0-M1-sources.jar

Data.Compression.The.Complete.Reference.(2004),.3Ed.ShareVirus

Variable-length Codes for Data Compression.pdf

PDF-format---compression-algorithm.rar_图形图像处理_Visual_C++_

最新资源