Lossless Compression Handbook

INDEX

A

ACB algorithm, Buynovsky's,

201-203

Adaptive coding

binary arithmetic coding, 134-139

cumulative distribution update

direct, 133-134

periodic, 140-142

tree-based, 139-140

strategies for computing symbol

distributions, 132

Adaptive entropy coder

code selection, 317

fundamental sequence encoding,

313-314

low-entropy options

second-extension option, 316

zero-block option, 31 6-317

no compression, 317

split-sample option, 314-315

Adaptive Huffman coding

algorithm M, 94

brute force, 89-90

Failer, Gallager, and Knuth (FGK)

algorithm, 91-93

splay tree algorithm, 93-94

Vitter's algorithm A, 93

Additive codes, 72-73, 77

Algorithmic Information Theory,

see

Kolmogorov complexity

Algorithmic Prefix Complexity,

42-43, 48

Algorithm M, 94

Amplitude range, and segmentation,

259-260

Apostolico and Fraenkel codes,

67-69, 77

Approximate arithmetic, 115-118

Arithmetic coding

adaptive, 336

approximate arithmetic, 115-118

code values, 104-106

context-based, 397

correct decoding: conditions for,

118-120

decoding process, 11 0-111

dynamic sources, 112-113

encoder and decoder synchronized

decisions, 113

encoding process, 106-I09

entropy-coding methods, 102

intervals

positive-length and disjoint,

118-119

rescaling, 114-115

inverse operations, 120

model for Burrows-Wheeler

compression, 177-179

nested subintervals, 119-120

notation, 103-104

optimality, 111-112

practical problems, 102-103

separation of coding and source

modeling, 113-114

Arithmetic coding implementation,

120-147

adaptive coding, 132-142

coding with fixed-precision

arithmetic, 121-132

complexity analysis, 142-147

integer-based, 147-150

Arithmetic encoder, 19-21

Arithmetic operations, speed of,

146-147

Asymptotic equipartition property,

26-34

ATMEL digital audio decoder,

432-433

Average

filter, 380

B

Backup, remote, massive data sets,

280

Balanced pairs,

rsync

algorithm,

283-284

Bandwidth, in telemetry

compression, 250-251

Bayesian model averaging, 218

Bidirectional dictionary methods,

161

Bilevel image data, 336--338

Binary arithmetic coding, 134-139

Binary polynomial representation,

56, 74-75

Binary sources, 10

Biocompress

programs, 162

Biomolecular sequences,

compression, 162-163

Bisection search, 143-145

Bit-plane coding, JPEG2000,

360-364

Bit rate

for lossless audio signal, 256

variable, peak

vs.

average, 264

Bits per character

averages, 240

entropy and, 228-229

for new transforms, 242

Bitstream scaling, architecture for,

421

Blending

model-based, 218-219

performance-based, 218

probability domain, 219

Blocking system, 17-18

Block moves, in delta compression,

273

Block size,

rsync

algorithm,

281-283

447